3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Matt Mar 25 '13 at 4:59
  • $\begingroup$ @Matt: Yes, that's my thinking. $\endgroup$ – user642796 Mar 25 '13 at 5:03
  • $\begingroup$ @Matt: You're welcome! $\endgroup$ – user642796 Mar 25 '13 at 5:43

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.