Proving a CFG is ambiguous?

Question

I have a CFG:

S --> 0S1S | 1S0S | ε

I'm trying to prove that it is ambiguous, but the steps to proving so are confusing me.

So if I pick a string, let's say 010110, I just have to show that there are two different parse trees for the string?

Answer 1

Proving inherent ambiguity of a language is difficult, but proving ambiguity of a grammar is relatively quite easy.

The definition of ambiguity of a grammar does not say that every string has to have different parse trees. It says there need to exist only one string which has different parse tree to make a grammar ambiguous.

The trick to achieve two different parse tree for an ambiguous grammar is to look for a string where you can apply two different rules for the same string or the same rule in two different ways. Since one rule derives $0S1S$ and the other rule derive $1S0S$ you cannot have both rules deriving same strings, so you have to look for a rule that can be applied in two different ways. There you are in luck. Both rules can be applied in different ways.

Take first rule for example: $S \rightarrow 0S1S$. Can you have a string starting with 0 but matches 1 at two (or multiple) different places? It turns out you can $\underline 0$-$10$-$\underline 1$-$\epsilon$ and $\underline 0$-$\epsilon$-$\underline 1$-$01$ i.e. string $0101$. $0101$ and $1010$ are the smallest length strings of the grammar which will have different parse trees.

String $010110$ also has two parse trees $\underline 0$-$\epsilon$-$\underline 1$-$0110$ and $\underline 0$-$10$-$\underline 1$-$10$.

Answer 2

You have to find a string which has two different parse trees. That string might be 010110 or it might be something totally different. In this kind of situation my recommendation is to refer back to the definition in your textbook and work out what the definition is saying.