Okay, so very good morning students. We had started with grammar in the last lecture. Just confirm with me if my voice is audible once again.

Yes, sir. Yeah, so in the last lecture we had discussed about grammars. So just we'll quickly revise what is grammar. So grammar is four-tuple as I stated yesterday that it is Vn then Vt then S and P.

So in this what do we mean by Vn? Vn is set of non-terminal symbols. Vn is set of non-terminal symbols.

Okay, set of non-terminal symbols. What are non-terminal symbols? These symbols are usually capital letter symbols.

Okay, then second is we have VT. What is VT? VT is set of terminal symbols.

VT is set of terminal. symbols. So these terminal symbols are nothing but our small case letters or we can also say that these can be our digits 0 to n. Then we have one symbol s which is basically the starting symbol of our grammar. So s is starting symbol of our grammar.

s is denoted as starting symbol of grammar. Usually the starting symbol of grammar is a non-terminal symbol. It is a non-terminal symbol.

And then we have production rules. We have production rules. So P is set of production rule.

P is set of production rules where each of this production rule is of form alpha derives beta. How we read this? We read this as alpha derives beta. Now depending upon the values of alpha and beta, we have four types, right? Depending upon what you have in your alpha and what you have in your beta, we have total four types of grammar.

We have total four types of grammar. What is the first type of grammar? First type of grammar is type 0 grammar.

First is type 0 grammar. So in type 0 grammar what we can have for our alpha and beta? Our alpha and beta both can be any combinations of terminal and non-terminal symbols.

Alpha and beta can be any combinations of terminal and non-terminal symbols. So you can make any possible combinations out of your capital letters and small letters while writing your production rules on both the sides. So, we had discussed few examples like suppose S gives AAB and suppose A gives B.

We can have these kind of production rules. So, you can write anything on the left hand side of your derivation and anything on the right hand side of your derivation. So, this was the first type that we had discussed yesterday.

Then next one is second type. So, second type is called as type grammar second is called as type 1 grammar. So in type 1 grammar what we have alpha and beta here also can be any combination of terminals and non terminals. Alpha and beta can be any combinations of terminals and non terminals apart from that what additional condition we have here that length of alpha should be less than equal to length of beta.

What is the additional condition that we have? Length of alpha should be less than equal to length of beta. So if you observe the left hand side grammar over here, here in the second production rule, alpha is small a capital A and beta is small b.

So here length of alpha is not less than equal to length of beta. So this particular grammar can be called as type 0, but this cannot be called as type 1 grammar. Type 1 grammar.

So I can have some grammar like this. Say for example, S gives suppose AAB, AA gives suppose B capital B, capital B gives suppose small b. So, this example is allowed now because now here if you see for all the three types that are written here, your length of alpha is less than equal to length of beta.

So, it can be called as type 1 grammar. Next is now type 2 grammar. Next is now type.

2 grammar. So what is there in case of type 2 grammar here? Now here alpha compulsory has to be a non-terminal symbol. Alpha compulsory has to be a non-terminal symbol. And what about beta?

Beta can be any combinations of terminal and non-terminal. Beta can be any combination of terminal and non-terminal symbol. So left hand side of your derivation compulsory has to be a non-terminal symbol.

And no doubt length of alpha should be less than equal to length of beta. So, in the left grammar over here if you observe in this second production rule, we have small a capital A gives small b capital. So, in the alpha here you are having any combinations of terminals and non-terminals.

So, this kind of production rule is allowed in type 1, but it is not allowed in type 2 because in type 2 alpha compulsory has to be a non-terminal symbol. It has to be compulsory a non-terminal. So I can give some examples suppose S gives AAB and suppose A gives AA or B. So this kind of production rules we can have.

This what I have written here is OR. What is meaning of this OR? Suppose if I have two production rules A gives AA and again another production rule is A gives B.

So together I am writing that in the form of OR. So if I write these two production rules independently, how they will look? They will look like this. A gives AA and A gives B. If I want to write these two production rules together because both are starting for same non-terminal symbols.

So that I can show here in this form also. Are you getting this? Now we have the last type of grammar that is type.

grammar last type of grammar that is type 3 grammar. So in type 3 grammar what are the restrictions again alpha compulsory has to be a non terminal symbol and now beta can take only two forms either terminal followed by non terminal or it can be only a terminal symbol. So it should suit actually to only of these two forms.

So we can have production rules like this, terminal followed by non-terminal and only terminal. Okay. So in this production rule, if you see in first production rule, we have in beta terminal, then non-terminal and then again terminal. So this is allowed in type two grammar, but it is not allowed in type three grammar.

In type three grammar, we should have terminal followed by non-terminal or only terminal support. Is this understood my dear students? Any doubt in the types of grammar?

No sir. Yes, all the four types of grammar are understood. Grammar is four tuple, VN, VT, S and P.

VN is set of non-terminal symbols, VT is set of terminal symbols, S is starting symbol of grammar which compulsory has to be a non-terminal symbol. Then P is set of production rule where every production rule is of form alpha. derives beta.

Depending upon the values of alpha and beta, we have four types of grammar, type 0, type 1, type 2 and type 3. Type 0 grammar is also called as unrestricted grammar. It is also called as unrestricted grammar or the corresponding language is called as unrestricted language. Then we have subset of it in the form of type 1 grammar which is basically context sensitive grammar and the corresponding language is called as sensitive language.

