S→x S y | xy | ϵ

i think it will be

T→x S y | xy | ϵ

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.

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,321 answers

198,402 comments

105,158 users