in Theory of Computation edited by
328 views
4 votes
4 votes

Consider the following grammar: $G$ $E \rightarrow E+E \mid E-E \mid E^*E \mid (E)\mid \text{id}$

The number of derivation trees for the string $\text{id} +\text{id} ^* \text{id} – \text{id}$ is:

  1. $5$
  2. $6$      
  3. $7$    
  4. $8$
in Theory of Computation edited by
by
328 views

4 Comments

how 5? because i m getting only 4
–2
–2

@Bikram sir, I am getting 6. . . please check .. which one is redundant. 

E--> E+E | E-E |E*E| (E)|id

id+id*id-id

1. E -> E+E

    E -> E + E * E

    E -> E + E * E - E

       -> id + id * id - id

2. E -> E+E

    E -> E + E - E

    E -> E + E * E - E

       -> id + id * id - id

3. E -> E*E

    E -> E + E * E

    E -> E + E * E - E

       -> id + id * id - id

4. E -> E*E

    E -> E * E - E

    E -> E + E * E - E

       -> id + id * id - id

5. E -> E - E

    E -> E * E - E

    E -> E + E * E - E

       -> id + id * id - id

6. E -> E-E

    E -> E + E - E

    E -> E + E * E - E

       -> id + id * id - id

0
0
i think 3rd one with 1st
0
0
edited by
ohhh.. got it.. actually, it is 3 and 4 ... each has same derivation tree.

Ans 5 is correct.

Thanks ..: )
2
2

2 Answers

4 votes
4 votes
Best answer

Here is the solution by setting all possible associativity

selected by

1 comment

Really helpful, thank you!
0
0
1 vote
1 vote
E--> E+E | E-E |E*E| (E)|id

id+id*id-id

1. E -> E+E

    E -> E + E * E

    E -> E + E * E - E

       -> id + id * id - id

2. E -> E+E

    E -> E + E - E

    E -> E + E * E - E

       -> id + id * id - id

3. E -> E*E

    E -> E + E * E

    E -> E + E * E - E

       -> id + id * id - id

    

4. E -> E - E

    E -> E * E - E

    E -> E + E * E - E

       -> id + id * id - id

5. E -> E-E

    E -> E + E - E

    E -> E + E * E - E

       -> id + id * id - id
Answer:

Related questions