Consider the following languages: \(L_1 = \{ a^nb^nc^m \} \cup \{a^nb^mc^m\},…
2019
Consider the following languages:
\(L_1 = \{ a^nb^nc^m \} \cup \{a^nb^mc^m\}, n, m \geq 0\)
\(L_2 =\{ww^R \mid w \in\{ a, b \}^*\}\) Where \(𝑅\) represents reversible operation.
Which one of the following is (are) inherently ambiguous languages(s)?
- A.
Only
\(𝐿_1\) - B.
Only
\(𝐿_2\) - C.
both
\(𝐿_1\)and\(𝐿_2\) - D.
neither
\(𝐿_1\)nor\(𝐿_2\)
Attempted by 56 students.
Show answer & explanation
Correct answer: A
Answer: Only L1 is inherently ambiguous.
Why L1 is inherently ambiguous:
L1 is the language { a^n b^n c^m } ∪ { a^n b^m c^m }.
For every n ≥ 0 the string a^n b^n c^n belongs to the first part (choose m = n) and also to the second part (choose m = n).
Thus each a^n b^n c^n has at least two distinct parse trees (one deriving it from the first component, one from the second).
There are infinitely many such strings, so this ambiguity cannot be removed by a different grammar: L1 is a standard example of an inherently ambiguous context-free language.
Why L2 is not inherently ambiguous:
L2 = { w w^R | w ∈ {a,b}* } is the set of even-length palindromes.
A simple unambiguous grammar for L2 is:
S -> ε | a S a | b S b
Each application of a S a or b S b peels a unique matching outer pair, so the decomposition is unique and derivations are unique by induction on string length. Therefore L2 is unambiguous.
Conclusion: L1 is inherently ambiguous while L2 is not, so the correct choice is that only the first language is inherently ambiguous.
A video solution is available for this question — log in and enroll to watch it.