the added b, the prefix condition will still be satisfied. Thus, if the prefix
condition holds after n steps, it will still hold after n+1 steps. Obviously, the
prefix condition holds after one step, so we have a basis and the induction
succeeds.
7. (a) First, solve the case n = m+3. Then add more b’s. This can be done by
But this is incomplete since it creates at least three a’s. To take care of the
cases n = 0, 1, 2, we add
(d) This has an unexpectedly simple solution
These productions nondeterministically produce either bb or bbb for each
generated a.
8. (a) For the first case n = m and k is arbitrary. This can be achieved by
In the second case, n is arbitrary and m ≤ k. Here we use
Finally, we start productions with S → S 1 |S 2 .
(e) Split the problem into two cases: n = k+m and m = k+n. The firstcase is
solved by
condition holds after n steps, it will still hold after n+1 steps. Obviously, the
prefix condition holds after one step, so we have a basis and the induction
succeeds.
7. (a) First, solve the case n = m+3. Then add more b’s. This can be done by
But this is incomplete since it creates at least three a’s. To take care of the
cases n = 0, 1, 2, we add
(d) This has an unexpectedly simple solution
These productions nondeterministically produce either bb or bbb for each
generated a.
8. (a) For the first case n = m and k is arbitrary. This can be achieved by
In the second case, n is arbitrary and m ≤ k. Here we use
Finally, we start productions with S → S 1 |S 2 .
(e) Split the problem into two cases: n = k+m and m = k+n. The firstcase is
solved by