Description
In lecture this week, we finished everything needed to complete the conversion back from regex to a DFA algorithm. This required the introduction of nondeterminism, which is a relaxation on the DFA model. In comparison to the DFA model, we made some drastic changes: we can make transitions without reading input and the transition function maps to a (possibly empty) set of states instead of a single state. That said, computation still proceeds more or less the same. Instead of processing one state and one symbol, we need to consider a set of active states and individually see where each one transitions. With this in mind, we are able to complete the cycle with regex translating nicely to NFA models and then NFAs translating (not so nicely) to DFA models.
Problem 1. Complete the TopHat worksheet )
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.
