in this lecture we will be studying about derivation tree a derivation tree or parse tree is an ordered a rooted tree data graphically represents the semantic information of strings derived from a context-free grammar so we have already studied about context-free grammar and we have an idea about context-free grammars and this derivation tree is actually a order rooted tree that shows the graphical representation of how strings can be generated from a context-free grammar so it is also known as a parse tree and now we will see an example to understand how this derivation tree is formed
and what are the things that we need to know about the derivation tree okay so here we have an example grammar given the grammar is given like this G equal to VT P and s so these are the four types of the grammar where B is the variables or non-terminal symbols T is the terminal symbols piece set of production rules and s is the start symbol and then the production rule is like this s gives 0 B a gives one a a and can also give epsilon or the empty symbol and B gives 0 a
a so here s is the start symbol the variables are B and a and then the terminal symbols are 0 and 1 and then for this given grammar here this is the derivation tree that is formed so this is how we form the derivation tree for this grammar ok so before we go into that let us know the main things that we need to know about a derivation tree the first one is the root vertex the root vertex must be labeled by the start symbol so the root vertex is the first vertex of the derivation
tree this one so it should be labeled by the start symbol here our start symbol is s the road vertex is labeled by s and then the next one is the vertex they are labeled by the non terminal symbols so the other nodes this one the vertex this are labeled by the non terminal symbols or the variables which are a and B so wherever you are seeing this a and B these are the vertex and then we have the leaves are labeled by the terminal symbols or by epsilon so the leaves are the ending nodes
or the ending vertices like for example here we see that this vertex it's a ending vertex means this vertex does not have any more children so those vertices which does not have any children they are known as the leads so the leaves are labeled by terminal symbols or by epsilon so we see that here this is labeled by zero this is levelled by zero which is labeled by one and this we are labeled by Epsilon so this is how we label the different vertices in a derivation tree okay now let's see how this derivation trees
form for this grammar so first we start with the start symbol which is s and we see that s gives 0 and B so we see that s gives 0 and B these two vertices becomes the children of the root vertex s and then we have B over here and from B let's see what are the production that we have we can give 0 a 8 so B gives 0 a and a ok and then this is a terminating symbol or terminal symbol so you can leave it as it is and then we have two
variables a a and we see that a gives one a a so this a I will say that it gives one a a so these are the three children of the vertex a over here and also we see that a gives Epsilon so here I will just write that this a gives Epsilon and then now we are left with two s here again and since we want to end the derivation tree we will say that a gives Epsilon because we see that a can give epsilon here so this is how you form the derivation tree
for a given grammar okay and then there are two types of derivation tree that we need to know that is the left derivation tree and the right derivation tree now we will see what are the left and right irrigation trees and we will try to see some examples to understand them so here we have left derivation tree and right derivation tree these are two types of derivation trees and a left derivation tree is obtained by applying production to the left most valuable in each step okay and a right derivation tree is obtained by applying production
to the rightmost variable in each step so this will become clear when we take an example so it actually means that whenever we are forming a derivation tree if we apply the production to the left most valuable in each step and then we move ahead those are known as left the revision trees whereas in right derivation tree we will apply the production to the rightmost variables so this will become clear when we take this example so here we have an example which says for generating the string a a B a a from the grammar s
gives a a s and also a SS and also epsilon and a gives SBA and also V a so we have a grammar given here this is a production of this grammar and then we want to generate the string a a B a a from this grammar so let us see how can we make the derivation tree for this so first let us make the left elevation tree for this and then after that we will make the right derivation tree okay so we start with the starting symbol which will be the root vertex so s
is my start symbol which is a root vertex and then as you proceed let's see s can give the production's a a s and also a SS and also Epsilon so I distinct that I want to get is a a B a a so in order to get a I will choose the production a s s from here because I am NOT choosing this one because if I choose this connection I am getting a capital A over here and from capital A it is difficult to get a a again in the next step I want
to get a when in the next step that is why I am choosing this one so here I will choose this one and so what will be the children that I will get for this root vertex they will be a s and yes okay so I get this now this is a terminal symbol so I can leave it as it is and I have two variables over here s and s now this is a left derivation tree and I have two variables over here from which I can choose and now since this is the left
derivation tree I should always choose the left most variable so which is a leftmost variable it is this one this is to the left of this one this is the leftmost so I will choose this s and let me see what production should I choose I need to get the next symbol as a and for that what is the production of s that I will take I'll choose the production s gives a a s and why I am choosing this is because if I choose this I will get a and then in the next step
I need to get B and since I have a capital letter A over here we see that capital letter A can later give a B so that is why I am choosing this one so this is will give a a and s okay so this is what I get okay now I am in this step and again I have to choose the leftmost variable and which is the leftmost valuable it is a over here now I have a and then what is the next symbol I want this B small letter B so I already got
a a and I need be now from a if I want to get B what is the production that I can use a gives V a so I will choose this one so this a will give B and a so I get this one now I am done with this one and there are no more variables in this step so I go back to the previous step okay so I go back to the previous step and here that I see that I have a s which is my variable and I already got a a B
a now what I need is just one more a so for that what I will do is I will choose a production s gives a s s that is because I will get a from here and I'll have two s remaining but I can replace those s with empty symbols epsilon so this s will give me a s and s okay this is an a ok now we are done with this and now I've already got the string that I needed a a B a a this one and now I am still having some variables
and I need to complete them I cannot just leave them like this I will again start with the leftmost which is this one s and what should i do I don't need any more simple so I see that s can give the production epsilon which is empty symbols so and we said this gives the empty symbol and I come to this one which is a nexus also will give the empty symbol and I come to the previous level everything is done and if I come to this level I see there is one s remaining this
also will give Epsilon so now we get the string that we needed a a B a a so a a B a we obtain this using the left derivation tree okay now let us do the same thing using the right derivation tree so for that again I will start with the start symbol which is s and I will choose s gives a SSS like in the previous step a s s ok now since this is the right derivation tree I have to choose the right most variable in each step so here I have two variables
and which is the rightmost one it is this one so now I have to start from here and not from this one like we did here so I will start from the rightmost I have an S and from s what will I choose I need I need to get this string so just like we did here I will choose s gives a a s this one so s gives a a and s okay so I already have two s here and now I have to again fill up this using the rightmost variable which is this
s from this s I will again choose this production a SS a s s the production ratios are almost same like the previous example okay now I already got a a and let's say we got this K now I need B a so in order to get ba I have to choose the production which will give me B a that is a gives B a so what I will do is I cannot directly go here so I have to complete this so how would I complete this I don't want any more productions from this s
so sorry from the rightmost I will give the epsilon symbol to this s okay and now I come up to this level and I have an A and I 1b SOA gives be a it gives B and a okay and then this is done and if I come here I see that that is one s remaining for this also I will give the epsilon symbol now we see that we got the sequence or string a a d a.a a.a b a a so this is how you do it using the right derivation tree [Applause] [Music]
