World's most popular travel blog for travel bloggers.

[Solved]: Why is $\{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ an inherently ambiguous language?

, , No Comments
Problem Detail: 

I came across a very hard interview question in last month's Ph.D. entrance exam. It was asking which one of the languages is inherently ambiguous. Short answer says 2). Why is the language in 2) an inherently ambiguous language?

1) $L = \{a^n b^{2n} c: n\geq 0\} \cup \{a^{2n} b^n d: n\geq 0\}$

2) $L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$

3) $L = \{a^n b a^{2n}: n \geq 0\} \cup \{a^{2n} b a^n: n\geq 0\}$

4) $L = \{\omega: \omega \in \{a,b\}^*: \omega \text{ does not have substring $baba$}\} \cup \{\omega : \omega \in \{a,b\}^*: \omega \text{ does not have substring $abab$} \}$

Asked By : Maryam Panahi

Answered By : Yuval Filmus

If $L_1,L_2$ are two disjoint context-free languages which are not inherently ambiguous, then $L_1 \cup L_2$ is also a context-free language which is not inherently ambiguous. The reason is simple: starting with context-free grammars for $L_1,L_2$ with start symbols $S_1,S_2$ (respectively) and otherwise disjoint non-terminals, you can construct an unambiguous grammar for $L_1 \cup L_2$ by adding a new start symbol $S$ and the productions $S\to S_1|S_2$. This takes care of 1) and 3), once you construct unambiguous grammars for the constituent languages.

As Palec mentions, 4) is regular, and so admits a regular grammar which corresponds to a DFA accepting it. This grammar has as non-terminals the states of the DFA, and productions $A \to aB$ if the DFA moves from $A$ to $B$ upon reading $a$. For each final state $F$ we add a production $F\to\epsilon$, and the start symbol is the start state. This description should make it clear that the grammar is unambiguous.

Intuitively, 2) could be unambiguous since words of the form $a^n b^m c^p$ with $n \neq m \neq p$ could have two different parse trees, corresponding to the two constituent languages. Proving this formally could be tedious. The only method I know consists of coming up with two words $x,y$ that can be pumped to the same word $w$ in such a way that makes it clear that the corresponding parse trees are different. If you want to pursue this further, a good first step will be to read some examples of this method.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40637

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback