[Overview] [Previous] [Next]

Definition of Unrestricted Grammars

The productions of a grammar have the form

(V union T)+ goes to (V union 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

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