W
Chapter 11
A Hierarchy of
Formal Languages
and Automata
e now return our attention to our main interest, the study of formal
languages. Our immediate goal will be to examine the languages
associated with Turing machines and some of their restrictions.
Because Turing machines can perform any kind of algorithmic
computation, we expect to find that the family of languages
associated with them is quite broad. It includes not only regular and context-free
languages, but also the various examples we have encountered that lie outside
these families. The nontrivial question is whether there are any languages that
are not accepted by some Turing machine. We will answer this question first by
showing that there are more languages than Turing machines, so that there must
be some languages for which there are no Turing machines. The proof is short
and elegant, but nonconstructive, and gives little insight into the problem. For
this reason, we will establish the existence of languages not recognizable by
Turing machines through more explicit examples that actually allow us to
identify one such language. Another avenue of investigation will be to look at
the relation between Turing machines and certain types of grammars and to
establish a connection between these grammars and regular and context-free
grammars. This leads to a hierarchy of grammars and through it to a method for
classifying language families. Some set-theoretic diagrams illustrate the
relationships between various language families clearly.
Strictly speaking, many of the arguments in this chapter are valid only for
languages that do not include the empty string. This restriction arises from the
fact that Turing machines, as we have defined them, cannot accept the empty
string. To avoid having to rephrase the definition or having to add a repeated
disclaimer, we make the tacit assumption that the languages discussed in this
Chapter 11
A Hierarchy of
Formal Languages
and Automata
e now return our attention to our main interest, the study of formal
languages. Our immediate goal will be to examine the languages
associated with Turing machines and some of their restrictions.
Because Turing machines can perform any kind of algorithmic
computation, we expect to find that the family of languages
associated with them is quite broad. It includes not only regular and context-free
languages, but also the various examples we have encountered that lie outside
these families. The nontrivial question is whether there are any languages that
are not accepted by some Turing machine. We will answer this question first by
showing that there are more languages than Turing machines, so that there must
be some languages for which there are no Turing machines. The proof is short
and elegant, but nonconstructive, and gives little insight into the problem. For
this reason, we will establish the existence of languages not recognizable by
Turing machines through more explicit examples that actually allow us to
identify one such language. Another avenue of investigation will be to look at
the relation between Turing machines and certain types of grammars and to
establish a connection between these grammars and regular and context-free
grammars. This leads to a hierarchy of grammars and through it to a method for
classifying language families. Some set-theoretic diagrams illustrate the
relationships between various language families clearly.
Strictly speaking, many of the arguments in this chapter are valid only for
languages that do not include the empty string. This restriction arises from the
fact that Turing machines, as we have defined them, cannot accept the empty
string. To avoid having to rephrase the definition or having to add a repeated
disclaimer, we make the tacit assumption that the languages discussed in this