Could someone tell why "G1 and G3 are ambiguous" and how to see whether a string has at least two different left-most derivations in general?



Although the problem of detecting whether a grammar is ambiguous is, in general, undecidable, for toy grammars like this it is usually pretty easy to find ambiguities by simply enumerating the possible (left-most) derivations until you derive the same sentence in two ways.

For example, $G_1$ has just three productions $S\to a S b \mid S b \mid c$, and none of them has more than one non-terminal on the right hand side. So there are only four derivations of three steps, and it's easy to see that two produce the same sentence.

$$\begin{align}S&\to a S b \to a a S b b \to a a c b b \; (P_1, P_1, P_3)\\ S&\to a S b \to a S b b \to a c b b\; (P_1, P_2, P_3) \\ S&\to S b \to a S b b \to a c b b\; (P_2, P_1, P_3) \\ S&\to S b \to S b b \to c b b\; (P_2, P_2, P_3)\\ \end{align} $$

$G_3$ does have a production which produces two non-terminals, so there are a lot more short derivations. Even so, it shouldn't take you very long to find two derivations for the same sentence.

Proving that a grammar is not ambiguous is not so easy. One possibility is to create a conflict-free parsing table, using any standard algorithm. Not all unambiguous grammars are deterministic (and fewer are deterministic with a single lookahead) but if you do manage to find a conflict-free parser, then the grammar was definitely unambiguous.


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.