Turning an ambiguous grammar to an unambiguous one

357 Views Asked by At

I understand the topic and how to do it, but then I stumbled upon this example which is: The context-free grammar that describes all words that have the string ab in them. The grammar is

$$ S \Rightarrow TabT $$ $$ T \Rightarrow aT | bT |cT | \epsilon $$

Because we can have any words between the $ab$ that means whatever I do it will still be ambiguous. For example, if I have the starting terminal ab in (ab) so you can recognize them, I can have both $(ab)ab$ and $ab(ab)$

The only solution I can think of is to use brackets which is not allowed

1

There are 1 best solutions below

1
On BEST ANSWER

Hint: Define the grammar as:

$$S\Rightarrow PabT$$

where $P$ is any string that does not contain $ab$ and $T$ is any string.

$P$ is a little tricky, but not that tricky.