Question

Consider the NFA M in Fig. 1. Construct an equivalent DFA using exactly the Subset Construction method taught in the lectures (no other method will be accepted). Draw the state diagram of a DFA accepting all binary words that are not in the language (10 + 110)^*. Consider the method "M to M*", shown in the lectures, which constructs the lambda-NFA M^* accepting (L(M))^*, for any given lambda-NFA M. Use that method to construct M^* when given the NFA M in Fig 1 (no other method will be accepted). Use that method as a guide to describe a method that constructs a lambda-NFA M^+ accepting the language (L(M))^*, when given any lambda-NFA M.

Answer 1

The Subset Construction method can be used to construct an equivalent DFA from an NFA. The M to M* method can be used to construct a lambda-NFA accepting (L(M))^*. To construct a lambda-NFA accepting (L(M))^*, we can use a similar method as M to M*, but with an additional epsilon transition.

Step-by-step explanation:

To construct an equivalent DFA using the Subset Construction method, we start with the initial state of the DFA which is the epsilon closure of the initial state of the NFA. For each state in the DFA, we find the next state for each input symbol by taking the epsilon closure of the move of the NFA states. We repeat this process until we have visited all states in the DFA. Finally, any state in the DFA that contains an accepting state of the NFA becomes an accepting state in the DFA.

For the given NFA M in Fig. 1, we start with the epsilon closure of the initial state {q0} which is {q0, q1}. From there, we move to the next states {q0, q1} using input symbol 0, and the next state is {q1, q2}. Similarly, for input symbol 1, the next state is {q1, q2, q3}. We continue this process until we have visited all states in the DFA. The final DFA will have states {q0, q1}, {q1, q2}, {q1, q2, q3}, and the accepting state is {q1, q2, q3}.

Using the method M to M*, we can construct a lambda-NFA M* accepting (L(M))^*. The lambda-NFA M* has the same states as M, but with an additional initial state and additional epsilon transitions. The new initial state is an epsilon transition to the initial state of M. For each accepting state in M, we add an epsilon transition to the new initial state. Finally, the accepting states of M* are the same as the accepting states of M.

To construct a lambda-NFA M+ accepting (L(M))^*, we can use a similar method. We start by constructing M* with the method described above. Then, we add an additional epsilon transition from each accepting state of M* to the initial state of M. This ensures that we can repeat the language of M any number of times, including zero times.