S→x S y | xy | ϵ

i think it will be

T→x S y | xy | ϵ

1 vote

Which of the following statements is/are TRUE?

- The grammar $S \rightarrow SS \mid a$ is ambiguous. (Where $S$ is the start symbol)
- The grammar $S \rightarrow 0S1 \mid 01S \mid \epsilon$ is ambiguous. (The special symbol $\epsilon$ represents the empty string) (Where $S$ is the start symbol)
- The grammar (Where $S$ is the start symbol)
S -> T/U$ T -> x S y | xy | ϵ U -> yT

generates a language consisting of the string $yxxyy$.

- Only (a) and (b) are TRUE.
- Only (a) and (c) are TRUE.
- Only (b) and (c) are TRUE.
- All of (a), (b) and (c) are TRUE.

1 vote

Best answer

(a) $S \rightarrow SS\ |\ a$

This grammar is ambiguous. Take the string $aaa$ for example. To generate this string we can either have:

$S \rightarrow SS \rightarrow Sa \rightarrow SSa \rightarrow Saa \rightarrow aaa$

or

$S \rightarrow SS \rightarrow aS \rightarrow aSS \rightarrow aaS \rightarrow aaa$.

(b) $S \rightarrow 0S1\ |\ 01S\ |\ \epsilon$

This grammar is also ambiguous. The string $01$ have two different derivation trees.

$S \rightarrow 0S1 \rightarrow 01$

and

$S \rightarrow 01S \rightarrow 01$

(c) This statement is TRUE. Here's how we can generate the string $yxxyy$ from the given grammar :-

$S \rightarrow U \rightarrow yT \rightarrow yxSy \rightarrow yxTy \rightarrow yxxyy$

So all the three statements are TRUE.

Hence answer is **(4)**.

P.S. I have not shown the derivation trees, but you can get the idea from the derivations.