retagged by
6,417 views
25 votes
25 votes

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 by

4 Answers

Best answer
21 votes
21 votes
  1. $i+k=j+m$
    where $i,j,k,m>=0$
     
  2. $bcde$
edited by
4 votes
4 votes
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→ε$
1 votes
1 votes

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$

Related questions

22 votes
22 votes
2 answers
1
24 votes
24 votes
1 answer
4
Kathleen asked Sep 29, 2014
14,257 views
Construct a finite state machine with minimum number of states, accepting all strings over $(a,b)$ such that the number of $a$'s is divisible by two and the number of $b$...