# Theory Of Computation MCQ - Context free languages

11:

Define for the context free language
L< {0;1} init (L) =  { u | u v   ε  L for some v in {0, 1}}

If L { w | w is nonempty and has an equal number of 0's and 1's}, then init (L) is set of all binary strings

 A. with unequal numbers of 0's and 1's. B. including the null string. C. Both (a) and (b) D. None of these Answer Report Discuss Option: B Explanation : Click on Discuss to view users comments. Write your comments here:
12:

Which of the following CFG's can't be simulated by an FSM ?

 A. s ---> sa | a B. s ---> abX , X --> cY, Y --> a | axY C. s ---> a sb | ab D. none of these Answer Report Discuss Option: C Explanation : Click on Discuss to view users comments. Write your comments here:
13:

Basic limitation of FSM is that it

 A. cannot remember arbitrary large amount of information B. sometimes fails to recognize grammars that are regular C. sometimes recognizes grammars are not regular D. None of these Answer Report Discuss Option: A Explanation : Click on Discuss to view users comments. Write your comments here:
14:

Which of the following is not possible algorithmically ?

 A. Regular grammar to context free grammar B. Non-deterministic FSA to deterministic FSA C. Non-deterministic PDA to deterministic PDA D. None of these Answer Report Discuss Option: C Explanation : Click on Discuss to view users comments. Write your comments here:
15:

The set {anbn | n = 1, 2, 3 ...} can be generated by the CFG

 A. S —>ab | aSb B. S —>aaSbb + abS C. S—> ab | aSb | E D. S —>aaSbb | ab | aabb Answer Report Discuss Option: D Explanation : Option (b) is wrong because it can't generate aabb (in fact any even power). Option (c) is wrong since it generates E also. Both options (a) and (d) are correct. Click on Discuss to view users comments. Write your comments here:

X