Given the following two languages: L₁ = { aⁿ bⁿ | n > 1 } ∪ {a} L₂ = { w c wᴿ…
2014
Given the following two languages:
L₁ = { aⁿ bⁿ | n > 1 } ∪ {a}
L₂ = { w c wᴿ | w ∈ {a, b}* }
Which statement is correct?
- A.
Both L₁ and L₂ are not deterministic
- B.
L₁ is not deterministic and L₂ is deterministic
- C.
L₁ is deterministic and L₂ is not deterministic
- D.
Both L₁ and L₂ are deterministic
Attempted by 33 students.
Show answer & explanation
Correct answer: D
L₁ is deterministic because {aⁿ bⁿ} and {a} are both DCFLs. L₂ uses 'c' as a pivot to deterministically match w and wᴿ. Thus, both languages are deterministic context-free.
A video solution is available for this question — log in and enroll to watch it.