CS402 Theory of Automata Spring 2009 Final Term Paper

[viki]

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
  

For Complete paper Download the file


  CS402_01_FINAL_Spring 2009-1.pdf (Size: 46.69 KB / Downloads: 794)