Peter Linz Edition 4 Derivation Trees Definition 5.3 (Page No. 130)

Question

Which of the following is false for derivation tree of CFG-  $G (V, T, P, S)$ ?

1. The root is labeled $S$.
2. Every leaf has a label from $V ⋃ T ⋃ \{ λ \}$.
3. A vertex with a child labeled $λ$ can only have it as the rightmost child.

• A. $\text{1 & 3}$
• B. $\text{1 & 2}$
• C. $\text{2 & 3}$
• D. $\text{Only 2}$

Comments

Where is the CFG ... .to me it seems this is half question...

---

Cfg can be any cfg.

Answer 1

Ans--C        ....    considering derivation tree for string in Language.

1) starting symbol will be root True.

2)Leaf node will contain symbol from {T} U {epsilon}, so False

3) epsilon can be anywhere, so False.

Comments

The leaf whose value is epsilon cannot have other siblings. Your answer is right but the third argument is wrong.

---

$S->Sa|\lambda\implies S\rightarrow Sa\rightarrow\lambda a\rightarrow a$[Here $\lambda$ is to the left]

$S->aS|\lambda\implies S\rightarrow aS\rightarrow a \lambda \rightarrow a$[Here $\lambda$ is to the right]

Both are valid CFGs.

---

Please check the derivation trees of the examples you have cited here.

---

@tarun_svbk I understood your point in the previous comment and I agree but the statement given is if a vertex has a child labelled $\lambda$, then it has to be on the right which is wrong by virtue of the counter examples I gave above but what you were saying is not what the statement says, the statement talks about the vertex which has leaf labelled $\lambda$ not about the leaf, $\lambda$. I think the argument should be what I said for the 3rd statement