Home » Theory of Computation » Theory of computation miscellaneous » Question

Theory of computation miscellaneous

Theory of Computation

  1. Consider the following languages :
    L1 = { an bm cn + m : m , n > 1 }
    L2 = { an bn c2n : n > 1 }
    Which one of the following is TRUE ?
    1. Both L1 and L2 are context-free.
    2. L1 is context-free while L2 is not context-free.
    3. L2 is context-free while L1 is not context-free.
    4. Neither L1 nor L2 is context-free.
Correct Option: B

L2 is not context free. No. of b 's will match with no. of a 's leaving c 's to be matched with no one. So L2 cannot be context free.



Your comments will be displayed only after manual approval.