so we can hope to recognize by mechanical means; that is, unrestricted
grammars generate exactly the family of recursively enumerable languages. We
show this in two parts; the first is quite straightforward, but the second involves
a lengthy construction.
Theorem 11.6
Any language generated by an unrestricted grammar is recursively enumerable.
Proof: The grammar in effect defines a procedure for enumerating all strings in
the language systematically. For example, we can list all w in L such that
S ⇒ w,
that is, w is derived in one step. Since the set of the productions of the grammar
is finite, there will be a finite number of such strings. Next, we list all w in L that
can be derived in two steps
S ⇒x ⇒ w,
and so on. We can simulate these derivations on a Turing machine and, therefore,
have an enumeration procedure for the language. Hence it is recursively
enumerable.
This part of the correspondence between recursively enumerable languages
and unrestricted grammars is not surprising. The grammar generates strings by a
well-defined algorithmic process, so the derivations can be done on a Turing
machine. To show the converse, we describe how any Turing machine can be
mimicked by an unrestricted grammar.
We are given a Turing machine
and want to
produce a grammar G such that L (G) = L (M). The idea behind the construction
is relatively simple, but its implementation becomes notationally cumbersome.
Since the computation of the Turing machine can be described by the
sequence of instantaneous descriptions
we will try to arrange it so that the corresponding grammar has the property that
grammars generate exactly the family of recursively enumerable languages. We
show this in two parts; the first is quite straightforward, but the second involves
a lengthy construction.
Theorem 11.6
Any language generated by an unrestricted grammar is recursively enumerable.
Proof: The grammar in effect defines a procedure for enumerating all strings in
the language systematically. For example, we can list all w in L such that
S ⇒ w,
that is, w is derived in one step. Since the set of the productions of the grammar
is finite, there will be a finite number of such strings. Next, we list all w in L that
can be derived in two steps
S ⇒x ⇒ w,
and so on. We can simulate these derivations on a Turing machine and, therefore,
have an enumeration procedure for the language. Hence it is recursively
enumerable.
This part of the correspondence between recursively enumerable languages
and unrestricted grammars is not surprising. The grammar generates strings by a
well-defined algorithmic process, so the derivations can be done on a Turing
machine. To show the converse, we describe how any Turing machine can be
mimicked by an unrestricted grammar.
We are given a Turing machine
and want to
produce a grammar G such that L (G) = L (M). The idea behind the construction
is relatively simple, but its implementation becomes notationally cumbersome.
Since the computation of the Turing machine can be described by the
sequence of instantaneous descriptions
we will try to arrange it so that the corresponding grammar has the property that