Q = {q 0 , q 1 ,…, q n }.
Figure 7.4
Then consider
with
and constructed from δ by including
for all q f ∈, F s ∈ Γ, and
for all
q i ∈ Q, s ∈ Γ, u ∈ Γ*. For M to accept a n b n we must have
with q i ∈ F. Because M is deterministic, it must also be true that