# Is it possible to write an Unambiguous Grammar for Two Hard Language?

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.

• 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). – Magdiragdag Apr 14 '15 at 19:20
• @Magdiragdag I do it, but failed. this is very hard for contest I think !! – Nima Nakisa Apr 14 '15 at 19:22
• I am curious, was this for a specific job or just a generic test of some sort? – copper.hat Apr 14 '15 at 19:23
• So, some ideas to show at least an attempt: what is, according to you, an unambigious grammar? – Magdiragdag Apr 14 '15 at 19:23
• @Magdiragdag if one parse tree be at there. – Nima Nakisa Apr 14 '15 at 19:24

My solutions.

1)

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

2)

$$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.

• I try to find a counterexample? how you prove it :) – Nima Nakisa Apr 14 '15 at 20:20
• Not sure. To me it's just intuitive. If you've seen enough of these, you can do them. – jkabrg Apr 14 '15 at 20:31
• This might not be a helpful answer then. – jkabrg Apr 14 '15 at 20:35
• @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. – Rob Arthan Apr 14 '15 at 20:36
• @user3491648: I think it is a very helpful answer - the OP is looking a gift horse in the mouth. – Rob Arthan Apr 14 '15 at 20:37