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

retagged | 986 views
0
easy but nice
+1

a. following is the more formal way: b. bcde contains two parse tree as shown below: 1. $i+k=j+m$
where $i,j,k,m>=0$

2. $bcde$
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
+3

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

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
+1
Your example bbbcee is giving i+k=j+m (3+0=1+2)
0
oh yes, sorry; i didn't notice it