Then we have type 2 grammar which we call it as context free grammar or the corresponding language as context free language. Within that we have regular grammar or its corresponding language is called as regular language. So this is how the hierarchy looks like. So all regular languages are contextual languages, but all contextual languages are not regular. Same is the case with grammar also.

All regular grammars could be treated as context-free grammars but all context-free grammars cannot be treated as regular grammar and the hierarchy continues for the next entities also like all context-free grammars are context-sensitive grammars but all context-sensitive grammars are not context-free grammars and so on so this diagram shows us the relationship between the four types of grammar and their corresponding four types of languages is it clear students any doubts am i audible yes Yeah, so let us now see some numericals based on grammar. As I told you that most of the content that we have in our curriculum of theory of computation is based on context-free grammar. So whatever grammar will be given for you, you have to write context-free grammar for those languages.

What you have to do? You have to write context-free grammar for those. Okay, you have to write context-free grammar.

We will also have few numericals for regular grammar, but I will tell you when we will be discussing those regular grammar. But as of now, we are discussing problems for context-free grammars. So, let us take the first example today. Let us take the first example for today. Just a moment.

Is the screen visible? Yes, sir. Yes, sir.

So let us take the first example. All of you are advised to open your notebook simultaneously and you have to solve in your notebooks. I may ask you to submit your notebooks.

Okay. So make sure that you are also making note of all these things while the lecture is going on. Okay.

So first example is A raise to N, B raise to N. take down the question where n is greater than equal to 0. a raised to n, b raised to n where n is greater than or equal to 0. So, I had explained you the meaning of this language during pumping lemma session, right? What this language indicates?

It indicates that the number of a's and the number of b's in this string are same. number of a's and number of b's in the string are same. If I have zero a's and zero b's because value of n starts with zero. If I have zero a and zero b's the string that I generated from that language will be null.

No a and no b then the string generated from that language will be null. What will be the next string that gets generated from this language? Value of n will be treated as one.

So if value of n is 1, I have 1a and 1b. So the string generated from that language will be ab. String generated from that language will be ab.

What will be the next string generated? 2 times a and 2 times b. What is the next string generated?

2 times a and 2 times b. Is it understood, my dear students? What will be the next string generated? 3 times a and 3 times b, 3 times a and 3 times b and so on.

Are the strings understood? Value of n is 0, string generated will be null. Value of n is 1, string generated will be ab.

Value of n is 2, string generated will be aabb. Don't write it as a square b square. It indicates how many a's and how many b's are there in your string. So, it is like aabb. Then we have value of n as 3. So, we will have 3 a's and 3 b's and so on.

Followed by we will have 4 a's and 4 b's and so on. Like this thing will be there. So, now my dear students, we have to write grammar for this particular language. What we have to do?

We have to write grammar for this particular language. And what type of grammar we have to write? We have to write context-free grammar. What type of grammar we have to write?

We have to write context-free grammar. So, if you see... there are four tuples in our grammar. What are the four tuples? Vn, Vt, S and P.

Vn non-terminal, Vt terminal, S is the starting symbol and P is the production rule. Now what is the most important tuple in this out of four? The most important tuple out of this four is your P, that is your production rules, right? Because production rules is something which will actually tell you what that grammar is.

From that production rule, you can easily write what are the remaining three tuples. Right. So what we need to actually construct here in this is the production rules. We need to construct these production rules. So how to construct these production rules?

So we can start making use of non-terminal symbols. We can start making use of non-terminal symbols. Now, what are terminal symbols?

I told you terminal symbols. We can link it to our alphabet. We can link it to our alphabet.

So in this particular example, what is our alphabet here? A and B. What is alphabet here?

It is A and B. So our terminal symbol also for this problem will be A and B, small a and small b. And non-terminal symbols, we will start constructing and we will take non-terminal symbol as per our requirement.

Initially, my dear students, if you observe, initially I will take one non-terminal symbol here, that is S, from where my grammar will begin. Initially, I am taking one non-terminal symbol S from where my grammar is beginning. All of it just be attention. This is very important. S is my first non-terminal symbol that I have taken from where my grammar is beginning.

Now, what kind of strings I have? If you closely observe my dear students over here, for every A, I have a corresponding B. For every A, I have a corresponding B. So, if I have this A, I have corresponding B for this over here.

If I have this A... I have a corresponding B for it over here. If I have this A, I have corresponding B for it over here.

Right? Same is applied to this string also. For this A, there is a corresponding B over here.

For this A, there is a corresponding B over here. Are you getting this? Similarly, for this string also. For this A, there is a corresponding B over here. Are you getting this, my dear students?

So, for every A, For every A, I have a corresponding B. For every A, I have a corresponding B. And now this is getting repeated again and again. It is getting repeated again and again. So what I do students, I use the same non-terminal symbol S over here in order to run so called recursion between that non-terminal symbol.

So say for example, I want to generate a spring like AB. Suppose. AB.

So I will apply as use ASB. So I will be done with one A and one B. Are you getting this?

I'll be done with one A and one B. Now suppose I ask you to generate string like three A's and three B's. Suppose I ask you to generate this string.

