ITEC 420 - Chomsky's Hierarchy and Linear
Bounded Automata
Chomsky's Hierarchy
- RL < CFL < CSL < TDL < TRL < All Langs.
- Relation of languages, machines, grammars:
| Language Class |
Regular |
Context Free |
Context Sensitive |
Turing Decidable |
Turing Recognizable |
All |
| Acceptor |
DFA=NFA |
NPDA |
LBA |
TM (Decider) |
TM (Recognizer) |
??? |
| Grammar |
Regular |
Context Free |
Context Sensitive |
|
Unrestricted |
|
Grammar Categories
- Regular Grammar: has productions of the form A → a | aB (or Ba)
- Context Sensitive Grammar:
- has productions of the form α → β
- where α has at least one nonterm and |α| ≤ |β| (ie no shrinking),
- except for possibly S → ε
- A CSG can generate anbncn using
productions like CB → BC to swap the order of B's and C's
- Unrestricted Grammar: has productions of the form α → β where
α is any string with nonterms and β is any string
Grammars and (Programming/Natural) Languages
- Programming languages have CF grammars.
- Languages accepted by DPDAs are equivalent to those generated
by LR(k) grammars (Leftmost parse, Rightmost derivation, k-symbol
lookahead)
- English is thought to have a CS grammar (except for poetry!).
FYI: Linear Bounded Automata (LBA)
- FYI: A Linear Bounded Automata (LBA) is a TM that is restricted so that
the tape head must remain over the input string. [In some other texts, the tape
length is restricted to (ie bounded) a linear function of the input length.]
- LBA recognize Context Sensitive Languages which are recognized by CS
grammars. This a class of languages is between CF and Turing Decidable
Languages