# How to we prove if a right linear language is ambiguous?

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?

• 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? – 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.$$

• Nice, what is the time+space complexity of this algorithm. – A. K. Oct 7 '20 at 1:40
• That’s a nice question for you to ponder. – 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.

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