in the last lecture we have studied about Chomsky normal form and we have also studied how to convert a given CFG to Chomsky normal form so in this lecture we'll be studying about another normal form which is known as the gback normal form we shall see what is this and we will also see how to convert a given context free grammar to gag normal form all right so let's see what is a gback normal form a context fre grammar is in gack normal form if the Productions are in the following forms a gives b or a gives B C1 C2 up till CN where a C1 till CN are non-terminals and B is a terminal symbol so if you have a production of this form where a which is a non-terminal symbol gives B which is a terminal symbol this is in gback normal form or if you have a production of this form where a non-terminal symbol a gives a terminal symbol followed by a set of non-terminal symbols then also it is in gback normal form so if you have Productions of these two forms then they are set to be in gback normal form and if they are not in this form then they are not in gback normal form so now we shall see the steps that we need to follow in order to convert a given CFG to its equivalent gback normal form so here we have the steps that we need in order to convert a given CFG to G gnf so step number one check if the given CFG has unit Productions or null Productions and remove if there are any so you have to first check in the given CFG are there any unit Productions or null Productions if you don't know what are these I request you to watch the previous videos where I have discussed about unit Productions and null Productions and also we have discussed how to remove the unit Productions and null Productions in one of the previous lectures so you can watch that and using that technique you have to remove any unit Productions or null Productions that are present all right so step number two check whether the CFG is already in chsky normal form and convert it to jsky normal form if it is not so you have to check that the given CFG is it already in chsky normal form or not and if you don't know about chsky normal form I advise you to watch the previous lecture with where we have discussed about chsky normal form and we have also discussed the steps that we need to follow in order to convert a given context grammar to chsky normal form so in step two we have to check whether the given CFG is already in chsky normal form and if it is not you have to convert it using the technique that we have discussed in the previous lecture and then step three says change the names of the non-terminal symbols into sum a of I in ascending order of I now what do we mean by this we will see this using an example all right so here we have an example where we have a context fre grammar given and the Productions are of this form s gives C A and also BB B gives small B and also SB C gives a small b and a gives small a so here the capital letters denote the non-terminal symbols and then the small letters they denote the terminal symbols so let us just see step number one we have to check if the there are any unit Productions or null Productions if you see that in these Productions there are no unit Productions or null Productions so step one we don't have to do it and step number two says check whether it is already in chsky normal form so if you remember the rules that we need to follow in order to check whether a given contextual grammar is in chsky normal form and and using that if we see we see that this is already in chsky normal form so step two also is done now step three says change the names of the non terminal symbols into Su a of I in ascending order of I now how do we do this for doing this we see that we have the non-terminal symbols s c a b in these Productions and all this we have to replace it with some a ofi and let's see how we can do this so here we will replace S with A1 and then C with A2 and then a with A3 and B with A4 so this is how we will replace the names of these non-terminal symbols using a of I where I is from 1 to 4 for this particular example now you cannot just randomly give any names to these non-terminal symbols but you have to follow it in ascending order starting from the very first production so it's not that you just see s okay let me call it a of one and then here I have B so let me call it a of2 it's not like that you have to first see the production the first production and you have to follow it in the correct order so here we have S so I call it a of one and then the next one is C I call it a of two a I call it a of three and B I call it a of four and if you come to the next notation it's B we have already Define what is B and the next one is s s also we have already given the name and then C and A also we have already given so we have to replace the variables like this in ascending order now let's see what will be the equivalent production that we get after we replace these non-terminal symbols with these names A1 A2 A3 and A4 so this is what we get A1 gives A2 A3 and A4 A4 so if you see why did we get this s was A1 that is why I wrote here A1 C was A2 that is why it's A2 here and a was A3 that is why it's A3 here and both B were A4 that's why you got A4 A4 here and the rest of the things also when we replace it this is what we get now let's see what is the next step step number four it says alter the rules so that the non- terminals are in ascending order such that if the production is of the form AI gives ajx then I should always be less than J and it should never be greater than or equal to J I should never be greater than or equal to J so what do we mean by this let us look at this product if you are taking this production let's see and try to put it in the form of a i gives ajx so here what is our AI it is A1 and what is our AJ it is A2 and you have to just look at the first variable and the next one that follows it you don't have to worry about the things after that so here your I is one and your J is 2 so our rule says that I should always be less than J it should always be be in ascending order so let us see if it is the case here or not so here I is 1 and J is 2 I is definitely less than J 1 is less than 2 so it is following the rule which is mentioned over here and let us see for the next one A1 gives A4 A4 so we have to just look at A1 and this A4 over here so here I is 1 and J is 4 so 1 is less than four it is also in ascending order so it is following the rule that is mentioned in Step number four so we are fine with this first production and now let us check for the second production here it says A4 gives B so what about this one so when I already told you about the rules of gback normal form in the beginning of this lecture we saw that if a non-terminal symbol directly gives a terminal symbol then that is already in gback normal form so this part is already in gback normal form you don't have to worry so now we have to look at this part so in this part it says A4 gives A1 A4 now let us see if it is following step number four or not so here your I is 4 and J is 1 so here we see that I is greater than J 4 is greater than 1 so we already said in Step number four the rule said that it should never be greater than or equal to J it is not following the rule that is mentioned in Step number four so we need to resolve this portion now let's see how we can resolve it we have to resolve it by replacing the problematic variable with some other values so let's see how we can do that so here let me just write down the rule that is causing the problem it is A4 gives B A1 A4 now if you look at this the problem is caused by this A1 over here so what I will do is I will replace this A1 with some other value now what is that some other value with which I can replace A1 I have to replace it with the value of A1 that is given over here so let us replace it and see if it is going to follow the rule or not so I'll write A4 it gives now this B I will write it as it is and then instead of A1 I will write A2 A3 and A4 A4 so first let me write this one A2 A3 so I'll write A2 A3 and this A4 which is here I have to write it down as it is A4 and also it gives A4 A4 so instead of this A1 I will put A4 A4 A4 A4 and this A4 which was here I will write it down as it is A4 all right so now we have this production now let us see if it is following the rules that was mentioned in step four or not A4 gives B that is fine now A4 gives A2 A3 A4 now let us check here our I is 4 and our J is 2 again we see that I which is 4 is greater than J which is 2 so this is not allowed so it is still not following the rule of Step number four so what I'll do is I will replace the value of A2 because this was the variable that is causing the problem I will replace the value of A2 with some other value in order to make it follow rule number four so what is the value of A2 with which I can replace it A2 gives B now let me try to replace A2 with B so this A4 let me write it A4 it gives B this B as it is and instead of A2 I will write B now B and the rest of the things I'll write as it is A3 A4 and this part also I'll write it as it is A4 A4 A4 now let's see if it is following our rules or not so here we see that A4 gives B okay that is fine and A4 gives B A3 A4 now if you remember the rules of gag normal form if a non-terminal symbol gives a terminal symbol followed by anything then that is in Gag normal form so let me just take you up there once so if you see here a CFG is in gback normal form if it is giving a terminal symbol directly or if it gives a terminal symbol followed by any other variables then also it is in gback normal form so we see that this part is in gback normal form now B and B A3 A4 are already in gback normal form now we have to check this part it says A4 gives A4 A4 A4 here our I is 4 and J is is also four so here we are getting a condition a situation where I is equal to J so that is also not allowed in step four it says it should never be I is greater than or equal to J so here we are getting a condition where I and J are equal so when we get this what we have to do when we get this kind of condition this kind of condition is known as left recursion so our step number five is to remove the left recursion so there are certain steps that we need to follow in order to remove left recursions and that we will be discussing in the next lecture so I hope this was clear to you so you have to follow steps number 1 to 4 in order to convert a given CFG to its equivalent gback normal form and now it is not complete because we have encountered a left recursion over here and in the next lecture we will be discussing how to remove the left recursion and after removing the left recursion what we get will be the CFG that is completely converted to its equivalent gback normal form so thank you for watching this and see you in the next one where we will be discussing about removal of left [Applause] [Music] recursions