Aw 1 , with A ∈ V and w 1 ∈ T * . By the inductive assumption
can be derived via . If we now apply a → Bv, then
But contains the rule A → v R B, so we can make the derivation
completing the inductive step.
11. Split this into two cases: (i) n and m are both even and (ii) n and m are both
odd. The solution then falls out easily, with
taking care of case (i).
13. (a) First construct a dfa for L. This is straightforward and gives
transitions such as
with q 0 the initial and final state. Then the construction of Theorem 3.4
gives the answer
17. Obviously, L(G 1 ) is regular, as is L(G 2 ). We can show that their union is
also regular by constructing the following dfa.
can be derived via . If we now apply a → Bv, then
But contains the rule A → v R B, so we can make the derivation
completing the inductive step.
11. Split this into two cases: (i) n and m are both even and (ii) n and m are both
odd. The solution then falls out easily, with
taking care of case (i).
13. (a) First construct a dfa for L. This is straightforward and gives
transitions such as
with q 0 the initial and final state. Then the construction of Theorem 3.4
gives the answer
17. Obviously, L(G 1 ) is regular, as is L(G 2 ). We can show that their union is
also regular by constructing the following dfa.