L = {a 2 n : n ≥ 0}.
It is known that L-systems with productions of the form (13.2) are not
sufficiently general to provide for all algorithmic computations. An extension of
the idea provides the necessary generalization. In an extended L-system,
productions are of the form
(x, a, y) → u,
where a ∈ Σ and x,y, u ∈ Σ*, with the interpretation that a can be replaced by u
only if it occurs as part of the string xay. It is known that such extended Lsystems are general models of computation. For details, see Salomaa (1985).
EXERCISES
1. Find a matrix grammar for
L = {ww : w ∈{a, b}*}.
2. What language is generated by the matrix grammar
P 1 : S → S 1 S 2 ,
P 2 : S 1 → aS 1 b,S 2 → bS 2 a,
P 3 : S 1 → λ, S 2 → λ?
3. Suppose that in Example 13.7 we change the last group of productions to
P 3 : S 1 → λ, S 2 → S.
What language is generated by this matrix grammar?
4. Why does the Markov algorithm in Example 13.9 not accept abab?
5. Find a Markov algorithm that derives the language L = {a n b n c n : n ≥ 1}.
It is known that L-systems with productions of the form (13.2) are not
sufficiently general to provide for all algorithmic computations. An extension of
the idea provides the necessary generalization. In an extended L-system,
productions are of the form
(x, a, y) → u,
where a ∈ Σ and x,y, u ∈ Σ*, with the interpretation that a can be replaced by u
only if it occurs as part of the string xay. It is known that such extended Lsystems are general models of computation. For details, see Salomaa (1985).
EXERCISES
1. Find a matrix grammar for
L = {ww : w ∈{a, b}*}.
2. What language is generated by the matrix grammar
P 1 : S → S 1 S 2 ,
P 2 : S 1 → aS 1 b,S 2 → bS 2 a,
P 3 : S 1 → λ, S 2 → λ?
3. Suppose that in Example 13.7 we change the last group of productions to
P 3 : S 1 → λ, S 2 → S.
What language is generated by this matrix grammar?
4. Why does the Markov algorithm in Example 13.9 not accept abab?
5. Find a Markov algorithm that derives the language L = {a n b n c n : n ≥ 1}.