1.1. Explain please

1.1.1

1.1.2

1.1.3.

- 00:00 1.1 NFA to DFA Consider the following NFA, which accepts strings that: begin with b and end with b or aa (with 0 or more as and bs in between) or begin and end with a (with 0 or more as and bs in between). (convince yourself this is the lanugage recognized by the NFA). a, b 5 1 a 6 0 7 10 11 a, b Recall that e-closure(s) for a state s is the set of states reachable from s using only e-transitions, and that this idea of reachability is transitive, that is, if there is an e-transition from s to s' and one from s' to s", then s" is in e-closure(s). Compute (a) c-closure (0) (b) E-closure(3) (c) E-closure(2) Use the subset construction to convert the NFA above into a DFA. You may present the resulting DFA using either a transition diagram or a transition table. Recall that, in the subset construction, states of the DFA correspond to sets of states of the NFA. Label your DFA states with the set of NFA states, e.g. {1,2,3). The start state should be e-closure(0). Why does the DFA you constructed above not have an error state? (Think about when, during scanning an input, we would realize that a string cannot be in this language.)