Three A's and three B's. If I ask you to generate this string. How I can generate this string? So for that first I'll apply ASB.

For that first I will apply A, S, B. Then again for this S, again I will apply A, S, B. With this I will be done with two A's. Then again for this S, I will apply A, S, B. Are you getting this? So I am able to get three A's and three B's. Are you able to understand this?

So, if I want to keep on increasing my number of A's and number of B's, simply I can apply the same production rule again and again to generate all those possible strings. Is it clear? Is it understood students?

How did we use the same non-terminal symbol? Am I audible? Yes, sir. So, we are making use of same non-terminal symbol. S gives ASP.

So if I want to generate a string like AB, I use this S is equal to S gives ASP only once. If I want to generate 2A and 2B kind of string, then I'll apply it two times. Now, my dear students, this should stop somewhere, right?

This should stop. So suppose when we solve the first problem, that was for AB, but still there is this S remaining in between, correct? or the second example I solved was 3a and 3b. Still this s is remaining in between. So for this string what is remaining here in between is null.

Here also what is remaining here in between is null because once I complete 3a's and 3b's what is remaining between over here nothing is remaining means null. So what I do is I'll add or null to this. This is as good as like this s gives ASB and SQ's NULL. These are two different production rules, but we can also write these two production rules in this form.

sqs asb or null sqs asb or null so now my dear students if i directly apply sqs null my first string null gets accepted correct my first string null gets accepted now if i want ab to get accepted what i do i'll first apply sqs asb and then i'll apply sqs null so once i apply sqs null what string i'll get out of this ab you So my AB string is accepted. What will happen to 3A and 3B? First I will apply SQ's ASB.

Then again I will apply SQ's ASB. Again I will apply SQ's ASB. I will get 3As, S and BBB.

Then I will apply SQ's NULL. So once I apply SQ's NULL, I will get final string as 3As and 3Bs. So when I solve this string, I write it in the derivation form. See how. Observe this.

ASP which production rule I use I use production rule SQ's ASP I use the production rule SQ's ASP next time what I do next time I replace it I replace S by ASP so here I write which production rule I am using I am using SQ's ASP next time again I use SQ's ASP so A SB, BB. What production rule I have used? SQs, ASB.

So, in the bracket, I am specifying which production rule I have used. Here, I am specifying which production rule I have used. And this process that I am writing is an example of derivation. This is an example of derivation. This is example of derivation.

Finally, what I am going to do? I'm going to apply sq's null. I'm going to apply sq's null.

So, from this I generate a string that is a a a b b b. I generate a string that is a a a and b b b. Is this understood?

Now, if I ask you to write four tuple for this grammar, what will be four tuple? What is non-terminal symbol? What is non-terminal symbol? It is S.

Only one non-terminal symbol is there, correct? What is terminal symbol of this problem? Terminal symbol for this problem is A and B. Terminal symbol is A and B.

What is starting symbol of our grammar? What is starting symbol of our grammar? It is S, which is belonging to Bn. And what are our production rules?

These are our production rules. These are our production rules. Is the example understood? a raised to n, b raised to n where n is greater than or equal to 0?

Yes, students? Yes, sir. Yes, sir. Yes. So, when you get this type of question for constructing grammar, so what is expected is first you need to work out your production rules.

Correct? you need to work out your production rules. So you will first write L. First you will write the strings for your language.

Once you write the strings, looking at the strings, we need to write the production rules. Once you finalize the production rules, then you will write the remaining three tuples because production rules you have already written, right? So you can write the remaining three tuples that is VN, VT and starting symbol.

Once you write this remaining three tuple, then you have to solve one derivation process. which I am marking here. This is the derivation process.

Is it clear what is expected in the answer? First, you will write strings. After you write the strings, you will try to construct the production rules.

Once you construct the production rules, you will write the remaining three tuples in the form of terminal, non-terminal and starting symbol. And after that, you will show one derivation process. Is it clear? I will just hold on.

this screen for another 2 to 3 minutes, all of you can take down this problem in your notebooks. It is 1155 right now, I will wait for 2 minutes till 1157, you take down this problem in your notebooks. Thank you. done students yes sir yes okay so let us take next example all of you note down the next example Language L is equal to a raise to n, b raise to n where n is greater than equal to 1. a raise to n, b raise to n where n is greater than equal to 1. So, what will be the difference in this?

As n is greater than equal to 1 now. So, n cannot be 0 now and if n is not 0, you will not have a null string in this language. You will not have a null string in the language. So, the first string that will be there in this language will be with the value of n as 1. With the value of n as 1. So, the string generated if the value of n is 1 will be ab.

String generated will be ab. Next string generated will be aabb. Then next string generated will be 3 times a and 3 times b.

then four times a and four times b and so on. Is it understood? So only change here is that you will not have null string will not have null string.

Now when I try to write a grammar, we have seen that if I want to repeat same non terminal, we had written a pattern like this in earlier example, and we repeated with s and then we closed this using or or null. But due to this, what happened is directly you can apply s gives null, directly you can apply s gives null and then null string gets accepted and null string get accepted. But now I don't want null in my language. I don't want null in my language. I don't want null in my language.

So in that case, in that case, this particular thing will not work right. This particular thing will not work right. So see how we write the grammar for this.

