Can a regular grammar be ambiguous?

Question

An ambiguous grammar is a context-free grammar for which there exists a string that has more than one leftmost derivation, while an unambiguous grammar is a context-free grammar for which every valid string has a unique leftmost derivation.

A regular grammar is a mathematical object, $G$, with four components, $G = (N, \Sigma, P, S)$, where

• $N$ is a nonempty, finite set of nonterminal symbols,
• $\Sigma$ is a finite set of terminal symbols, or alphabet, symbols,
• $P$ is a set of grammar rules, each of one having one of the forms:
  • $A \rightarrow aB$
  • $A \rightarrow a$
  • $A \rightarrow \varepsilon$ for $A, B \in N$, $a \in Σ$, and $\varepsilon$ the empty string, and
• $S ∈ N$ is the start symbol.

Now the question is: Can a regular grammar also be ambiguous?

Answer 1

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$

Answer 2

There do indeed exist ambiguous regular grammars. Take for example

$S\rightarrow A~|~B$

$A\rightarrow a$

$B\rightarrow a$

Answer 3

See this:
S --> aA|aB
A --> λ
B --> λ
It is a right-regular grammer with ambiguity as 'a' can be printed by either following aA from S or aB from S.

Answer 4

Just have a look at this naive example,

$S→A | B$

$A→λ$

$B→λ$

In this example, the string $λ$ can be printed in two ways, which gives rise to ambiguity.

Answer 5

We know from Chomsky's Heirarchy of Languages that every regular language is also a context free language.

We also know every regular language is also a regular grammar.

Therefore, every regular grammar is also a context free grammar. Since CFGs can be abmbiguous, therefore by logic, some regular grammars can be ambiguous. (not ALL but there exists, in this case).