[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.

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 empty string.

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.


Copyright 1996 by David Matuszek
Last modified Apr 8, 1996