So no doubt we require recursion for A and B. No doubt we require recursion for A and B because for every A, I have a corresponding B. For every A, I have a corresponding B.

For every A, I have a corresponding B. Every A corresponding B. Any string that you take. A, you have a B. A, you have a B.

But now what I do here, I use another non-terminator. I use another non-terminal here. Suppose that another non-terminal is capital A.

It is capital A. So what will happen my dear students? When I write production rule like this that S gives A capital A and B. So minimum one A will be applied over here. Minimum one small a and small b will be applied.

Are you getting this? Now I will not apply directly null over here. Rather I will write another production rule here that is A gives A.

A capital A B or null. Now what will happen due to this? Minimum one A and minimum one B will always be applied because I will start from the starting symbol of grammar, right? I'll start from the starting symbol of grammar.

The first production rule that I'll apply will be A capital A B. So minimum one A and one B will be applied. Then suppose I want string like A B. Suppose I want string like A B. Then what will happen? Then I will make this a as null by using production rule a gives null. Are you getting this? Suppose I am processing string a b.

Suppose I am processing string a b. How I will write derivation for this? First I will do s gives a a b. First I will do s gives a a b.

And then I will make a as null using production rule a gives null. Using production rule a gives null. Are you getting this? Suppose if I ask you to process string like a, a, b, b. Suppose I ask you to process string like a, a, b, b.

See how this will be processed now, my dear students. First, I'll apply sqs a, a, b. Correct? Production rule used is sqs a, a, b. Then next time, I want one more a because my string is having two a's and two b's.

So, this second a now I'll get from this a production rule. Correct? this a production rule again has a recursion for a and b once again so that i'll apply over here now so this is a a a b b which production rule we have applied here a gives a a b which production rule we have applied here a gives a a b are you getting this then next which production rule i'll apply can anyone tell me which production rule i should apply next for generating aabb yes anyone yes hello someone has unmuted correct a gives null is we are going to apply what we are going to apply here is a gives Null.

Then only this A will become null now and then your string will be AABB. Your string will be AABB. Are you getting this?

Suppose I give you string like 3 times A, 3 times B. 3 times A, 3 times B. Okay. Then what will be the first production rule that you apply? A gives, S gives, AAB.

First will be as gives aab next will be this a gives aab a A-b then I want three a's so again this a gives aab so this a gives a A-b and then now once I am done with three a's and three b's then I will make this a as null So production rule that I apply here will be a gears null. So what production rules we have used here first time I used sq's aab next time I used a gears aab then next time again I used a gears aab and here I had used a gears null. How are you getting this?

What will be our 4-tuple? What is our Vn? Vn is of this problem is now two symbols are there, capital S and capital A. What is our terminal symbol?

Small a and small b. What is starting symbol of our grammar? Starting symbol of our grammar is capital S, which belongs to capital A. non-terminant and this is our production rules this is our production rules is the example understood my dear students so what sequence you should write first problem then you will write strings then you will write this production rules after you write this production rules then you will write this remaining three tuples after you write these three tuples you will stall one string of your choice like i have solved three here out of which one you can swap Is that example understood? Yes?

Yes, sir. I'll wait for two minutes. You can take down this problem. It is 12.05 here. I'll wait for two minutes.

You can note this down. Lune. Can you repeat that please? You will be getting recording of this lecture, don't worry.

Done? Next question, so next is language of palindromes, language of palindromes where you are dealing with your alphabet for A's and B's. What is palindrome?

We all know palindrome is a string whose reverse is the string itself. Correct? Palindrome is a string whose reverse is the original string itself.

Now here this string is comprising of A and B. String is comprising of A's and B's. So what will be our language strings?

Whether null is a palindrome? Yes, null is a palindrome. Next, whether only A is a palindrome? Yes, only A is also palindrome.

Only B is also palindrome. AA is also palindrome. AB is not a palindrome. Correct? BA is also not a palindrome.

Then BB is palindrome. Correct? Then AAA is palindrome.

ABA is palindrome. BAB is palindrome. BBB is palindrome. Then 4 times A is palindrome. Then ABBA is palindrome.

Then BAAB is palindrome. Then BBBB is palindrome. Did you understand this?

Please mute yourself. Yes. Is this understood? Yes, sir. Are the strings understood which are palindromes?

Yes. Yes. Yes, sir.

Yeah. So now, my dear students, if we closely observe here in these examples, please mute yourself. If we closely observe in these examples for if I have first symbol as a suppose a then I have corresponding a over here. Right. So for every a I have a matching or say, for example, I have B.

Then for every b, I have a b matching. In the earlier example, if you remember, a raised to n, b raised to n. For every a, I was having a b matching. Correct? For every a, I used to have a b matching.

But here, for every a, I have a matching or for every b, I have a b matching. Are you getting this? So here, recursion is something like this. Are you getting this?

Like in A raised to N, B raised to N, I was having for every A, I was having a B. But that cannot be applied here to palindrome because for every A, I have A matching or for every B, I have a B matching kind of situation over here. Are you getting this one, my dear students? Is the first part understood? What do I mean by that?

every A there is a matching A. For every B there is a matching B. So if I try to write production rule for this how I will write? A S A and B S B. Correct? For every A I have a matching A and for every B I have a matching B.

