search
Log In
1 vote
2.2k views

Which of the following statements is/are TRUE?

  1. The grammar $S \rightarrow SS \mid a$  is ambiguous. (Where $S$ is the start symbol)
  2. 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)
  3. 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$.
  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
edited by
2.2k 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 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$
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.


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

Related questions

0 votes
1 answer
1
0 votes
0 answers
2
553 views
Which of the following statements is/are TRUE ? (i) The grammar S → SS | a is ambiguous (where S is the start symbol). (ii) The grammar S → 0S1 | 01S | e is ambiguous (the special symbol e represents the empty string and S is the start symbol). (iii) The grammar (where S is the ... (iii) are TRUE (D) All of (i), (ii) and (iii) are TRUE Sure shot (i) and (ii) are true i want third one in brief
asked Jun 19, 2018 in Compiler Design Nikhil Patil 553 views
0 votes
2 answers
3
101 views
Which of the following grammars is(are) ambiguous? $s \rightarrow ss \mid asb \mid bsa \mid \lambda$ $s \rightarrow asbs \mid bsas \mid \lambda$ $s \rightarrow aAB \\ A \rightarrow bBb \\ B \rightarrow A \mid \lambda \text{ where } \lambda \text{ denotes empty string}$ Choose the correct answer from the options given below: $(a)$ and $(c)$ only $(b)$ only $(b)$ and $(c)$ only $(a)$ and $(b)$ only
asked Nov 20, 2020 in Theory of Computation jothee 101 views
...