Partial Derivation Tree


Derivation of Parse Tree:


First we explain parse tree or derivation tree. In the parse tree or derivation tree Root node is always starting symbol and leave node is always terminals and λ. And internal vertex (node) A, B is variable. 



When we traverse top – bottom and left to right then we got yields which is a string belongs to language. 


ω = aaλbλ where ω ∊ L(G) = aab


Partial Derivation Tree (PDT):


In partial derivation tree it is not necessary that the yields is always a string, it may be a sentential form also. And another thing it is not necessary that the root node is always start symbol i.e. it is not necessary to start it always with string symbol.



Any intermediate state of derivation tree or parse tree is partial derivation tree.


So, Derivation Tree → Partial Derivation Tree and equivalently we can say,