Is a string with the null character the same as the same string without the null character?

Question

Is this { Λ, 1 } the same as this { 1 }?

For instance if you have the following grammar:

S -> 0X|Y1

X -> 1|Λ

Y -> 0|Λ

Will every string created by it be ambiguous?

Answer 1

The set $\{\Lambda,1\}$ has two elements, the empty string and the string $1$; the set $\{1\}$ has only one element, the string $1$. Thus, the two sets are not equal.

Your grammar can generate three different strings, $0,1$, and $01$. The strings $0$ and $1$ have unique derivations,

$$S\Rightarrow 0X\Rightarrow 0$$

and

$$S\Rightarrow Y1\Rightarrow 1\;.$$

The string $01$, however, does have two derivations,

$$S\Rightarrow 0X\Rightarrow 01$$

and

$$S\Rightarrow Y1\Rightarrow 01\;.$$

Both are leftmost derivations, so the grammar is ambiguous. The language $\{0,1,01\}$ itself is not inherently ambiguous, however: you can easily write an unambiguous grammar for it. (Note that ambiguity is not a property of individual strings: it’s a property of grammars and languages.)