[Overview] [Previous] [Next]
Theorem. Any language generated by an unrestricted grammar is recursively enumerable.
This can be proven as follows:
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 .
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.
Copyright © 1996 by David Matuszek
Last modified Apr 8, 1996