A phrase-structure grammar is a modification of the classical notion of a
rewriting system, introduced by Axel Thue at the beginning of this
century, [Thue,1914].
Many different notations exist to define them. The definition here is close to
the one in [Mateescu,Salomaa,1997].
A rewriting system is a finite set of rules 
, where u and v are words, indicating that
an occurence of u can be replaced by v. Noam Chomsky used
rewriting systems as a device for defining languages. He introduced a hierarchy
of grammars [Chomsky,1959].
Phrase-structure grammars or type 0 grammars are the most general
grammars in the Chomsky hierarchy. They are equivalent to computability.
It is a fundamental result of formal language theory that the family of
phrase-structure languages is equal to the family of recursively enumerable
languages. The latter can be defined by Turing machines, introduced by Alan
Turing, see [Lewis,Papadimitriou,1981]
for example.
Normal forms are often used to achieve simpler proofs of results about
languages. They are also used for syntactical analysis and simplification.
Theorems about normal forms, like ``given a context-free grammar, an equivalent
context-free grammar in normal form can effectively be constructed'' can be
found in [Hotz,1978]
and [Autebert,Berstel,Boasson,1997].
The next chapter, in which the recursive matrix systems are defined, is based on these elementary definitions. Especially the general phrase-structure grammar is needed for further development.
Dominik Heckmann
