1 votes 1 votes Which of the following is false for derivation tree of CFG- $G (V, T, P, S)$ ? The root is labeled $S$. Every leaf has a label from $V ⋃ T ⋃ \{ λ \}$. A vertex with a child labeled $λ$ can only have it as the rightmost child. $\text{1 & 3}$ $\text{1 & 2}$ $\text{2 & 3}$ $\text{Only 2}$ Theory of Computation theory-of-computation peter-linz peter-linz-edition4 context-free-grammar derivation-tree + – tarun_svbk asked Feb 24, 2018 • edited Mar 5, 2019 by Naveen Kumar 3 tarun_svbk 749 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Arunav Khare commented Feb 24, 2018 reply Follow Share Where is the CFG ... .to me it seems this is half question... 0 votes 0 votes tarun_svbk commented Feb 25, 2018 reply Follow Share Cfg can be any cfg. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes 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. Tarun kushwaha 1 answered Feb 25, 2018 Tarun kushwaha 1 comment Share Follow See all 4 Comments See all 4 4 Comments reply tarun_svbk commented Feb 25, 2018 i edited by tarun_svbk Mar 10, 2018 reply Follow Share The leaf whose value is epsilon cannot have other siblings. Your answer is right but the third argument is wrong. 0 votes 0 votes Sukannya commented Mar 10, 2018 reply Follow Share $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. 1 votes 1 votes tarun_svbk commented Mar 10, 2018 reply Follow Share Please check the derivation trees of the examples you have cited here. 0 votes 0 votes Sukannya commented Mar 10, 2018 reply Follow Share @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 0 votes 0 votes Please log in or register to add a comment.