for producing one such string from a previous one. These observations can be
formalized in the concept of a rewriting system. Generally, a rewriting system
consists of an alphabet Σ and a set of rules or productions by which a string in Σ +
can produce another. What distinguishes one rewriting system from another is
the nature of Σ and restrictions for the application of the productions.
The idea is quite broad and allows any number of specific cases in addition
to the ones we have already encountered. Here we briefly introduce some less
well-known ones that are interesting and also provide general models for
computation. For details, see Salomaa (1973) and Salomaa (1985).
Matrix Grammars
Matrix grammars differ from the grammars we have previously studied (which
are often called phrase-structure grammars) in how the productions can be
applied. For matrix grammars, the set of productions consists of subsets P 1 ,P 2 ,
…,P n , each of which is an ordered sequence
x 1 → y 1 , x 2 → y 2 ,….
Whenever the first production of some set P i is applied, we must next apply the
second one to the string just created, then the third one, and so on. We cannot
apply the first production of P i unless all other productions in this set can also be
applied.
Example 13.7
Consider the matrix grammar
P 1 : S → S 1 S 2 ,
P 2 : S 1 → aS 1 , S 2 → bS 2 C,
P 3 : S 1 → λ, S 2 →λ.
A derivation with this grammar is