Theory Of Computation MCQ - Context free languages


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


with unequal numbers of 0's and 1's.


including the null string.


Both (a) and (b)


None of these


Option: B

Explanation :


 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

Option: C

Explanation :


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

Option: A

Explanation :


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

Option: C

Explanation :


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

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.

Suggest an improvement