Register

Test by Bikram | Theory of Computation | Test 1 | Question: 21

• edited by
566 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$
• edited by
User Avatar

2 Answers

1 votes
1 votes
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
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

6 votes
6 votes
2 answers
1
Bikram asked Nov 26, 2016
1,226 views
Test by Bikram | Theory of Computation | Test 1 | Question: 30
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is: Decidable Undecidable but semi-decidable Not even semi-decidable Indeterminable
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is:DecidableUndecidable but semi-decida...
User Avatar
0 votes
0 votes
1 answer
2
Bikram asked Nov 26, 2016
314 views
Test by Bikram | Theory of Computation | Test 1 | Question: 29
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an: Decidable problem Undecidable problem Cannot ascertain None
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an:Decidable prob...
User Avatar
0 votes
0 votes
1 answer
3
Bikram asked Nov 26, 2016
223 views
Test by Bikram | Theory of Computation | Test 1 | Question: 28
Recursive Enumerable Languages are NOT closed under : Union Intersection Complement Homomorphism
Recursive Enumerable Languages are NOT closed under :UnionIntersectionComplementHomomorphism
User Avatar
0 votes
0 votes
1 answer
4
Bikram asked Nov 26, 2016
219 views
Test by Bikram | Theory of Computation | Test 1 | Question: 27
If $S$ and $T$ are languages over $\Sigma =\{a,b\}$ represented by the regular expressions $(a+b^*)^*$ and $(a+b)^*$ respectively, then which of the following options is CORRECT? $S \subset T$ $T \subset S$ $S = T$ $S \cap T = \emptyset$
If $S$ and $T$ are languages over $\Sigma =\{a,b\}$ represented by the regular expressions $(a+b^*)^*$ and $(a+b)^*$ respectively, then which of the following options is ...
User Avatar
Link Copied!