0
votes

I've been at trying to solve this for hours and it's just been an endless loop of trial and error. I need to make this grammar unambiguous:

S -> Sa | Sb | aS | bS | aa

As I understand this can generate any combination of a's and b's with "aa" appearing somewhere. The main problem is it can generate from both sides so there are several parse trees. My best attempt so far is something like this:

S -> aS | bS | aT
T -> aU | a
U -> bU | b

That generates any a's and b's...then forces a second a, and allows adding more b's. That doesn't allow every string though...can't do "abaaba". I can't wrap my head around how to make this unambiguous.

1

1 Answers

1
votes

Try to produce a language (P) which does not contain two consecutive as. (Which means that every a must be followed with a b). And another language (S) which can contain any sequence of as and bs. Then you can unambiguously parse your language as PaaS. (It's unambiguous because the aa in that production must be the first one in the string to be produced.)

(I chose P and S from Prefix and Suffix, respectively. Sometimes mathematics is just too terse.)