Consider the following languages L 1 = {a p | p is a prime number} L 2 = {a n b m c 2m | n ≥ 0, m ≥ 0} L 3 = {a n b n c 2n | n ≥ 0} L 4 = {a n b n | n ≥ 1} Which of the following are CORRECT? I. L 1 is context-free but not regular. II. L 2 is not context-free III. L 3 is not context-free but recursive. IV. L 4 is deterministic context-free

Correct Answer is : III and IV only

GATE Computer Science (CS) 2017 Shift 2 Solved Paper

Question : 50 of 65

Marks: +1, -0

Consider the following languages
L₁ = {a^p | p is a prime number}
L₂ = {aⁿb^mc^2m | n ≥ 0, m ≥ 0}
L₃ = {aⁿbⁿc²ⁿ | n ≥ 0}
L₄ = {aⁿbⁿ | n ≥ 1}
Which of the following are CORRECT?
I. L₁ is context-free but not regular.
II. L₂ is not context-free
III. L₃ is not context-free but recursive.
IV. L₄ is deterministic context-free

I, II and IV only
II and III only
I and IV only
III and IV only

Validate

Go to Question:

Prev Question

Next Question