GATE CSE 1997 | Question: 11

Question

Consider the grammar

• $S \rightarrow bSe$
• $S \rightarrow PQR$
• $P \rightarrow bPc$
• $P \rightarrow  \varepsilon$
• $Q \rightarrow cQd$
• $Q \rightarrow  \varepsilon$
• $R \rightarrow dRe$
• $R \rightarrow \varepsilon$

where $S, P, Q, R$ are non-terminal symbols with $S$ being the start symbol; $b, c, d, e$ are terminal symbols and ‘$\varepsilon$’ is the empty string. This grammar generates strings of the form $b^i, c^j, d^k, e^m$ for some $i, j, k, m \geq 0$.

1. What is the condition on the values of $i, j, k, m$?

2. Find the smallest string that has two parse trees.

Comments

Language generated by given grammar is context free.

This was asked in GATE2018-35

---

$S \rightarrow bSe | PQR $

$ P \rightarrow bPc | \epsilon $

$ Q \rightarrow cQd | \epsilon $

$ R \rightarrow dRe | \epsilon $

$ S \rightarrow bSe \rightarrow bbSee \rightarrow b^mSe^m $

$ b^{m}Se^{m} \rightarrow b^{m}PQRe^{m} \rightarrow b^{m}(b^{n}c^{n})(c^{o}d^{o})(d^{p}e^{p})e^{m} $

$ b^{m+n}c^{n+o}d^{o + p}e^{p+m} $

Equating with

$b^{i}c^{j}d^{k}e^{l} $

$i+k = j+l = m+n+o+p $

---

Nice explanation…

Answer 1

1. $i+k=j+m$
   where $i,j,k,m>=0$
    
2. $bcde$

Comments

@meivinay question makes sense. Please help.

---

@meivinay 

epsilon will not have two pares tree.

---

@rajan

Start symbol is S, so two parse tree for "bc" is not possible.

i.e. We cannot start from P directly to derive "bc".

Answer 2

For part B) You can get using bcde

 

Answer 3

A.

Let's see what the grammar is doing.

$S→bSe$ => For every b one e must be there

$S→PQR$ => terminals can come from either P, Q or R.

$P→bPc$ =>  For every b one c  must be there.

$Q→cQd$ =>  For every c one d  must be there.

$R→dRe$ =>  For every d one   must be there.

Summary: $b-e , b-c, d-c, d-e$

So number of b and d equals number of c and e.

We can have strings $ε$, be, cd.

Hence the condition is  $i+k=j+m$
where $i,j,k,m>=0$

B. We should have multiple choice for making the tree so let's try with string which can be reached using production in different ways.

String: bede

Way 1: $S→bSe$

            $S→bPQRe$

            $S→bPcQdRe$

            $S→bcde$ (Using $P→ε$ , $Q→ε$ , $R→ε$)

Way 2:  $S→PQR$

             $S→bPcdRe$ (Using $Q→ε$ )

             $S→bcde$ (Using $P→ε$ , $R→ε$

Answer 4

S generates equal number of b's and e's.

P generates equal number of b's and c's.

Q generates equal number of c's and d's.

R generates equal number of d's and e's.

 

Let's give them arbitrary numbers:

b	e	b	c	c	d	d	e
5	5	19	19	4	4	6	6

 

It gives: $b^{24}, c^{23}, d^{10}, e^{11}$

Try out a few more, you'll get

$i+k=j+m$