# Can a regular grammar be ambiguous?

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?

There do indeed exist ambiguous regular grammars. Take for example

$S\rightarrow A~|~B$

$A\rightarrow a$

$B\rightarrow a$

• WoW ! That's funny ! Thank you :) May 6, 2016 at 7:20
• I like this one because it answers quickly to the question. Jan 2, 2021 at 18:58
• Could you clarify how is this a regular grammar having a production S -> A where A is a non-terminal symbol? AFAIK this doesn't comply with the restrictions for the productions having the form A -> a / A -> empty / A -> aB ((source) Oct 14, 2021 at 3:24

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$

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.

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.

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).

• It's not logical Nov 23, 2020 at 12:57
• Just because you don't understand what i wrote, does not mean its not logical. Please don't comment nonesense. Thanks. May 16, 2021 at 3:28
• Im sorry but that some cfg are ambiguous do not implies that the subset of regular language is ambiguous : "Therefore by logic" is wrong. Take for instance "primes are odd", "some odd numbers are divisible by 9" don't imply "some primes are divisible by 9". May 17, 2021 at 7:43