ON GRAMMAR AND LANGUAGE FAMILIES

Article type: Research Article

Authors: Fernau, Henning

Affiliations: Lehrstuhl lnformatik für Ingenieure und Naturwissenschaftler. Universität Karlsruhe (TH). D-76128 Karlsruhe, Germany, email: [email protected]

Abstract: In this paper, we emphasize the differences of grammar families and their properties versus language families and their properties. To this end, we investigate grammar families from an abstract standpoint, developping a new framework of reasoning. In particular when considering decidability questions, special care must be taken. We illustrate this by inspecting some theorems and their proofs in the field of regulated rewriting. As an exercise, we show that there is no ‘effective’ grammatical characterization of the family of recursive languages.

DOI: 10.3233/FI-1996-25102

Journal: Fundamenta Informaticae, vol. 25, no. 1, pp. 17-34, 1996