Grammars in Automata

 

What is a grammar (in automata)?

A grammar is a formal tool  that generates strings of a language by repeatedly applying production rules.

Formal definition
A grammar is a 4-tuple $G=(V,\Sigma,R,S)$:

• $V$: finite set of nonterminals (variables)

• $\Sigma$: finite set of terminals (alphabet), $V\cap\Sigma=\varnothing$

• $R$: finite set of productions (rewrite rules)

• $S\in V$: start symbol

Applying productions creates derivations (leftmost/rightmost), which can be shown by parse trees. The set of all terminal strings derivable from S is the languageL(G).

Why grammars matter:

• They’re the generative counterpart to automata (the recognizers).

• Each grammar class corresponds to a machine model: finite automata, pushdown automata, linear-bounded automata, Turing machines.

---

The Chomsky hierarchy (types of grammars)

Type-3: Regular Grammars (RG)

Rule shape (choose one style consistently):

• Right-linear: $A\to aB \mid a \mid \varepsilon$
  

• Left-linear: $A\to Ba \mid a \mid \varepsilon$
  

Power / Automaton: exactly the regular languages ↔ DFA/NFA ↔ regular expressions.

Use: token patterns (lexical analysis).
Example: $L=(ab)^*$

• $S\to aA \mid \varepsilon$, $A\to bS$
  

Note: For some definitions, $\varepsilon$ is allowed only if $S$ doesn’t appear on any RHS and $\varepsilon\in L$.

---

Type-2: Context-Free Grammars (CFG)

Rule shape: $A\to \alpha$ where $A\in V$ and $\alpha\in(V\cup\Sigma)^*$

 (LHS is a single nonterminal).

Power / Automaton: context-free languages ↔ pushdown automata.
Use: programming-language syntax (nested/recursive structures), parse trees/ASTs.
Normal forms: CNF (Chomsky normal form), GNF (Greibach).
Example: $L=\{a^n b^n\mid n\ge 0\}$

• $S\to aSb \mid \varepsilon$
  

Ambiguity: a CFG is ambiguous if some string has ≥2 parse trees (e.g., $E\to E+E\mid E*E\mid id$). Disambiguate by stratifying precedence:

• $E\to E+T\mid T,\; T\to T*F\mid F,\; F\to (E)\mid id$
  

---

Type-1: Context-Sensitive Grammars (CSG)

Rule shape (length nondecreasing): $\alpha A \beta \to \alpha\,\gamma\,\beta$ with $|\gamma|\ge 1$. (No $\varepsilon$-productions, except a special case for $S$.)

Power / Automaton: context-sensitive languages ↔ linear-bounded automata (LBA).
Use: languages requiring synchronized counts beyond a single stack.
Normal form: Kuroda normal form.
Classic example: $L=\{a^n{b}^n{c}^n\mid n\ge 1\}\; (not\; CFL).$ One standard CSG (intuition: generate markers, then “commute” and translate):

• $S \to aSBC \mid abc$
  

• $CB \to BC$
  

• $aB \to ab,\; bB \to bb,\; bC \to bc,\; cC \to cc$
  

(High-level idea: each new $a$ introduces a $B,C$ pair; swap $C$ past $B$ with $CB\to BC$, then rewrite $B,C$into extra $b,c$ symbols, keeping counts equal.)

---

Type-0: Unrestricted (Phrase-Structure) Grammars

Rule shape: $\alpha \to \beta$ where $\alpha,\beta \in (V\cup\Sigma)^*$ and $\alpha$ contains at least one nonterminal.

Power / Automaton: recursively enumerable languages ↔ Turing machines (most general).

Use: theoretical completeness; not practical for parsing.
Note: Constructions typically simulate a TM; explicit examples are verbose.

---

How grammars relate to automata (at a glance)

Grammar Type	Rule Restriction	Language Class	Equivalent Machine	Example Language
Type-3 Regular	linear (left or right)	Regular	DFA/NFA	$(ab)^*$, strings ending in 1
Type-2 Context-Free	single nonterminal on LHS	Context-free	Pushdown Automaton	$\{a^n b^n\}$, balanced parentheses
Type-1 Context-Sensitive	nondecreasing length, context-limited	Context-sensitive	Linear-Bounded Automaton	$\{a^n b^n c^n\}$
Type-0 Unrestricted	none (except LHS has a nonterminal)	Recursively enumerable	Turing Machine	all TM-recognizable languages