The Chomsky Hierarchy
Who Is This Guy?
Avram Noam Chomsky is an American professor known for his work in linguistics, political activism, and social criticism. He is sometimes called “the father of modern linguistics” — and he contributed the Chomsky hierarchy of formal languages and grammars, which will be studied in the final lectures in this course.
Overview
The “Chomsky Hierarchy” includes four classes of formal languages and grammars that are used in computational linguistics and in software development. These will be introduced, beginning with the simplest of these, in the first three lectures. The remaining lectures — which will be “for interest, only” will concern problems concerning deciding membership of strings in various kinds of grammars, and “parsing problems”.
Lecture #21: Chomsky Hierarchy I — Regular Languages (Tuesday, November 19)
Why This is Included
Regular languages are the simplest of the languages included in the Chomsky hierarchy. They have applications in text processing and program compilation.
This lecture will introduce a kind of phrase-structure grammar whose languages are the regular languages. It will also introduce alternative characterizations of these languages and computational problems, concerning these languages and their grammars, that are of interest.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #22: Chomsky Hierarchy II — Context-Free Languages (Tuesday, November 26)
Why This is Included
Context-free languages are the next simplest of the languages included in the Chomsky Hierarchy. While students in this course might not be familiar with these languages they (arguably) make use of them all the time — because parsing algorithms for various kinds of context-free languages are used, heavily, to compile software programs.
Like the lecture before this, this lecture will introduce a kind of phrase-structure grammar whose languages are the languages that are now being considered. Once again, alternative characterizations of these languages — that are useful for algorithm development and in proofs — will be introduced, and computational problems, concerning these languages and their grammars, will be described. This time, though, several of the problems, that are of interest, will be unsolvable.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #23: Chomsky Hierarchy III — Context-Sensitive Languages (Thursday, November 28)
Why This is Included
Context-sensitive languages are the next-simplest of the languages in the Chomsky Hierarchy. This is the last of these sets of languages that will be introduced in this course — because the remaining sets of languages, to be considered, are the decidable languages and the recognizable languages — and these have certainly been considered already.
These languages have not been studied as much as the other languages in the Chomsky Hierarchy, and few applications of these are well-documented. However, they have interesting characterizations — including one as a complexity class — so that they serve as a kind of link between computability theory and computational complexity theory.
Once again, the lecture will introduce a kind of phrase-structure grammar whose languages are the languages now being considered. Alternative characterizations of these languages, that are useful when proving their properties, will be described. Various computational problems, for these languages, will be described as well.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #24: Chomsky Hierarchy IV — Normal Forms and Parsing (Tuesday, December 3)
Why This is Included
Both context-free grammars and (arguably) regular grammars play significant roles in compiler development and use. In particular, testing membership in these languages, and the generation of parse trees for the strings that belong to them, are used when converting a computer program, written in a high-level programming, into assembly language, object code or machine code.
The conversion of a context-free grammar into a grammar in Chomsky normal form is also useful when testing membership in the languages of context-free grammars.
“Preparatory reading” for this lecture presentation therefore presents a process that can be used to convert an arbitrary context-free grammar into Chomsky normal form. The lecture presentation describes provably correct — but, unfortunately, inefficient — algorithms that can be used to decide membership, and generate parse trees, for regular grammars, as well as grammars in Chomsky normal form.
Note: This lecture is “for interest only:” Its content will not be tested, in any way, on the final examination.
Preparatory Reading
- Chomsky Hierarchy IV — Normal Forms and Parsing: [ PDF ]
Lecture Presentation
Lecture #25:
Chomsky Hierarchy V — Efficient Algorithms for Parsing
(Thursday, December 5)
Why This is Included
Since the development and use of compilers include tests for membership in regular and various kinds of context-free grammars, it might be helpful to see that deterministic polynomial-time algorithms for parsing in regular grammars, and grammars in Chomsky normal form, do exist.
During the lecture presentation an “algorithm design technique”, that students (ideally) learned about in CPSC 413, will be applied to obtain asymptotically efficient algorithms from the correct — but, unfortunately, inefficient — algorithms that we already have.
Note: This lecture is “for interest only:” Its content will not be tested, in any way, on the final examination.