Okay? Now if I want to have strings like suppose uh A, B, B, A. Still I can get that because I'll apply first A, S, A and then I'll apply B, S, B. Correct? Then I'll be able to reach to these kind of strings.

A, B, B, A. So in this recursion, I can use combinations of A and B both also. And already every left hand side A is getting adjusted to a right side A. Because my recursion is like ASA and BSB. So, that continuous pattern will be repeated.

Now, this pattern has to end somewhere, right? This pattern has to end somewhere. Correct? So, for this type of string which I have taken, what string I have taken here?

For example, it is AA. Sorry. It is ABBA.

It is ABBA. What is length of this string? 4. So I can say this is an even length string. It is an even length string. So when my palindrome is of even length, my dear students, you see once I am done with all the four symbol, what remains inside is S.

What remains inside is S. So for this string to become ABBA now, this S should become null. This S should become null.

Correct? So I should also add a production rule that sq is null. Correct. So if now I have sq is null, I can make here like this. I can apply production rule sq is null over here.

Correct. I had applied sq is ASA over here and I had applied sq is BSB over here. And then last symbol that was remaining that was s.

This I have to make it as null. then only a b b a i will get suppose i give you string like b b b b what will happen first i'll apply s gives b s b b s b then again middle s will be b s b so i'm getting s gives b b s b b then that middle s again i'll make it as null like this so i'll get string like b b b b i'll get string like b b b are you getting this Yes. Suppose I have a two length palindrome.

Suppose AA or BB. How it will be handled? Suppose I have palindrome like AA.

So I will apply S gives ASA. So both the As are done. Then this S will be again null. So AA I will get.

Are you getting this? Is this much understood my dear students? can anyone just confirm yes sir am i audible yes sir so my palindrome if it is of even length if my palindrome is of even length even length means two length palindrome or four length or for that matter zero length also zero length palindrome means what null so they are getting accepted by this one so if i want to accept null Directly I'll apply sqs null, null is accepted. Then for aa, I'll do this kind of derivation. sqs asa and then sqs null, aa is accepted.

For bb what I'll do? sqs bsb and then sqs null. So bb will be accepted, right? Then 4 times a can be accepted like this. Then abb I have shown.

Ba, abb can also be accepted in that way. And 4 times b also can be accepted. So this much part works well with even length palindrome.

But now my dear students, we also have few odd length palindromes over here. Like I have only A, correct? Only A, then only B, then I have this three length A, three length B, then ABA and BBB kind of strings also. So consider this particular example.

Suppose I am working string like ABA, ABA. So what will happen? I'll first apply sq's asa so with this this a and this a is done so now this s should be replaced by what in order to get aba yes can anyone tell me this is correct very good this s should be replaced by b correct or another example suppose you have a string like bab suppose you have a string like bab then first i'll use s gives B S B correct first I will use S gives B S B then for getting this B and this B is done using this B and B then this S should be replaced by what in order to get B A B A correct this S should be replaced by A this S should be replaced by A in that case right so when I am having order length palindromes See, when I am having odd length palindromes or for example, I can take a five length palindrome also. Suppose I am having AB, ABA kind of string, five length string, AB, ABA. Then first I will have ASA, correct?

Then I will have, for this A again I will have BSB, correct? Then for this S, now I should be able to get this A, correct? So when I am dealing with odd length palindromes, middle symbol that is remaining is either A or B. So I am adding two more options to this production rule that is either A or B. With this what happens is my only A.

and only B that is one length palindrome also get accepted by my grammar. So my final grammar looks like this. S gives null or ASA or PSB or A or B. Is it understood my dear students? So what will be my VT here?

My VT is A and B. What is my VN? VN is capital S, only one non-terminal.

What is starting symbol of this grammar? It is S which belongs to VN and this is my production rule. This is my production rule and one string you can solve, one odd length and one even length. Is it clear? Example.

Yes? Yes, sir. Yes, it is 12.18. I will wait for another two minutes. You can take down this.

First, write down the language strings. Then, write down the production rules. Then, write down the remaining three tuples.

And then, write one or two derivation. One you can write for even length. Maybe ABBA, which I have written. One you can write for odd length.

Maybe BAB string. Two strings are sufficient for you to shoot. I'll wait for two minutes then we'll start with the next example.

Completed? Yes sir. Shall we move on to the next example?

Yes. Now suppose I gave you an expression suppose suppose it is a plus b cleans ideally this is a regular language right but for regular language also I can write context three grammars because regular all regular languages are contextual basically if you see that circle all the regular languages are contextual languages So even if I give you a regular expression, I will be able to write a context free grammar for it. So let us write grammar for this language.

Let us write grammar for this language. So what is this language? A or A plus B clings.

So we all know what are the strings for this language? Null A B AA AB BA BB 3 times A AAB, ABA, ABB, BAA, BAB, BBA, BBB and so on. Right. So you all know that these strings are there.

So let me write grammar for this now. First of all, I can repeat. A anytime, I can repeat B any number of times, right? I can repeat A any number of times, I can repeat B any number of times and I can have also null in my language. I can also have null in my language.

