Can a regular grammar be ambiguous?
There do indeed exist ambiguous regular grammars. Take for example
$S\rightarrow A~|~B$
$A\rightarrow a$
$B\rightarrow a$
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$