Theory of Computation and Compilers - 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

Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


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

Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


13. Basic limitation of FSM is that it

Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


14. Which of the following is not possible algorithmically?

Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


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

  • 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.
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *