-
Consider the following languages.
L1 = {ap | p is a prime number}
L2 = {an bm c2m | n ≥ 0, m ≥ 0}
L3 = {an bn c2n | n ≥ 0}
L4 = {an bn | n ≥ 1}
Which of the following are CORRECT?
I. L1 is context-free but not regular.
II. L2 is not context-free.
III. L3 is not context-free but recursive.
IV. L4 is deterministic context-free.
-
- I, II and IV only
- II and III only
- I and IV only
- III and IV only
- I, II and IV only
Correct Option: D
Consider the given languages.
L1 = {aP | P is a Prime Number},
L2 = 2 { an bm c2m | n ≥ 0 , m ≥ 0 }
L3 = 2 { an bn c2n | n ≥ 0 } , L4 = { an bn | n ≥ 1 } .
Now, consider each option:
(i) L1 is context free but not regular is Incorrect because it is not CFL, it is a CSL (Context sensitive language).
(ii) L2 is not CFL is also Incorrect because it is CFL.
(iii) L3 is not context free but recursive is correct because L3 is CSL (context sensitive language) and every CSL is recursive.
(iv) L4 is deterministic context free is correct because L4 is a proper subset of context free language. Hence option (d) is correct.
