12
$\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$
0
6
$\begingroup$

There do indeed exist ambiguous regular grammars. Take for example

$S\rightarrow A~|~B$

$A\rightarrow a$

$B\rightarrow a$

$\endgroup$
2
  • $\begingroup$ WoW ! That's funny ! Thank you :) $\endgroup$ May 6 '16 at 7:20
  • $\begingroup$ I like this one because it answers quickly to the question. $\endgroup$
    – jlguenego
    Jan 2 at 18:58
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$

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.

$\endgroup$
1
-1
$\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$
3
  • $\begingroup$ It's not logical $\endgroup$
    – Romuald
    Nov 23 '20 at 12:57
  • $\begingroup$ Just because you don't understand what i wrote, does not mean its not logical. Please don't comment nonesense. Thanks. $\endgroup$ May 16 at 3:28
  • $\begingroup$ 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". $\endgroup$
    – Romuald
    May 17 at 7:43

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.