0

I'm trying to figure out how I can change my grammar to get rid of the ambiguity but I'm having a hard time figuring it out, unfortunately I haven't been able to find an example that's close enough to my problem either.

The grammar:

$S\rightarrow A|C$

$A\rightarrow aaaB$

$B \rightarrow bBc | bc$

$C\rightarrow Dccc$

$D\rightarrow aDb|ab$

I believe this grammar is ambiguous because I can take two different paths and still get the string w='aaabbbccc'.

I'm not too sure where to start here, the grammar above is a representation of the union of two different grammars represented by the following

{$aaab^nc^n$ | $n>=1$} U {$a^mb^mccc$ | $m>=1$}

I don't have any work to show so far as I'm still trying to figure out the right course of action for getting rid of the ambiguity.

AFC
  • 383

1 Answers1

1

HINT: There are probably better ways, but since the word $a^3b^3c^3$ is the only one that’s problematic, one very simple way is to use the same basic idea to generate the language

$$\{a^3b^nc^n:n\ge 4\}\cup\{a^nb^nc^3:n\ge 4\}$$

and to generate each of the $5$ words $a^3b^nc^n$ and $a^nb^nc^3$ with $n\in\{1,2,3\}$ individually, directly from $S$.

Brian M. Scott
  • 616,228