To make formal the informal claim of Example 3.25, show that any deterministic finite automaton for the regular expression (a|b)*a(a|b)(a|b)...(a|b ) where (a|b) appears n — 1 times at the end, must...

To make formal the informal claim of Example 3.25, show that any deterministic finite automaton for the regular expression

(a|b)*a(a|b)(a|b)...(a|b )

where (a|b) appears n — 1 times at the end, must have at least 2n states. Hint: Observe the pattern in Exercise 3.9.4. What condition regarding the history of inputs does each state represent?

Example 3.25

Exercise 3.9.4

Construct the minimum-state DFA's for the following regular expressions:


a) (a|b)*a(a|b).

b) (a|b)*a(a|b)(a|b).

c) (a|b)*a(a|b)(a|b)(a|b).

Do you see a pattern?