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 a^{n}b^{n}c^{n} 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, ksymbol
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