Register

Parse tree

1,263 views
0 0 votes

In any CNF grammar G, how many nodes will all parse trees for terminal string of length n>0 generated by G have?

a) 2n-1

b) 3n-1

c) 2n+1

d) 3n+1

1 Answer

Voting & Accepting an answer helps improve the community
← Previous · Data Structure (obje...Next → · Find Regular
← Previous in category · Data Structure (obje...Next in category → · Find Regular
Position:
Show:

Related questions

1 1 vote
1 1 answer
106
106 views
GO Classes asked Sep 7
106 views
GO Classes DPP | GATE CS | Theory of Computation | Parse Tree Count
Consider the grammar $E \to E-E \mid \text{int}$. For the string $5-3-2$, which statements are correct?The string has two distinct parse trees. The string has exactly one...
1 1 vote
1 1 answer
115
115 views
GO Classes asked Sep 7
115 views
GO Classes DPP | GATE CS | Theory of Computation | Parse Tree Yield
Using the palindrome grammar $S \to 0S0 \mid 1S1 \mid 0 \mid 1 \mid \epsilon$, which derivation generates the string $010010$?$S \Rightarrow 0S0 \Rightarrow 01S10 \Righta...
0 0 votes
2 2 answers
2.3k
2.3k views
atulcse asked Jan 21, 2022
2,329 views
parse tree - context-free grammars - TOC
Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees?
1 1 vote
0 0 answers
1.2k
1.2k views
ahmed65956 asked Sep 27, 2023
1,236 views
10. Give the translation scheme that converts infix to postfix form for the following grammar. Also generate the annotated parse tree for input string 2+6+1 E-> E+T E->T T->0|1|2|3|4|5|6|7|8|9
Give the translation scheme that converts infix to postfix form for the following grammar. Also generate the annotated parse tree for input string 2+6+1E- E+TE->TT->0|1|2...