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 :
-
: finite set of nonterminals (variables)
-
: finite set of terminals (alphabet),
-
: finite set of productions (rewrite rules)
-
: start symbol
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:
-
Left-linear:
Example:
-
,
Note: For some definitions, is allowed only if doesn’t appear on any RHS and .
Type-2: Context-Free Grammars (CFG)
Rule shape: where and
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:
Ambiguity: a CFG is ambiguous if some string has ≥2 parse trees (e.g., ). Disambiguate by stratifying precedence:
Type-1: Context-Sensitive Grammars (CSG)
Rule shape (length nondecreasing): with . (No -productions, except a special case for .)
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:
One standard CSG (intuition: generate markers, then “commute” and translate):
(High-level idea: each new introduces a pair; swap past with , then rewrite into extra symbols, keeping counts equal.)
Type-0: Unrestricted (Phrase-Structure) Grammars
Rule shape: where and contains at least one nonterminal.
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 | , strings ending in 1 |
Type-2 Context-Free | single nonterminal on LHS | Context-free | Pushdown Automaton | , balanced parentheses |
Type-1 Context-Sensitive | nondecreasing length, context-limited | Context-sensitive | Linear-Bounded Automaton | |
Type-0 Unrestricted | none (except LHS has a nonterminal) | Recursively enumerable | Turing Machine | all TM-recognizable languages |
Comments
Post a Comment