So suppose if you want string like null, directly you will write as gives null. right if you want string like a if you want string like a first i'll write s gives as and then this s gives null so a will be accepted right suppose i want string like bb sorry b suppose i want string like b first i'll write s gives bs and then this s gives null so string like b will be accepted Then next is suppose string is aa, string is aa, so first I will write s gives as, so 1a is done. Again this s gives as, 2as are done, then s gives null, so aa is accepted.

Are you getting this? Next string is ab, so first I will write as. Then as my string is AB, next time I'll write SQs BS.

Next time I'll write SQs NULL. So string AB is accepted. Suppose I have string like ABB now.

Suppose ABB I am taking 3 length. How it will be SQs AS this A is done. Then SQs BS this B is done. Then again SQs B s this B is also done then s gives null so ABB will be accepted are you getting this Yes? Yes?

Yes, sir. Yeah? So you can take down?

Yes, sir. Yeah, this is my production rule. You can write what is VN, what is VT and what is starting symbol. You can write on your own.

I will wait for one minute. Just take down this one. Thank you.

roll number 67 is neil gopni yes sir did you understand Rule number 18. Yes sir. What is grammar? It is four tuple.

What are the four tuples? VN, VT, S and P. Okay, roll number 24. Nishant, Shivite. Roll number 24. Hello.

Yes, what is VN? VN is state of non-termination. Very good. Roll number 20. Yes sir. Nikita, what is VT?

It is set of terminal symbols. Set of terminal symbols. Okay.

Roll number 51, Apurva. Hello sir. Yeah, what is S?

Starting symbol. Starting symbol of the grammar. Okay. Then roll number 4, Anushka.

Yes, sir. What is P? Sir, it is the set of production nodes. Production rules. It is set of production rules.

Yes, sir. Rule number 43, Madhuri. Rule number 43, Madhuri. roll number 43 are you there roll number 43 roll number 33 kartik Yes, sir. Yeah, what are the four types of grammar?

So, the type 0 grammar, type 1 grammar, type 2 grammar and type 3 grammar. Okay, type 0 grammar is also called as? Sir, unrestricted grammar.

Unrestricted grammar. What is the conditions for alpha and beta? Sir, alpha and beta belongs to Vn union Vt star. Okay, so it can be any combinations of terminals and not terminals.

Very good. Then? roll number 59 aniruddha yes aniruddha what is type 1 grammar no yes what is type 1 grammar yes aniruddha what is type 1 grammar Aniruddha, what is Type 1 Grammar? Do you have a clue? Aniruddha?

Hello, Sir. Yes. What is type 1 grammar? Sir Where is Laksh?

Here Rule no. 29, Rohit Patil Rohit Patil. Rule number 29, Rohit Patil. Yes, what is type 1 grammar?

Sir, type 1 grammar is also called as context sensitive grammar in which alpha beta belongs to Vn union Vt star. Yes, and? And sir, mod alpha is less than equal to mod beta.

Okay. roll number 39 home car power yes sir yes what is type 2 grammar so it is also called context free grammar in which alpha is belong to vn beta belongs to vt in vt union vn uh and mod alpha is less than or equal to mod beta Run over 48, Mudaseer. Yes sir.

What is type 3 grammar? Regular grammar. What are the conditions for regular grammar?

Alpha belongs to non-terminal values and beta belongs to terminal as well as non-terminal. beta is also belonging to only terminal okay very good yes so good students so after that we have seen some numericals today let us continue with few more numericals Next question, L is equal to A or B plus. If you remember students, I had told you plus notation also.

So, plus notation means there is absence of null string. Rest, it will behave like cleans only, right? So what will be the strings in this language?

A, B, AA, AB, BA, BB, 3 times A, AAB, ABA, ABB, BAA, BAB, BBA, BBB and so on. Correct? Only null will be absent. So now in the earlier grammar we had written condition like this AS or BS. For repeating any number of AS I write AS.

For repeating any number of Bs I write BS. But to stop that in earlier example we had written null. Now if we write null over here what will happen?

Null directly I can apply S gives null. and null string will get accepted but i don't want null to be accepted in my language because my language now starts with a my language now starts with a my language now starts with a is it understood students why i cannot write null yes yes sir yeah so now instead of that what we can do is we can terminate it with only a or b we can terminate it with only a or b so if i want my first string to be accepted which is a i can directly apply production rule s gives a i can directly apply production rule s gives a so only a is accepted then if i want to b to get accepted i can directly apply only production rule s gives b so only b is accepted correct then if i want to accept string like aa then what i'll do i'll first apply sqs as first i'll apply sqs as and then i'll apply this sqs a then i'll apply sqs a so i'll get string like a correct suppose i want string like a b suppose i want string like a b so first i'll apply sqs as right then i'll apply sqs So I'll get string like AP. Similarly, suppose I want string like ABA.

Suppose I want string like ABA. So first I'll apply s gives AS. So first I'm working on ABA. So this A will be done. Then s gives BS.

This B will be done. And then this s gives A. So ABA will be accepted.

Did you understand? So instead of writing that null, we are terminating it with a or b then we will be getting grammar for a or b plus is it clear yes students is it clear yes yeah so you can write down the grammar production rule and also mention what is terminal non-terminal and starting symbol so every grammar problem what you need to do first write this language strings after you write this language strings Write down this grammar. After you write down this grammar, write down these three tuples and solve one string of your choice.

