Take the 2-minute tour ×
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.

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|improve this question

1 Answer 1

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|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. –  Arthur Fischer Mar 25 '13 at 5:03
    
Thanks for the help! –  Matt Mar 25 '13 at 5:40
    
@Matt: You're welcome! –  Arthur Fischer Mar 25 '13 at 5:43

Your Answer

 
discard

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.