CSE 237, Homework 3 (NFAs)
due 2/15/06 in class

Please start each problem on a new sheet.

Problem 1. Converting RE to an NFA

We showed in class that for every RE there is an equivalent NFA by giving such an NFA in the case of atomic REs (base cases) and showing how to combine them into larger NFAs in the case of regular operations.  Use this algorithm to create an NFA for the following two REs.  Do it in steps, building up from the simplest NFAs for the smallest RE subexpressions, and to the final NFA for the whole expression.  Don't worry that your NFAs are not as simple (small) as can be.

    a. a*b U ba

    b. (a U e)(bcd)* 

Problem 2. Converting NFA to DFA

Use the construction discussed in class to convert the following NFAs to DFAs.

    a. N1 in Figure 1.27;

    b. N3 in Figure 1.34;

Problem 3. Proofs about NFAs

    a. Prove the following, using definitions: If an FSA M contains an unreachable state q, then it is equivalent to M with q and all adjacent transitions removed.  

    b. Find an algorithm that, given an arbitrary NFA M, creates an NFA M' such that L(M') is the complement of L(M); prove that your algorithm is correct. Hint: it will be a two-step algorithm, related to problem 2 of this homework, and to problem 3 of last homework.