The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
708 views

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.

asked in Compiler Design by Veteran (59.5k points)
retagged by | 708 views
0
easy but nice

1 Answer

+14 votes
Best answer
  1. $i+k=j+m$
    where $i,j,k,m>=0$
     
  2. $bcde$
answered by Active (3.8k points)
edited by
+1
string bc has also 2 parse trees. (more than 2)
0
how ?
0
@jayendra how u got more then two parse tree for string "bc"
0
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
0
Can condition be given as ::

j=i+floor(k/2)

k=floor(j/2)+m
0
@Bikram sir @VS

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

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

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  

0

 Bikram sir i got i=j=k=m

pls see

0
wrong

according to you "bc" is not accepted

but in grammar it is accepted
0
@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
0
How does bcde have 2 parse trees ?

can someone give the tree ?
0
@Abhijeet

bc is accepted and it also satisfy the condition.
0

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

0
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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,512 questions
46,665 answers
139,709 comments
57,485 users