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

string bc has also 2 parse trees. (more than 2)

---

how ?

---

@jayendra how u got more then two parse tree for string "bc"

---

if u r saying like that  1.  P->bPc and put P->epsilon and second one u wid the help of S->PQR by putting P->bPc and Q,R as null . so u are wrong bcz we always start  wid start  symbol  which is S so ur 1 is wrong . correct me if i m wrong

---

Can condition be given as ::

j=i+floor(k/2)

k=floor(j/2)+m

---

@Bikram sir @VS

Please explain how conditions can be derived for part(a)

i+k=j+m ????
where i,j,k,m>=0

---

@ amitpawar

S ->bSe ->bbccddee

or  

S->bSe->bcde [ that smallest string ]

so we can see same number of b , c , d, e is generated. 

power of b,c,d,e are respectively  i,j,k,m .

so  i+k = j+m  

---

 Bikram sir i got i=j=k=m

pls see

---

wrong

according to you "bc" is not accepted

but in grammar it is accepted

---

@set2018

Here following string you can generate from grammar { bc  , cd, de, bc^2d^2e, b^2c^2d^2e^2.....}  So you can not say i=j=k=m bcz it doesn't satisfy given string

---

How does bcde have 2 parse trees ?

can someone give the tree ?

---

@Abhijeet

bc is accepted and it also satisfy the condition.

---

@set2018

Just follow these steps

1. S- > bSe

2. S- > bSe

3.S- > bSe

4.S -> PQR

5. P-> null

6.Q ->cQd

7.Q -> null

8. R- > null

Finally you will get bbbcdeee

which means i=3 , j=1,k=1,m=3 and hence the answer i+k=j+m .

---

If I put

S->bSe

s->bbSee

s->bbPQRee

->bbbPcQRee

->bbbcQRee (put P as epsilon)

now put Q and R also as epsilon

we'll get

S->bbbcee

now here i=3,j=1,k=0,m=2

so neither i+k=j+m

nor i=j=k=m

i think it should be (i,j,k,m)>=0

---

Your example bbbcee is giving i+k=j+m (3+0=1+2)

---

oh yes, sorry; i didn't notice it

---

Why  epsilon is not smallest string?

---

@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$