S ⇒ S 1 S 2 ⇒ aS 1 bS 2 c ⇒ aaS 1 bbS 2 cc ⇒ aabbcc.
Note that whenever the first rule of P 2 is used to create an a, the second one also
has to be used, producing a corresponding b and c. This makes it easy to see that
the set of terminal strings generated by this matrix grammar is
L = {a n b n c n : n ≥ 0}.
Matrix grammars contain phrase-structure grammars as a special case in
which each P i contains exactly one production. Also, since matrix grammars
represent algorithmic processes, they are governed by Church’s thesis. We
conclude from this that matrix grammars and phrase-structure grammars have
the same power as models of computation. But, as Example 13.7 shows,
sometimes the use of a matrix grammar gives a much simpler solution than we
can achieve with an unrestricted phrase-structure grammar.
Markov Algorithms
A Markov algorithm is a rewriting system whose productions
x → y
are considered ordered. In a derivation, the first applicable production must be
used. Furthermore, the leftmost occurrence of the substring x must be replaced
by y. Some of the productions may be singled out as terminal productions; they
will be shown as
x →. y.
A derivation starts with some string w ∈ Σ and continues either until a terminal
production is used or until there are no applicable productions.
For language acceptance, a set T ⊆ Σ of terminals is identified. Starting with
a terminal string, productions are applied until the empty string is produced.
Definition 13.5
Note that whenever the first rule of P 2 is used to create an a, the second one also
has to be used, producing a corresponding b and c. This makes it easy to see that
the set of terminal strings generated by this matrix grammar is
L = {a n b n c n : n ≥ 0}.
Matrix grammars contain phrase-structure grammars as a special case in
which each P i contains exactly one production. Also, since matrix grammars
represent algorithmic processes, they are governed by Church’s thesis. We
conclude from this that matrix grammars and phrase-structure grammars have
the same power as models of computation. But, as Example 13.7 shows,
sometimes the use of a matrix grammar gives a much simpler solution than we
can achieve with an unrestricted phrase-structure grammar.
Markov Algorithms
A Markov algorithm is a rewriting system whose productions
x → y
are considered ordered. In a derivation, the first applicable production must be
used. Furthermore, the leftmost occurrence of the substring x must be replaced
by y. Some of the productions may be singled out as terminal productions; they
will be shown as
x →. y.
A derivation starts with some string w ∈ Σ and continues either until a terminal
production is used or until there are no applicable productions.
For language acceptance, a set T ⊆ Σ of terminals is identified. Starting with
a terminal string, productions are applied until the empty string is produced.
Definition 13.5