Consider the following languages. L1 = {ai bj ck | i = j, k ≥ 1} L1 = {ai bj |…
2008
Consider the following languages.
L1 = {ai bj ck | i = j, k ≥ 1}
L1 = {ai bj | j = 2i, i ≥ 0}
Which of the following is true?
- A.
L1 is not a CFL but L2 is
- B.
L1 ∩ L2 = ∅ and L1 is non-regular
- C.
L1 ∪ L2 is not a CFL but L2 is
- D.
There is a 4-state PDA that accepts L1, but there is no DPDA that accepts L2
Attempted by 19 students.
Show answer & explanation
Correct answer: B
The correct answer is that L1 = {a^i b^j c^k | i = j, k ≥ 1} is a context-free language (CFL), while L2 = {a^i b^j | j = 2i, i ≥ 0} is also a CFL. Both languages require counting and matching symbols, which can be done with a pushdown automaton (PDA). Therefore, both are context-free languages.
A video solution is available for this question — log in and enroll to watch it.
Loading lesson…