The productions of a grammar have the form

(V T)+ (V T) *

The other grammar types we have considered (left linear, right linear, linear, context
free) restrict the form of productions in one way or another. An *unrestricted grammar*
does not.

In what follows, we will attempt to show that unrestricted grammars are equivalent to Turing machines. Bear in mind that

- A language is
*recursively enumerable*if there exists a Turing machine that accepts every string of the language, and does not accept strings that are not in the language. - "Does not accept" is
*not*the same as "reject" -- the Turing machine could go into an infinite loop instead, and never get around to either accepting*or*rejecting the string.

Our plan of attack is to show that the languages generated by unrestricted grammars are precisely the recursively enumerable languages.

Copyright © 1996 by David Matuszek

Last modified Apr 1, 1996