Problem Solving in Automata, Languages, and Complexity

2.7 Minimum Deterministic Finite Automata 69

(d) If A and AB are regular, then B is regular.

(e) If A and B are regular, then Up0 - ( Ai n Bi) is regular.

9. Show that every regular language in 0* can be represented in the form

0”’ + 0”” +.. l + Oak + (obl + ob2 + l l - + Obh)(OC),,

for some integer constants al, ~2, l l. , ukr bl, b2, l l l , bh, and c.

* 10. A subset P of nonnegative integers is ultimately periodic if there exists

two positive integers b, p such that, for all nz > - b, m E P implies

m. + p E P. Prove the following statements:

(a) For any regular language L, { (~1 ] x E L} is ultimately periodic.

(b) A language L over (0) is regular if and only if { 1~1 I x E L} is

ultimately periodic.

(c) If f is a mapping from integers to integers such that f-l (P) is

ultimately periodic for every ultimately periodic set P, then the

set {Z E A I (3y) [ly] = f( IX]), y E B]} is regular for every pair of

regular sets A and B.

(d) If f is a mapping from integers to integers such that f -’ (P) is

ultimately periodic for every ultimately periodic set P, then the

set {z I (3Y) [IYI = f(l4>7 XY E L) is regular for every regular set

L.

* 11. Apply Exercise 10(d) a b ove to prove the following results:

(a) If L is a regular language, then so is {Z I (3~) []y] = 21Xi, my E L}.

[Hint: Use Fermat’s theorem, which states that for any odd integer

m. > 3, there exists an integer v(m) such that 2q@) G 1 mod m.]

(b) If Lis a regular language, then so is {Z I (3~) []y12 = (XI, my E L}.

2.7 Minimum Deterministic Finite Automata

In the past few sections, we have introduced a number of ways to construct

a DFA for a given regular language. These methods, however, often result in

DFA’s with a large number of states. For instance, if we are given a regular

expression Y, we can find a DFA for L(r) by first finding an NFA M1 from r,

using the method developed in Section 1.3, and then converting Ml to a DFA

k5 by the subset construction method of Section 2.4. What is the size of the

DFA M2 compared with the size of T or &!I? In general, the first step creates

an NFA of O(n) states from a regular expression of n symbols, and the second

step creates a DFA of up to 2” states from an NFA of n states (cf. Example

2.27). Apparently, such a DFA is too big for a reasonably big number n.

As another example, consider the NFA hl’ constructed from a given DFA

M in Example 2.40. Suppose the given DFA M has n states, then M’ has