[Overview] [Previous] [Next]

Definition of Unrestricted Grammars

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.