The Gateway to Computer Science Excellence
+1 vote
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.
in Theory of Computation by Veteran (431k points)
edited by | 1.1k views

S→x S y | xy | ϵ

i think it will be 

T→x S y | xy | ϵ

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

1 Answer

+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$
$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$
$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.

by Boss (17.8k points)
selected by
$(a),(b)$ are true , i agree .but can you tell me regarding $(c)$.How did you derive $T$? Question is incomplete
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,309 answers
105,023 users