Chomsky's Language Hierarchy

• Who has heard of Noam Chomsky?
• One of the first things he did as a Linquist was come up with the hierarchy of languages.
• That's formal languages.
• He uses rewrite rules (e.g. A -> Aa and A-> b).
• Regular grammars have one non terminal on left, and at most one terminal ane one non-terminal on the right.
• Context free grammars can have more than one terminal on right
• Context sensitive grammars can have more one non-terminal on both sides.
• There are more gradations.
• Natural language is thought to be between context free and context sensitive.
• This is a basis of formal language theory (computational theory e.g. H. Lewis and C. Papadimitriou (1981) Elements of the Theory of Computation. Prentice Hall)