ABSTRACT
The
Chomsky hierarchy, also occasionally referred to as the Chomsky- Schützenberger
hierarchy defines the hierarchy of grammars as corresponding to their types.
This hierarchy is a nested set of classes of formal grammar all contained
together. This paper provides an overview of the Chomsky hierarchy, with each
of its levels well defined and showing their various applicable areas. It also
discusses beforehand, the personalities involved in the creation of the
hierarchy and definitions of languages, grammar and available grammar types.
INTRODUCTION
The collaboration of Avram Noam Chomsky and
Marcel-Paul Schützenberger brought about the Chomsky- Schützenberger hierarchy
in 1956 popularly known as the Chomsky hierarchy in computer science. Noam
Chomsky was born on December 7th,1928 and as at May 2010 he was the
current Professor ementus of linguistics at MIT. He is regarded as one of the
fathers of modern linguistics. He has been involved in the creation of the
theory of generative grammar and sparked the cognitive revolution in
psychology. His contributions cut across academic majors from linguistics
(transformational grammars, generative grammar and language acquisition) to
computer science (Chomsky hierarchy, Chomsky normal form, context free grammar)
and Psychology (cognitive revolution-1959, and universal grammar).
Marcel-Paul Schützenberger, a French mathematician and
a Doctor of Medicine was born on October 24th, 1920 and died in July
29th, 1996. His contribution in the area of formal language with
Noam Chomsky brought about the Chomsky- Schützenberger hierarchy and the
Chomsky- Schützenberger theorem (Noam Chomsky, 1959).
The hierarchy is a containment hierarchy (strictly
nested sets) of classes of formal grammars classified into four separate class
type. The Highest restricted class type being a subset of the next less
restricted class type up to the last unrestricted class type. The unrestricted
class type acts as a supper set to the other restricted classes which are all
subsets in it.
Click to download the full PDF
