Register

GO Classes DPP | GATE CS | Theory of Computation | LMD RMD relation

72 views
0 0 votes

Consider any CFG $G$ and a string $w \in L(G)$. Let $p$ be the number of parse trees for $w$, $\ell$ be the number of leftmost derivations of $w$, and $r$ be the number of rightmost derivations of $w$. Which relation is always true?

  1. $p \le \ell \le r$
     
  2. $p = \ell = r$
     
  3. $p = 1$ for every $w \in L(G)$
     
  4. $\ell + r = p$

1 Answer

0 0 votes

For a fixed CFG and a fixed string $w$, every parse tree corresponds to exactly one leftmost derivation and exactly one rightmost derivation. 

Similarly, each LMD or RMD corresponds to one parse tree. 

Therefore, the number of parse trees, leftmost derivations, and rightmost derivations is always the same.

Answer : B

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CS&DA LA Practi...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

1 1 vote
1 1 answer
88
88 views
GO Classes asked Sep 7
88 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
98
98 views
GO Classes asked Sep 7
98 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...
1 1 vote
1 1 answer
64
64 views
GO Classes asked Sep 7
64 views
GO Classes DPP | GATE CS | Theory of Computation | BNF Rightmost Derivation
Consider the grammar,$$\begin{aligned}P &\to A \mid PA \\A &\to n ::= R \\R &\to S \mid R+S \\S &\to \epsilon \mid E \\E &\to t \mid n \mid tE \mid nE\end{aligned}$$Which...
0 0 votes
1 1 answer
64
64 views
GO Classes asked Sep 7
64 views
GO Classes DPP | GATE CS | Theory of Computation | Leftmost Derivation
Consider the grammar $E \to \text{int} \mid E-E \mid E/E \mid (E)$. Which of the following is a leftmost derivation of $2/(3-4)$?$E \Rightarrow E/E \Rightarrow 2/E \Right...