Problem 1. Complete the TopHat worksheet titled Spring 2020 HW3.1. There are a total of 10 questions, each worth 2 points.
Problem 2. Consider the regex r = 11(0∪1)∗ ∪(0∪1)∗0 that matches strings starting with 11 or ending with 0.
2(a) Using the process from lecture, convert r to an equivalent NFA N. Be sure to include all of the intermediary NFAs and the -arcs that are required. Note that this differs slightly from the textbook examples as we require every stage to produce a single final state on our diagram. You may use the following shortcut (only for) (0∪1)∗:
0,1
2(b) Convert your resulting NFA into an equivalent DFA using the process from lecture. You should omit any unreachable states. Note that this will not have hundreds of states that might be expected by the conversion process.
Problem 3. (6+2+2+6 points) For this problem, let Σ = {a,b}. Construct an NFA N = (Q,Σ,δ,s,F) and the NFA N0 = (Q,Σ,δ,s,Q − F) such that there is a string w ∈ Σ∗ such that w 6∈ L(N) and w 6∈ L(N0). Provide the computation tree of each NFA given the input w. To answer this problem, you should (a) construct your NFA N, (b) draw the resulting NFA N0, (c) state the string w, and (d) draw the two computation trees.
