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$} \}$

  • 2
    $\begingroup$ You can immediately rule out 1) and 3) by constructing their unambiguous CFG. The language in 4) is regular (complement and union preserves regularity) and therefore there is an unambiguous regular grammar (which is also context-free). Thus the only remaining option is 2). If you’re sure one of them is inherently ambiguous, you can be sure it is the one in 2). $\endgroup$ – Palec Mar 22 '15 at 10:27
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understaing. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Mar 22 '15 at 11:05
  • 1
    $\begingroup$ Mind what mods and hi-rep users tell you, @MaryamPanahi. I see two of your questions have been closed Continuing in such a trend could lead to a question ban. You need to have 20 rep to be able to participate in the chat, so for the time being use comments here to try to shortly answer what Raphael asks. When we know what specific problems you have with understanding why $L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ is inherently ambiguous, we will be able improve your question and answer it. $\endgroup$ – Palec Mar 22 '15 at 12:34
  • 1
    $\begingroup$ E.g. do you want to get a proof that that language is inherently ambiguous? Do you know how to prove inherent ambiguity for any other language? Have you tried to read such a proof for another language and failed to understand a step? $\endgroup$ – Palec Mar 22 '15 at 12:39
  • 1
    $\begingroup$ Most likely, the purpose of the question is not to have you prove that case 2) is an inherently ambiguous language, but only to force you to show that the other 3 are not inherently ambiguous (in case that was not clear). $\endgroup$ – babou Mar 22 '15 at 17:49

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.

| cite | improve this answer | |
  • $\begingroup$ thanks, so help full. really is it possible learn more to me and say what is the result of union of (1) to (4) ? I want to learn about unions of this grammar at first. $\endgroup$ – Maryam Panahi Mar 22 '15 at 19:25
  • $\begingroup$ I don't understand the question. Are you having trouble with unions of languages or with unions of grammars? $\endgroup$ – Yuval Filmus Mar 22 '15 at 19:29
  • $\begingroup$ I'm So Sorry. I means what is the result of (1) L ? (2) L ? (3) L ? (4) L? I think at first I want to able to determine this after that knowing ambiguous ? am I right? $\endgroup$ – Maryam Panahi Mar 22 '15 at 19:36
  • $\begingroup$ The result is just the union. There isn't necessarily any better representation. $\endgroup$ – Yuval Filmus Mar 22 '15 at 19:42
  • $\begingroup$ wow, so there is no better representation, so at next, would you please say what is the tricky point you know about ambiguity from this not well formed representation? $\endgroup$ – Maryam Panahi Mar 22 '15 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.