Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to find an unambiguous context free language for the ambiguous language:

$$S\rightarrow AB$$ $$A\rightarrow Ba| b$$ $$B \rightarrow aA|b$$

I understand the language makes up of strings that have exactly 2 $b$'s and for each b on either side of each $b$ the language generates $a$'s in a balanced manner such that no side differs by a count of 1 $a$. (I hope that make sense). However, I can't think of a method to create a new grammar to make it unambiguous.

Thanks for any help.

share|cite|improve this question
up vote 3 down vote accepted

Note that the language consists of those strings of the form $\newcommand{\A}{\mathtt{a}}\newcommand{\B}{\mathtt{b}}\A^i \B \A^j \A^k \B \A^\ell$ where $i \leq j \leq i + 1$ and $\ell \leq k \leq \ell + 1$. We can write a new CFG for this language to make this explicit at the beginning :

$$\begin{align} S &\rightarrow A_{=} A_{=} \mid A_{<} A_{=} \mid A_{=} A_{>} \mid A_{<} A_{>} \\ A_{=} &\rightarrow \A A_{=} \A \mid \B \\ A_{<} &\rightarrow \A A_{<} \A \mid \B\A \\ A_{>} &\rightarrow \A A_{>} \A \mid \A\B \end{align}$$ Ambiguity occurs when the rules $S \rightarrow A_{<} A_{=}$ and $S \rightarrow A_{=} A_{>}$ are taken. Do we need both?

share|cite|improve this answer
Ah ok so you can eliminate one of them because having the left side unbalanced and right side balanced is the same thing as having the right side imbalanced and left side balanced since both of them just contribute to the middle having one extra "a". Thus this eliminates the ambiguity in the language. Is this the right line of thought? – Matt Mar 25 '13 at 4:59
@Matt: Yes, that's my thinking. – arjafi Mar 25 '13 at 5:03
Thanks for the help! – Matt Mar 25 '13 at 5:40
@Matt: You're welcome! – arjafi Mar 25 '13 at 5:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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