Problem 1.

Let {} (recall that = ). Prove that there is a DFA M having n accepting states that accepts L. (Assume an underlying alphabet of = {1}.) Then prove that L cannot be accepted by any DFA having fewer accepting states.

Problem 2.

Let n and k be positive integers. How many NFAs are there with states {} and input alphabet {1, 2, , k}?

The length of a regex is the number of symbols in it (counting both special symbols such as and alphabet symbols such as 0; for instance, the length of (0|1)*0110 is 10. Show that there is a language A {0, 1} with the following properties.

For all x A, |x| 4.

No regex with length smaller than 11 recognizes A.

Assume that the only allowed symbols in a regex are ( ) * + | 0 1.