The language L = { aⁿ bⁿ aᵐ bᵐ | n ≥ 0, m ≥ 0 } is
2013
The language L = { aⁿ bⁿ aᵐ bᵐ | n ≥ 0, m ≥ 0 } is
- A.
Context free but not linear
- B.
Context free and linear
- C.
Not context free and not linear
- D.
Not context free but linear
Attempted by 30 students.
Show answer & explanation
Correct answer: A
The language L is the concatenation of two context-free languages {a^n b^n}. Since CFLs are closed under concatenation, L is context-free. However, it cannot be generated by a linear grammar because two independent nested structures require multiple non-terminals simultaneously.
A video solution is available for this question — log in and enroll to watch it.
Loading lesson…