Classical

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

 
 

Option: B

Explanation :


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
 
 

Option: C

Explanation :


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
 
 

Option: A

Explanation :


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
 
 

Option: C

Explanation :


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
 
 

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