I will wait for one minute. You can take down this problem. Then we will see next problem. Thank you.

yes sir yes done okay take down take down next problem language of strings starting with A language of string starting with A language of string starting with A what will be the language elements A, AA, AB, AAA, AAB, ABA, ABB correct and so on Language of string starting with A. All of you just pay attention here, my dear students. Now, string should start with A. String should start with A. After that A, you can get any combination of A and B.

And for writing any combination of A and B, just now I had taught you the logic. How to write any combination of A and B? This is what we had solved, right?

This was for plus. This is any combination of A and B, right? Any combination of a and b is this one.

a s or p s or null. Right. So now we need to solve it for starting with a.

So first my string should start with a. First my string should start with a. So from s when I start first thing should be a.

After that anything can come. That anything is now non-terminal a for me. So.

anything from a or b or null. This we have seen right now, right? What is this?

This is same like the earlier one, this one, correct? a plus b star. This was like s gives as or bs or null. Only thing is now we have written it in another non-terminal format because now s we have already used because s gives aa.

So, now first a will come compulsory. This small a will come. After that what I want?

This capital A. This capital A is nothing but any combination of A's and B's. This capital A is nothing but any combination of A's and B's. So if I want string like suppose AAB.

Suppose I want string like AAB. Suppose I take string AAB. Suppose my string is AAB.

How I do? It is AA. It is AA.

Then this A gives again AA. This A gives again AA. Then this A gives, wait, wait, wait, wait, wait, wait, wait, there is a small mistake here. Wait, this is not B.

This has to be A, same non-terminal. If you see here, it was SQs, AS or BS. So, the name of non-terminal should be same. So, it is a gives aa or ba so this a will be now ba and finally this a will be now null so we'll accept string like a what will be our four double now vd will be ab dn will be S and A, starting symbol is S. Is it clear?

This is our production rules. Yes, is it clear? Am I audible?

Yes. Yeah, just take down this numerical, then we'll see more examples. Hello?

Yes. Sir, can you repeat, please? What did you, what is the doubt?

Can you just specify me the doubt? Yes? Who was that?

Hello? Who was that? Am I audible?

Yes, sir. Yeah. What was the doubt? Yes, what was the doubt? Our string should start with A, correct?

Our string should start with A. So, first I write S gives small a and capital A. Here one small a will be processed compulsory every time. Then what is my capital A?

My capital A is basically any combinations of A's and B's. This grammar we have seen just now in the form of S. in the earlier example. How I write any combination of A's and B's?

That grammar was S gives A S or B S or Null. So here I am writing the same grammar in terms of A. So capital A gives A A or B A or Null.

So this part, this second part, this basically gives me something which is A plus B star. Correct? And this is giving me starting with A. So, totally it is like a into a plus b star, which is nothing but starting with a, the question that is asked. Is it clear?

Yes? Yes, sir. Okay, next problem. Yes, all of you take down language L, a raise to n, b, a raise to n, where n is greater than equal to 1. a raise to n, b, a raise to n, where n is greater than equal to 1. Yes.

What will be my first string in this language? Can anyone tell me? A, B, A. Very good. So when the value of n is 1, string will be A, B, A. What will be your second string in this language?

A, A, B, A, A. Very good. A, A, B, A, A. When my value of n is 2. String will be 2 times a then b then 2 times a then next will be 3 times a b 3 times a and so on. So again here also for every a I am having a corresponding a correct for every I have a corresponding a this is my recursion and it stops with b at the end it stops with b at the end not with a null. right? It stops with B at the end and minimum one A should come because n is greater than equal to one.

So minimum one A should be there in my language. So when minimum one A is there, I process that minimum one A using this AAA. So minimum one A will be processed, correct? If I want more number of A's, again I can apply A capital AA, correct? So if I want only one A, say for example, say for example, my string is ABA.

So what I do is give A, A, A. So this A is done. This A is done. Now with this A, what I would require?

I would require a B. So I give here option of B. I give here option of B. So my string A B is A.

A B A is accepted now. My string A B is accepted. Now suppose I have a string like 2 times A B A A. This is my string. Then what will happen?

First I apply S gives. Sorry. So my first a and this last a is done. Now again I need one more a for this. This a will be replaced by this a a a.

So I'll get two a's and two a's which are required for me. And now this finally middle b I require which I'll get by writing a gives b. This is not even a gives b. See while solving derivation please make sure you write it in proper way.

In bracket you should specify which production rule you are applying like this. Okay, so this is for string ABA. Here I have not mentioned the production rules. I'll erase this.

Mentioning production rules is required. It is must. Is the example understood?

So You can specify what are your terminal, what are your non-terminal, what is your starting symbol and these are your production routes. Take it down. Sir, for ABA, there should be A gives B.

It is there, right? Yes. Correct. This one, right? Yes, sir.

Correct. Very good. Your name?

Rohit Patlu. Done all of you? Yes students done? Yes sir.

Next example. L is equal to a raised to n, d a raised to n. Now n is greater than equal to 0. Write down language scripts. All of you write down language scripts. First string in this language will be?

B. Very good. First string will be B.

Yes. Next? ABA. Very good. Yes.

Just try to write grammar. Anyone would like to share any answer? Anything that is going on in his or her mind? Even if it is wrong, you can share, you can discuss. A or B.

