Find unambiguous grammar for an ambiguous grammar

Question

Hi I want to find an unambiguous grammar for a known ambiguous one, and the production is like this:

S->bA|aB
A->a|aS|bAA
B->b|bS|aBB

I have found the string to prove this grammar is ambiguous: bbaaba. I wonder whether it is doable to convert the grammar into unambiguous. I have approached it from this perspective: in the above counter-example, the difference shows up when we have AA in the list, then whether we are changing the first A to contain S or the second will make the next step different. So I think maybe I can restrict A to go only via the first or the second A and hence eliminate the ambiguity, like this:

S->bA|aB
A->a|aS|baA|baSA
B->b|bS|abB|abSB

I'm not sure whether my approach or answer is correct or not. I understand there is no algo for this kind of conversion, but are there any kind of 'common steps' for getting the unambiguous grammar?

Answer 1

I'm not sure whether my approach or answer is correct or not.

It is not correct. Your modified grammar can produce at most three consecutive 'a's or 'b's, while the original grammar can produce an unbounded number of consecutive 'a's or 'b's.

Your approach starts fine by looking for counterexamples, but then runs into a trap by staying too close to the given grammar. This is a trap, because the problem asks for extensional equality of languages. After you isolated the critical part of the grammar which generates the problem, you should first try to understand the generated language (that interacts with that part), before starting to modify the grammar.

I understand there is no algo for this kind of conversion, but are there any kind of 'common steps' for getting the unambiguous grammar?

1. Your first step to look for a counterexample and isolate the part of the grammar which generates the problem makes sense.
2. My next step would be trying to understand the generated language. Let me try your example:

From S, I can generate any number of 'a's, followed by the same number of 'b's, and end up in S again. Can I ever generate more 'a's than 'b's? No, the number of 'a' or 'A' on the left side is identical to the number of 'a' or 'A' minus 'b' or 'B' on the right side for all rules. Can I generate any string with the same number of 'a's and 'b's? Yes, because ...

Ah, so the generated language is simply the language where the number of 'a's equals the number of 'b's.

3. After you understood the generated language, you can try to determine whether it can be generated by an unambiguous grammar, and write down such a grammar if desired. Let me try for your example:

The generated language is so simple, I would have heard if this language were ambiguous. It should even be deterministic, I can just push 'a's on the stack when there are more 'a's than 'b's, and push 'b's on the stack when there are more 'b's than 'a's. Of course, when the symbol on top of the stack differs from the current symbol, then I will just pop it. I know it is possible to convert this sort of deterministic PDA into a deterministic grammar, so I'm done without even trying to write down any specific deterministic grammar.