Observations on grammar and language families

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'.