What? S gives? S gives A, S, A or B. Your name? Very good.

Correct. S gives A, S, A or B. Now I don't need another new non-terminals.

In the earlier example, n was greater than or equal to 1. So we had to process that one a compulsory. That's why I took one more non-terminal. And then there I repeated a pattern of repeating a again and finishing it with b.

But now when my n is greater than or equal to 0, I can directly terminate my recursion in the same non-terminal. So only b is getting accepted if I apply s gives b. If I apply s gives b, only b is getting accepted.

If I want string like a, b, a, first I'll apply s gives. ASA then I'll apply as gives B so ABA will be accepted. When I want two times A, B, AA, I'll apply as gives ASA two times, correct? Then I'll apply as gives B.

Is it clear? Write down the production rules. Write down VN, VT, starting symbol and one derivation. Done? Yes, done?

Okay, next problem, all of it, language L is equal to 0 raise to n, 1 raise to, just hold on, 0 raise to n. 1 raised to 2n where n is greater than or equal to 1. 0 raised to n, 1 raised to 2n where n is greater than or equal to 1. My dear students, all of you pay attention. Now here, when I say 2n, it is twice the number of count.

So when the value of n is 1, what it indicates? I need 1, 0. When I have 1, 0, I need 2, 1s. Because for 1, I have power of 2n.

Are you getting this? So what will be the first string that will be accepted from this language? Yes, can anyone tell me? Very good.

0, 1, 1. So, when the value of n is 1, when the value of n is 1, string accepted will be 0, 1, 1. When the value of n is 2, string accepted will be, yes, can anyone tell me? 0, 0, 1, 1, 1. Correct. 2 times 0 and? 0, 0, 4. 4 times 1. Very good. Next will be 3 times 0 and 6 times 1 and so on.

6 times. Twice. Very good, very good.

So, twice the number of 1s we need, correct? Now, and value of n we know is greater than 1. So, we will prefer having two non-terminals. We will prefer having two non-terminals, right?

So, when I write pattern for every 0 now, for every 0, how many 1s I need? I need two 1s. Are you getting this? For every 0, I need two 1s. And recursion I'll do using new non-terminal because minimum one zero should be processed.

If more number of zeros are coming, they will be replaced by this one, 0A11. Or if I want to stop, I can stop it by null. So if you are getting string like 011, how you'll solve this? S gives 0A11, right?

Production rule that you'll use will. is sq0 a11 and then a gives null next will be a gives none next will be a gives none is it understood suppose i take string like zero zero four times one so first i'll apply s gives zero a one one first i apply s gives zero a one one next time i'll apply a gives 0, a, 1, 1. Next time I apply a gives 0, a, 1, 1. Then I'll apply a gives null. Then I'll apply a gives null to get string 0, 0, 4 times 1. Is it understood students?

Yes, sir. So, for every 0, earlier you used to have 1, 1. If I give you problem like 0 raised to n, 1 raised to n where n is greater than equal to 1. So I would have written 0a single 1. But here I have two 1s. That's why it is 0a 2 times 1. Rest logic remains same. This is my production rule. You can write what is your terminal symbol.

It is 0 and 1. Your non-terminal symbols are s and a. The starting symbol of your grammar is s. This belongs to bn.

And these are your production rules. And you can solve one string. You can take down this problem.

I will wait for two minutes. Done? Yes?

Completed? Am I audible? Yes, sir.

Done? Or still you need time to write? We'll wait for one more minute.

mute mute mute mute someone has switched on the mic one more numerical we'll take and then we'll stop okay one last numerical i'll take two hours in online becomes little heavy i can understand i'll take only one problem then we'll stop for today okay take down next problem is zero raise to n one raise to 2n 1 raise to 2n where now n is greater than equal to 0. All of you write down the strings. Null. Very good.

Null. What will be the next string? Null.

After null, what will be the next string? 0111. 0111. Very good. Then 2 times 0, 4 times 1. 4 times 1. Very good. So what can be the grammar? Can anyone tell me?

SQ0S111. oh yes one one one by one okay someone told s0s11 okay what else yes this is one option okay someone else was also telling some capital a Yes, anyone else would like to share answer? Any different answer? Yes?

So this is correct. No doubt this is correct. Okay.

So when I apply s gives null, the string gets accepted. When I want 0, 1, 1, I'll apply this once. Then s gives null. when i want this i'll apply this two times and then s gives none and so on so this is my production rule p accordingly you can write what is your vn vd starting symbol you can solve one string zero zero four times one s gives zero s one one zero s one one and Is it clear students? Yes?

Yes sir. Is it interactive? It is quite challenging to teach mathematics like this. Okay, but I hope you have understood the problems. Yes, whatever we have discussed today.

Yes, students? Yes, sir. It is quite challenging, but is the handwriting visible?

Yes, sir. Yes, sir. Okay.

Is it required that then I teach you on board or something? See I am teaching on computer only. This is another way I can teach. I can focus it on a whiteboard. You can see a whiteboard behind me right now.

But in that case I feel the font size would be proper. Is this method okay? Whether you are able to read the handwriting properly? Yes sir.

Can we continue in the same way from next lecture onwards? Yes, sir. Okay, just hold on for a minute.

Let me download the attendance first.