[Overview] [Previous] [Next]

From Grammars To Turing Machines

Theorem. Any language generated by an unrestricted grammar is recursively enumerable.

This can be proven as follows:

1. If a procedure exists for enumerating the strings of a language, then the language is recursively enumerable. (We proved this earlier.)
2. There exists a procedure for enumerating all the strings in any language generated by an unrestricted grammar. (We will demonstrate the procedure shortly.)
3. Therefore, any language generated by an unrestricted grammar is recursively enumerable.

Here's a review of the argument for (1) above. We prove the language is recursively enumerable by constructing a Turing machine to accept any string w of the language.

• Build one Turing machine that generates the strings of the language in some systematic order.
• Build a second Turing machine that compares its input to w and accepts its input if the two strings are identical.
• Build a composite Turing machine that incorporates the two machines above, using the output of the first as input to the second.

Now to systematically generate all the strings of the language. For other types of grammars it worked to generate shortest strings first; we don't know how to do that with an unrestricted grammar, because some productions could make the sentential form shorter. It might take a million steps to derive .

Instead, we order the strings shortest derivation first. First we consider all the strings that can be generated from S in one derivation step, and see if any of them are composed entirely of terminals. (We can do this because there are only a finite number of productions.) Then we consider all the strings that can be derived in two steps, and so on.

Q.E.D.