Can a regular grammar be ambiguous?

Solution 1:

There do indeed exist ambiguous regular grammars. Take for example

$S\rightarrow A~|~B$

$A\rightarrow a$

$B\rightarrow a$

Solution 2:

Every regular grammar which contains a rule of the form $A \rightarrow aB$ (reachable from the start symbol) has an equivalent ambiguous regular grammar. Just take a new non-terminal symbol, $D$, add the rule $A \rightarrow aD$, and for each rule with $B$ as the left symbol add a new rule obtained by replacing each $B$ in that rule with $D$.

For example, the following regular grammar is unambiguous:

$$\begin{align} S &\rightarrow aS \mid bA \\ A &\rightarrow bA \mid aB \mid \varepsilon \\ B &\rightarrow aB \mid \varepsilon \end{align}$$

Taking the rule $A \rightarrow aB$ we construct an equivalent ambiguous regular grammar as follows: $$\begin{align} S &\rightarrow aS \mid bA \\ A &\rightarrow bA \mid aB \mid aD \mid \varepsilon \\ B &\rightarrow aB \mid \varepsilon \\ D &\rightarrow aD \mid \varepsilon \end{align}$$

Then the string $ba$ has the following two leftmost derivations:

• $S \rightarrow bA \rightarrow baB \rightarrow ba \varepsilon = ba$
• $S \rightarrow bA \rightarrow baD \rightarrow ba \varepsilon = ba$