for the language L 2 – L.
22. Let L be the language in Example 2.5. Show that L * is regular.
23. Let G M be the transition graph for some dfa M. Prove the following.
(a) If L (M) is infinite, then G M must have at least one cycle for which there
is a path from the initial vertex to some vertex in the cycle and a path from
some vertex in the cycle to some final vertex.
(b) If L (M) is finite, then no such cycle exists.
24. Let us define an operation truncate, which removes the rightmost symbol
from any string. For example, truncate (aaaba) is aaab. The operation can
be extended to languages by
truncate (L)= {truncate(w):w ∈ L}
Show how, given a dfa for any regular language L, one can construct a dfa
for truncate (L). From this, prove that if L is a regular language not
containing λ, then truncate (L) is also regular.
25. While the language accepted by a given dfa is unique, there are normally
many dfa's that accept a language. Find a dfa with exactly six states that
accepts the same language as the dfa in Figure 2.4.
26. Can you find a dfa with three states that accepts the language of the dfa in
Figure 2.4? If not, can you give convincing arguments that no such dfa can
exist?
2.2 Nondeterministic Finite Accepters
Finite accepters are more complicated if we allow them to act
nondeterministically. Nondeterminism is a powerful but, at first sight, unusual
idea. We normally think of computers as completely deterministic, and the
element of choice seems out of place. Nevertheless, nondeterminism is a useful
notion, as we shall see as we proceed.