Skip to content
Home » Regular Grammars

Regular Grammars

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:

SymbolMeaning
VSet of variables/non-terminals
TSet of terminals
PSet of production rules
SStart 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 GrammarContext-Free Grammar
More restrictedMore powerful
Generates Regular LanguagesGenerates Context-Free Languages
Production is generally \(A\rightarrow aB\), \(A\rightarrow a\)Production can be \(A\rightarrow\alpha\)
Equivalent to Finite AutomataEquivalent 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\)