Regular Grammers

 

Regular Grammar

A Regular Grammar is the most restricted type of grammar in the Chomsky Hierarchy.

It generates exactly the class of regular languages (the same languages accepted by finite automata and described by regular expressions).

Formally, a grammar $G = (V, \Sigma, R, S)$ is regular if all productions in $R$ are of one of the following forms:

1. Right-linear form:

   $$A \rightarrow aB \quad \text{or} \quad A \rightarrow a \quad \text{or} \quad A \rightarrow \varepsilon$$
   

   where $A, B \in V$, $a \in \Sigma$.

2. Left-linear form:

   $$A \rightarrow Ba \quad \text{or} \quad A \rightarrow a \quad \text{or} \quad A \rightarrow \varepsilon$$
   

Note: A grammar must be entirely right-linear or left-linear to be regular. Mixing both may lead to a CFG that is not regular.

---

Intuition

• Regular grammars correspond to finite automata (DFA/NFA).

• Productions represent transitions:

  • $A \rightarrow aB$ means “on reading $a$, go from state $A$ to state $B$.”

  • $A \rightarrow a$ means “on reading $a$, finish (accept).”

  • $A \rightarrow \varepsilon$ means “accept without consuming input.”

So:

• Right-linear → strings “grow” to the right.

• Left-linear → strings “grow” to the left.

---

Examples of Regular Grammars

 Strings ending with ab

Language:

$$L = \{ w \in \{a,b\}^* \ | \ w \text{ ends with } ab \}$$

Right-linear Grammar:

$$S \rightarrow aS \ | \ bS \ | \ aA$$
$$A \rightarrow b$$

Derivation:

• For  aab:
  $S \Rightarrow aS \Rightarrow aaS \Rightarrow aaA \Rightarrow aab$
  

---

Language $a^*$ (zero or more a’s)

$$S \rightarrow aS \ | \ \varepsilon$$

• Generates ε, a, aa, aaa, …

---

Language $(ab)^*$

$$S \rightarrow aA \ | \ \varepsilon$$
$$A \rightarrow bS$$

• Generates ε, ab, abab, ababab, …

---

Left-linear version of $a^*$

$$S \rightarrow Sa \ | \ \varepsilon$$

• Generates ε, a, aa, aaa, …

• This is left-linear instead of right-linear.

---

Relation to Finite Automata

Every regular grammar corresponds to a finite automaton, and vice versa:

• $A \rightarrow aB$↔ transition from state A to state B on input a.

• $A \rightarrow a$ ↔ transition to a final state.

• $A \rightarrow \varepsilon$ ↔ nonterminal A is a final state.

Example:
Grammar:

$$S \rightarrow aS \ | \ bS \ | \ a$$

Generates all strings ending in a.

Equivalent NFA:

• States: {S,F}

• Transitions: S —a→ S, S —b→ S

• Accept: final state F after reading a.

---

Key Properties of Regular Grammars

• Generate only regular languages.

• Strictly less powerful than context-free grammars.

• Ambiguity is usually not an issue, because regular grammars are very restrictive.

• Always convertible to finite automata or regular expressions.