Question

2.3. For each of the NFA8 in Problem 2.2, construct the equivalent DFA

Answer 1

a).

The corresponding DFA is:

b a 1 12 12 12 23 3 1 12 23 123 12 123 12 123

Let us understand how this DFA is being constructed from the given NFA.

State 1, on getting input 'a', goes to two states: state 1 and state 2. So, we make a new state named "12", which is a combination of state 1 and state 2. State 1 on getting input 'b' goes to state 3, so that will remain the same.

Now, we will consider the newly created state "12". For this, we will take the union of the states 1 and 2. For e.g.,

• On input 'a', state 1 goes to {1,2} while state 2 goes to {1}. The union of {1,2} and {1} is {1,2}. Thus, like the previous case, we should make a new state named "12". But, there is already a state 12. Therefore, we will not make a new state.
• Similarly, on input 'b', state 1 goes to {3} while state 2 goes to {2,3}. The union of {3} and {2,3} is {2,3}. Therefore, we will make a new state named "23" which is a combination state 2 and state 3.

We will do this for all the states present in the DFA constructed till that point. For e.g., our DFA just got a new state "23". So, we will perform the same procedure for this state too.

This means that we will have to perform this procedure for any number of states being introduced in the DFA table.

Since 2 is the final state in the NFA, in the DFA, all the states containing 2 will be the final states. The states containing 2 are 12, 23, and 123. Thus, these are the final states.

This is how the above DFA is constructed.

b).

The corresponding DFA is:

b 4

(Refer to the part a) for detailed explanation).

Here, state 2 on input ε goes nowhere in the NFA. Thus, we create a new state named 5, which is also called as the dead state or the trap state. (I've named it 5 just because there are 4 states already present names 1-4. You can name it anything you want to.)

A dead state will always point to itself, no matter what the input is. That is why it is also called as the trap state. Thus, in the above case, state 5 will go to itself on getting any input.

Since 3 is the final state in the NFA, in the DFA, all the states containing 3 will be the final states. The state containing 3 is 3 itself. Thus, it will be the final state in the DFA too.

c).

The corresponding DFA is:

h C 1 12 2 13 5 12 123 23 13 4 4 2 3 23 1 13 123 23 1234 2 1234 1 1234 23 1234 14 34 23 124 14 34 3 2 24 1 4 1 2 3 5 23 1234 34 1234 1234 14 134 2 234 1 23 4 124 123 13 14 12 2 13 24 13 23 13 1234 134 1234 2 1 234 134 23 1234 14 5 5 5 5 5

(Refer to the parts a) and b) for detailed explanation).

Here, as we go on constructing the DFA, we encounter more and more new states. Thus, the size of the DFA is very large. For 4 states in the NFA, we have 16 states in its equivalent DFA.

Since 3 is the final state in the NFA, in the DFA, all the states containing 3 will be the final states. The states containing 3 are 3, 13, 23, 123, 1234, 34, 134, and 234. Thus, these are the final states.

Hope it helped. If you have any doubts or queries, please feel free to ask in the comments section. If it helped in any way, please consider giving a thumbs up.