[Overview] [Previous] [Next]
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
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