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


Sponsored Links

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




For Complete paper Download the file

CS402_01_FINAL_Spring 2009-1.pdf