Lecture 5 min.
The Chomsky hierarchy is a classification of formal languages and formal grammars, according to which they are divided into 4 types by their relative complexity. It was proposed by Noam Chomsky, a linguist and professor at the Massachusetts Institute of Technology.
According to Chomsky, formal grammars can be divided into four types. For a grammar to be assigned to one type or another, all of its rules (productions) must conform to certain schemes.
A phrase-structure grammar G is an algebraic structure, an ordered quadruple (VT, VN, P, S), where :
— the alphabet (set) of terminal symbols, or terminals,
— the alphabet (set) of nonterminal symbols, or nonterminals,
— the vocabulary 
, where 
— the finite set of productions (rules) of the grammar, 
— the start symbol (source).Here 
is the set of all strings over the alphabet 
, and 
is the set of nonempty strings over the alphabet .
Type 0 in the Chomsky classification comprises unrestricted grammars — phrase-structure grammars, that is, all formal grammars without exception. The rules can be written in the form:
,
where 
is any nonempty string containing at least one nonterminal symbol, and 
is any string of symbols from the alphabet.
Because of their complexity, such grammars have no practical application.
This type includes context-sensitive (CS) grammars and non-contracting grammars. For a grammar 
all rules have the form :
, where 
. Such grammars are classified as context-sensitive., where 
. Such grammars are classified as non-contracting.These classes of grammars are equivalent. They can be used in the analysis of natural-language texts, but they are practically never used in building compilers because of their complexity. For context-sensitive grammars the following statement has been proved: by some algorithm it is possible to determine in a finite number of steps whether a string of terminal symbols belongs to the given language or not.
This type includes context-free (CF) grammars. For a grammar all rules have the form:
, where 
(for non-contracting CF grammars) or (for contracting ones), 
. That is, the grammar allows only a nonterminal symbol to appear on the left-hand side of a rule.CF grammars are widely used to describe the syntax of computer languages (see parsing).
The third type comprises regular grammars (finite-state grammars), the simplest of the formal grammars. They are context-free, but with limited capabilities.
All regular grammars can be divided into two equivalent classes, which for a grammar of type III have rules of the following form:
or 
, where 
(for left-linear grammars).
; or , where (for right-linear grammars).Regular grammars are used to describe the simplest constructs: identifiers, strings, constants, as well as assembly languages, command processors, and so on.
Formal languages are classified according to the types of grammars that generate them. However, the same language can be generated by different grammars belonging to different types. In that case, the language is considered to belong to the simplest of them. Thus, a language described by a phrase-structure grammar, a context-sensitive grammar and a context-free grammar will be context-free.
As with grammars, the complexity of a language is determined by its type. The most complex are phrase-structure languages (natural languages can be included here), followed by CS languages, CF languages, and, the simplest of all, regular languages.
Hierarchy of languages, grammars and automata:
The alphabet of a formal language is the set of atomic (indivisible) symbols of that formal language (sometimes called letters, by analogy with the alphabets of natural languages, or symbols). Words are built from the symbols of the alphabet of a formal language, and the admissible expressions of the language are specified by a formal grammar.
Most often an alphabet is considered to be a nonempty finite set. For example, the alphabet 
underlies Morse code, and the alphabet 
is the generally accepted set of symbols for representing information in computers. Musical notation symbols and digits are also examples of finite alphabets. In some cases infinite alphabets are also considered, for example the set of natural numbers 
, the simplest example of a countable alphabet (although natural numbers can also be regarded as words over the finite alphabet of digits).
The concept of the alphabet of a formal language is widely used in linguistics (in the branches that study formal grammars), mathematical logic (above all model theory), automata theory, artificial intelligence (including computational linguistics), and computer science (in particular, the theory of programming languages). Certain theoretical problems of constructing words and expressions of formal languages over alphabets are studied by means of general algebra and combinatorics.
A word of a formal language (also string, chain) is an arbitrary sequence of symbols from a given alphabet. The number of symbols in a word 
is called its length and is denoted 
. The existence of a single word of length 0 (the empty word), containing no symbols at all, may be permitted (denoted 
, 
or 
).
The set of all words of length 
over the alphabet 
is denoted by 
; over a finite alphabet the number of such words is exactly the size of the alphabet raised to the power (
). The set of all words over the alphabet (of arbitrary length) is denoted by 
(the Kleene star), so that:
On words over a given alphabet the operation of concatenation is defined — the sequential joining of words. The set of all words over the alphabet with the operation of concatenation forms a monoid (the free monoid[en]). The set of all nonempty words over the alphabet with the operation of concatenation forms a semigroup.
Comments