Now let us see about regular grammar and its types. So before discussing about regular grammar, let's see what is a grammar. A grammar is represented by using g with the help of four tuples v comma t comma p comma s. So we use just totally four tuples.
The first one is v, second one is t, third one is p, fourth one is s. So first let's see what is v. So V means set of variables. Set of variables or this can also be called as non-terminals.
Non-terminals. So non-terminals are represented by uppercase letters, capital letters. Second one is T.
T means set of terminals, set of terminal symbols. So terminal symbols means Terminal symbols are represented by lowercase letters, digits and symbols also. Plus, minus, question mark, epsilon, likewise. Next one is P.
So P means set of production rules. Set of production rules. So every production rule is in the form alpha implies beta.
So alpha means left hand side production. Beta means right hand side production. And the last one is S. S means the start symbol. S means the start symbol.
Start symbol is always a variable, a non-terminal. The first production left hand side symbol is a start symbol. Let the first production is A implies CA. So A will become the start symbol.
So this is about what is a grammar. Now let us see about types of regular grammar. Regular grammar is mainly classified into two types.
The first one is left linear regular grammar or this can also be called as left linear grammar. The second one is right linear regular grammar. This can also be called as right linear grammar.
So first let's see about what is left linear grammar. So we can say that in left linear grammar the production is in the form A implies A implies B alpha. So, left linear grammar means in the right hand side, okay, the leftmost symbol is always a non-terminal.
The leftmost symbol is always a non-terminal. Here A and B, capital A and capital B are non-terminals, variables. Whereas alpha means terminal symbol.
Alpha means terminal. It may be lowercase letter or We know what is a terminal. It may be lowercase letter or digit or symbol.
Symbol means epsilon is also a symbol. So, this is a left linear grammar. So, in left linear grammar, in the right hand side, the left most non-terminal is always a non-terminal. Now, let us see what is right linear grammar or right linear regular grammar. In right linear regular grammar, The production is in the form A implies alpha B.
So, here A and B are non-terminals, whereas alpha is a terminal. It may be a symbol. Terminal symbol means it is a lowercase letter or digit or symbol.
Here, right linear grammar means in the right hand side, the rightmost The rightmost symbol is always a non-terminal or a variable. So, this is the difference between left linear and right linear. Left linear means the leftmost one is always a non-terminal, whereas right linear grammar means here the rightmost is always a non-terminal. In the next video, we will see about how to construct a left linear grammar as well as how to construct a right linear grammar, ok.
That means how to convert right linear grammar to left linear grammar as well as left linear to right linear