6
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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$
$\endgroup$
4
$\begingroup$

There do indeed exist ambiguous regular grammars. Take for example

$S\rightarrow A~|~B$

$A\rightarrow a$

$B\rightarrow a$

$\endgroup$
  • $\begingroup$ WoW ! That's funny ! Thank you :) $\endgroup$ – Arman Malekzadeh May 6 '16 at 7:20
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.