Decision Problems of Phrase-Structure Grammars

Abstract

Phrase-structure grammars were first introduced and studied by Chomsky as devices for generating the sentences of a language. By means of increasingly heavy restrictions on the productions (rewriting rules), four types of grammars were singled out by Chomsky: type 0 (unrestricted), type 1 (context-dependent), type 2 (context-free), and type 3 (finite state). In this paper, a number of decision problems are resolved for these classes of grammars and the languages they generate, largely in the negative. A table of decision problems for grammars of the four different types is presented. This table indicates the problems which have been found to be decidable or undecidable. The ambiguity problem for type 3 grammars and the emptiness and infiniteness problems for type 2 grammars are shown to be decidable. A known unsolvable problem, the Post correspondence problem, is the key to the undecidability proofs which are given. For type 2 grammars, the ambiguity and equivalence problems are proved undecidable; the emptiness and infiniteness problems for type 1 grammars are shown to be undecidable. There is no algorithm to decide whether a language of a given type can be generated by a grammar of a more restricted type. The results on type 2 grammars were first obtained by Bar-Hillel, Perles, and Shamir.