Considering the following language as an example:

$$\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}$$

This has ambiguous transitions on the string $ba$, but how do we prove in general that a right linear language is ambiguous. Is there an algorithm for this?

  • 2
    $\begingroup$ All right linear languages are regular, so they are all unambiguous. Do you mean to ask how to prove whether a right linear grammar is ambiguous? $\endgroup$ – reinierpost Oct 5 '20 at 15:17

For simplicity, let me assume that the only allowed rules are of the form $A \to aB$ and $A \to \epsilon$. Denote the set of nonterminals by $V$, where $S \in V$ is the starting symbol.

Construct a new right linear grammar with nonterminals $V \times V \times \{0,1\}$. The new grammar will simulate two different production sequences for each word, keeping track whether the two actually differ. The starting symbol is $(S,S,0)$, and the rules are:

  • For every pair of original rules $A \to aB$ and $C \to aD$ we add the rule $(A,C,1) \to a(B,D,1)$. (Possibly some of $A,B,C,D$ are equal.)

  • For every pair of original rules $A \to aB$ and $A \to aC$ such that $B \neq C$ we add the rule $(A,A,0) \to a(B,C,1)$. (Possibly $A=B$ or $A=C$.)

  • For every pair of original rules $A \to \epsilon$ and $B \to \epsilon$ we add the rule $(A,B,1) \to \epsilon$. (Possibly $A=B$.)

A word $w$ has two different derivations in the original grammar iff it can be generated by the new one.

For example, in your sample grammar the word $ba$ has two different derivations, $S \to bA \to baB \to ba$ and $S \to bA \to baD \to ba$, and this is reflected in the following derivation in the new grammar: $$ (S,S,0) \to b(A,A,0) \to ba(B,D,1) \to ba. $$

  • $\begingroup$ Nice, what is the time+space complexity of this algorithm. $\endgroup$ – A. K. Oct 7 '20 at 1:40
  • 1
    $\begingroup$ That’s a nice question for you to ponder. $\endgroup$ – Yuval Filmus Oct 7 '20 at 4:01

A right linear grammar with rules of the form $A\to aB$ and $A\to\varepsilon$ is a finite state automaton in disguise.

Such a linear grammar is ambiguous iff the following holds:

There is a pair of productions $A\to aB$ and $A\to aC$ ($B\neq C$) such that $A$ is reachable from $S$, and the languages derivable from $B$ and $C$ have a string in common.

How do we check whether pairs $B,C$ generate a common string? This can be done by a recursive marking algorithm. We start by marking pairs $(B,C)$ such that $B\to \varepsilon$ and $C\to \varepsilon$ (including $B=C$). Now repeatedly mark pairs $(X,Y)$ for which there are productions $X\to a B$ and $Y\to aC$ with $(B,C)$ marked.

  • $\begingroup$ Yes, this may seem different, but basically this is the same solution as given by Yuval. $\endgroup$ – Hendrik Jan Oct 5 '20 at 16:34

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.