## CS402 Theory of Automata Spring 2009 Final Term Paper

FINALTERM EXAMINATION
Spring 2009
CS402 - Theory of Automata

Marks: 75

Question No: 1 ( Marks: 1 ) - Please choose one
(a+b)*a(a+b)*b(a+b)* is the RE of language defined over ={a,b} having at least one a
and one b

• True
• False
• Such a language does not exist
• None of these

Question No: 2 ( Marks: 1 ) - Please choose one
If r1 = (aa + bb) and r2 = ( a + b) then the language (a + b)* (aa + bb)* will be
generated by

• (r2)(r1)
• (r1 + r2)*
• (r2)*(r1)*
• (r1)*

Question No: 3 ( Marks: 1 ) - Please choose one
In FA starting state is represented by a ________ sign.

• +
• -
• *
• S

Question No: 4 ( Marks: 1 ) - Please choose one
Who did not invent the Turing machine?

• Alan Turing
• A. M. Turing
• Turing
• None of these

Question No: 5 ( Marks: 1 ) - Please choose one
According to _________ machine, Finite set of states containing exactly one START state and
some (may be none) HALT states that cause execution to terminate when the HALT states are

• entered.
• Finite Automata
• TG
• Turing
• Insertion

Question No: 6 ( Marks: 1 ) - Please choose one
Can a turing machine's head ever be in the same location in two successive
steps?

• Yes
• Yes but only in finite languages
• No
• Yes but only in infinite langauges

Question No: 7 ( Marks: 1 ) - Please choose one
Examin the following CFG and select the correct choice
S AB, A BSB, B CC
C SS
A a|b
C b|bb

• abb is a word in the corresponding CFL.
• abb is not the word of corresponding CFL.
• any word can be accept from the corresponding CFL.
• Non of these

Question No: 8 ( Marks: 1 ) - Please choose one
To determine whether a string is generated by the given CFG

• CYK algorithm is used
• CIK algorithm is used
• CNK algorithm is used
• CNM algorithm is used

Question No: 9 ( Marks: 1 ) - Please choose one
The process of finding the derivation of word generated by particular grammar is called____

• Processing
• Parsing
• Programming
• Planing

Question No: 10 ( Marks: 1 ) - Please choose one
Converting the given CFG in CNF is the first rule of _____

• CYK algorithm
• CKY algorithm
• KYC algorithm
• CNK algorithm