+1 vote
1.1k views
Which of the following statements is/are TRUE ?

(a) The grammar $S \rightarrow SS\ |\ a$  is ambiguous. (Where $S$ is the start symbol)

(b) The grammar $S \rightarrow 0S1\ |\ 01S\ |\ \epsilon$  is ambiguous. (The special symbol $\epsilon$ represents the empty string)  (Where $S$ is the start symbol)

(c) The grammar (Where $S$ is the start symbol)

$S \rightarrow T\ /\ U$

$T \rightarrow x\ S\ y\ |\ xy\ |\ \epsilon$

$U \rightarrow yT$

generates a language consisting of the string $yxxyy$.

$(1)$ Only (a) and (b) are TRUE.

$(2)$ Only (a) and (c) are TRUE.

$(3)$ Only (b) and (c) are TRUE.

$(4)$ All of (a), (b) and (c) are TRUE.

edited | 1.1k views
+1

S→x S y | xy | ϵ

i think it will be

T→x S y | xy | ϵ

0
yes , else only $a,b$ are correct.
0
Yes. Corrected now
0
all are correct. explained below.

+1 vote

(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.

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

by Boss (17.8k points)
selected
0
$(a),(b)$ are true , i agree .but can you tell me regarding $(c)$.How did you derive $T$? Question is incomplete