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