1. Definition
A Regular Grammar is a grammar used to generate Regular Languages.
In simple words:
A Regular Grammar is a simple type of grammar in which the rules have a restricted form and can generate only regular languages.
Regular grammars are closely related to Finite Automata.\[ \boxed{\text{Regular Grammar} \equiv \text{Finite Automaton}} \]
2. Types of Regular Grammar
There are mainly two types:
1. Right-Linear Grammar
The non-terminal appears on the right side of the production.
General form:\[ A\rightarrow aB \]
or\[ A\rightarrow a \]
Example:\[ S\rightarrow aA \]\[ A\rightarrow bB \]\[ B\rightarrow b \]
Here, the non-terminal is always at the right end.
2. Left-Linear Grammar
The non-terminal appears on the left side of the production.
General form:\[ A\rightarrow Ba \]
or\[ A\rightarrow a \]
Example:\[ S\rightarrow Aa \]\[ A\rightarrow Bb \]\[ B\rightarrow b \]
Here, the non-terminal is at the left end.
3. Components of Regular Grammar
A grammar is generally represented as:\[ G=(V,T,P,S) \]
Where:
| Symbol | Meaning |
|---|---|
| V | Set of variables/non-terminals |
| T | Set of terminals |
| P | Set of production rules |
| S | Start symbol |
4. Example of Regular Grammar
Consider:\[ G=(V,T,P,S) \]
where:\[ V=\{S,A\} \]\[ T=\{a,b\} \]
Production rules:\[ S\rightarrow aA \]\[ A\rightarrow bA \]\[ A\rightarrow b \]
Derivation
Starting with S:\[ S\Rightarrow aA \]\[ \Rightarrow abA \]\[ \Rightarrow abbA \]\[ \Rightarrow abbb \]
Therefore, strings such as:\[ ab,\ abb,\ abbb,\ abbbb,\ldots \]
can be generated.
The language is:\[ L=\{ab^n\mid n\geq1\} \]
This is a Regular Language.
5. Regular Grammar and Finite Automata
There is an important relationship:
Every regular grammar can be converted into a finite automaton, and every finite automaton can be converted into a regular grammar.
So:\[ \boxed{\text{Regular Grammar} \leftrightarrow \text{Finite Automaton}} \]
This is very important for TOC exams.
6. Regular Grammar vs CFG
| Regular Grammar | Context-Free Grammar |
|---|---|
| More restricted | More powerful |
| Generates Regular Languages | Generates Context-Free Languages |
| Production is generally \(A\rightarrow aB\), \(A\rightarrow a\) | Production can be \(A\rightarrow\alpha\) |
| Equivalent to Finite Automata | Equivalent to Pushdown Automata |
| Cannot handle \(0^n1^n\) | Can handle \(0^n1^n\) |
⭐ Exam Answer — 5–10 Marks
A Regular Grammar is a type of formal grammar used to generate regular languages. Its production rules have a restricted form. A regular grammar can be either right-linear or left-linear.
In a right-linear grammar, productions generally have the form:\[ A\rightarrow aB \]
or\[ A\rightarrow a \]
In a left-linear grammar, productions generally have the form:\[ A\rightarrow Ba \]
or\[ A\rightarrow a \]
A regular grammar is represented as:\[ G=(V,T,P,S) \]
where V is the set of non-terminals, T is the set of terminals, P is the set of production rules and S is the start symbol.
Regular grammars are equivalent to finite automata, and both generate/recognize exactly the regular languages.
🧠 Fast memory trick
Regular Grammar → Restricted rules → Regular Language → Finite Automaton
And remember:
Right Linear: \(A\rightarrow aB\)
Left Linear: \(A\rightarrow Ba\)
