CSCI 510 Homework # 1
1. Transforming a NFA with n states into a DFA may require as many as 2n states. Give examples of NFAs with 2 and 3 states that require 4 and 8 states, respectively, in their equivalent DFAs. Use the alphabet Σ = {0,1}. Explain why they require 2n states and find the DFAs in question. 2. Let Σ =??0 0?,?0 1?,?1 0?,?1 1??. So Σ contains all columns of 0s and 1s of height two. A string of symbols in Σ give two rows of 0s and 1s. Consider each row to be a binary number and let C = {w ∈ Σ∗|the bottom row is three times the top row}. For example,?0 0??0 1??1 1??0 0?∈ C because the binary number 0110 is three times the binary number0010, but ?0 1??0 1??1 0?6∈ C because the binary number 110 is not three times the binary number 001.Show that C is regular. For this problem you may assume the truth of the theorem that says that the reverse of a regular language is regular. The reverse of a language A, written AR, is the set of all strings wR = wn ...w2w1 such that w = w1w2 ...wn ∈ A, AR = {wR| wR = wn ...w2w1 where w = w1w2 ...wn ∈ A},
3. Let Σ be as in the previous problem, and let E = {w ∈ Σ∗|the bottom row of w is the reverse of the top row of w}. Show that E is not regular.
1
