I came across a very hard interview exam. It was asked wrote an unambiguous grammar for two following language, Who can hint it to solve it?

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

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

I know 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. but I couldent write grammar for these.

  • $\begingroup$ First write an unambiguous grammar for $\{a^n b^{2n}\}$; then adapt that. While you're at it, show some work or some of your own ideas; that will help people to help you (and otherwise your question without context will likely be rapidly closed). $\endgroup$ – Magdiragdag Apr 14 '15 at 19:20
  • $\begingroup$ @Magdiragdag I do it, but failed. this is very hard for contest I think !! $\endgroup$ – Nima Nakisa Apr 14 '15 at 19:22
  • $\begingroup$ I am curious, was this for a specific job or just a generic test of some sort? $\endgroup$ – copper.hat Apr 14 '15 at 19:23
  • $\begingroup$ So, some ideas to show at least an attempt: what is, according to you, an unambigious grammar? $\endgroup$ – Magdiragdag Apr 14 '15 at 19:23
  • $\begingroup$ @Magdiragdag if one parse tree be at there. $\endgroup$ – Nima Nakisa Apr 14 '15 at 19:24

Spoiler alert.

My solutions.


$$ L ::= Bc \mid Cd \\ B ::= aBbb \mid \epsilon \\ C ::= aaCb \mid \epsilon $$


$$ L ::= A \mid B \\ A ::= b \mid aAaa \\ B ::= aaba \mid aaBa $$

Notice that the base case of the B recursion is $aaba$, not $\epsilon$. This removes ambiguity.

  • $\begingroup$ I try to find a counterexample? how you prove it :) $\endgroup$ – Nima Nakisa Apr 14 '15 at 20:20
  • $\begingroup$ Not sure. To me it's just intuitive. If you've seen enough of these, you can do them. $\endgroup$ – jkabrg Apr 14 '15 at 20:31
  • $\begingroup$ This might not be a helpful answer then. $\endgroup$ – jkabrg Apr 14 '15 at 20:35
  • $\begingroup$ @Nima Nakisa: you prove by induction over the size of a parse tree that a string of symbols belongs to the language specified by the grammar iff it satisfies the specification given in the problem. $\endgroup$ – Rob Arthan Apr 14 '15 at 20:36
  • $\begingroup$ @user3491648: I think it is a very helpful answer - the OP is looking a gift horse in the mouth. $\endgroup$ – Rob Arthan Apr 14 '15 at 20:37

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.