wikiacademia

site

Complexity and the Chomsky Hierarchy

The Chomsky Hierarchy
The four levels of Chomsky's classic hierarchy, focusing on the associated machines but with descriptions of the grammars involved, and sample machines in Perl.
Information and Control
A short summary of the 1956 paper by Chomsky where he introduces the hierarchy, proves basic theorems about the four language classes, and introduces some of the machine correspondences.
Extended Hierarchy
Two complexity classes that are not part of Chomsky's hierarchy.
Stuff for Ambrose's tutorial
http://cs.marlboro.edu/ courses/ fall2006/ tutorials/ chomsky_hierarchy/ home
last modified Friday December 8 2006 1:40 am EST