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 : Click on Discuss to view users comments. |
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 : Click on Discuss to view users comments. |
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 : Click on Discuss to view users comments. |
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 : Click on Discuss to view users comments. |
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 : Click on Discuss to view users comments. |
