edited by
4,000 views
1 votes
1 votes

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 (i) and (ii) are TRUE.
  2. Only (i) and (iii) are TRUE.
  3. Only (ii) and (iii) are TRUE.
  4. All of (i), (ii) and (iii) are TRUE.
edited by

1 Answer

Best answer
1 votes
1 votes

(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
Answer:

Related questions

0 votes
0 votes
1 answer
1
admin asked May 1, 2019
531 views
Give a context-free grammar that generates the language $A=\{a^{i}b^{j}c^{k}\mid i=j$ $\text{or}$ $ j=k$ $\text{where}$ $ i,j,k\geq 0\}.$ Is your grammar ambiguous$?$ Why...
1 votes
1 votes
2 answers
2