KIT | KIT-Bibliothek | Impressum
Open Access Logo
URN: urn:nbn:de:swb:90-AAA398943

Observations on grammar and language families

Fernau, Henning


In this report, 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 when trying to use decidability results (which are,
in the first place, properties of grammar families) in order to
establish results (e.g. hierarchy results) on language families.

We illustrate this by inspecting some theorems and their proofs in
the field of regulated rewriting. In this way, we also correct the
formulation of an important theorem of Hinz and Dassow.

As an exercise, we show that there is no `effective' grammatical
characterization of the family of recursive languages. Moreover,
we show how to prove the strictness of the Chomsky hierarchy using
decidability properties only. Most of the material of this report
will be published in `fundamenta informaticae'.

Zugehörige Institution(en) am KIT Informatik für Ingenieure und Naturwissenschaftler (Inf. für Ing. u. Naturwiss.)
Publikationstyp Buch
Jahr 1994
Sprache Englisch
Identifikator KITopen ID: 39894
Erscheinungsvermerk Karlsruhe 1994. (Interner Bericht. Fakultät für Informatik, Universität Karlsruhe. 1994,22.)
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page