Register

Parse tree

1,238 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
77
77 views
GO Classes asked Sep 7
77 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
87
87 views
GO Classes asked Sep 7
87 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,293 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,230 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...