NFA to DFA Conversion (Problem 1)

追加: 2026-05-30

[00:00:00]Hello everyone, welcome to Nesso Academy. We are learning theory of computation and in the previous lecture we have completely understood the process of conversion of NFA to DFA with an example. And now in this lecture that is NFA to DFA conversion problem number one. We are going to solve and understand one very simple but important problem on NFA to DFA conversion. So let's get started.

[00:00:30]In this lecture, we have the topic NFA to DFA conversion. Let's see the problem. Construct an NFA for accepting the strings starting with A over the alphabet A, B. Also convert the NFA into its equivalent DFA.

[00:00:50]So as you can see this question has two parts. In the first part, you are required to construct a nondeterministic finite automator for accepting the strings made up of A's and B's starting with the symbol A. And in the second part of the question, you need to convert that NFA that you construct in the first part into its equivalent DFA.

[00:01:15]So let's start this problem by the very first part that is the construction of NFA for accepting the strings starting with the symbol A.

[00:01:26]So this is the required NFA as per the given problem. In this NFA you can see Q not is our initial state and the first symbol is A. That means our string is beginning with the symbol A and that is why our string is getting accepted. Q1 is the final or the accepting state of the NFA. So as per the given condition, NFA should only accept the strings starting with the symbol A. So in this diagram also NFA is accepting the strings beginning with the symbol A. And once the string begins with the symbol A, it doesn't matter what comes after that. So we can have any combination of A and B after the string begins with A.

[00:02:09]That is why I have created a self loop of the symbol a comma b over the state q1. So this is the transition diagram of an nfa for accepting the strings starting with the symbol a and we are done with the very first part of this question. Now in the second part of this question we are required to convert this nfa into its equivalent dfa. So in the previous lecture we have seen three steps to convert a non-deterministic finite automator into its equivalent DFA. The first step is to construct the transition table of NFA. The second step is to convert the NFA transition table into DFA transition table. And the third step is to construct the transition diagram of DFA from the transition table of DFA. So let's begin our process with the step number one that is the construction of the NFA transition table for the NFA transition diagram. So here we have the NFA transition table corresponding to the given NFA transition diagram. In this table you can see Q not and Q1 are the two states of the NFA. Q not is the initial state and Q1 is the final state. A and B are the input symbols used in this NFA. Now we have to fill the transitions when the current state is getting any input symbol. So for the state Q not on getting the input symbol A we are getting the next state as Q1. Let's see for the state Q not on getting the input symbol A we are getting the next state as Q1. Q not doesn't have any transition for input symbol B. That is why this cell is empty. For the state Q1 on input symbol A we are getting Q1. As you can see for the state Q1 on getting input symbol A we are again getting the state Q1. Similarly for the state Q1 on getting the input symbol B we are getting the same state Q1. So this is the NFA transition table corresponding to the NFA transition diagram that we have constructed. In this way we are done with the step number one that is the construction of NFA transition table from the NFA transition diagram. Now let's proceed with the step number two that is the conversion of NFA transition table into the DFA transition table.

[00:04:35]So here we have the transition table of NFA that we have just constructed and now we will apply the subset construction algorithm that we have studied in our previous lecture to convert this NFA transition table into the DFA transition table. So let's see the basic structure of the DFA transition table.

[00:04:56]As you can see I told you in the previous lecture that the header row of the DFA transition table will be same as the header row of NFA transition table.

[00:05:06]That is why we are having Q sigma A and B. Like here also Q sigma A and B. Now let's talk about the first row of the DFA transition table. I told you that the first row of the DFA transition table will be almost same as the first row of NFA transition table. So the first row of DFA transition table is this that is Q not Q1 and PH. We can verify from this table. We have the state Q not. Similarly, we have the state Q not. We have the state Q1. Here also we have the state Q1. And here we are having the missing transition. Which means that for the state Q not there is no transition for input symbol B in the NFA. But we know in case of DFA every state should have a transition for every input symbol. That is why we cannot use the blank cell in case of DFA. So in DFA this blank cell will be replaced by a special state called as the dead state in case of DFA which is represented by the symbol five. These square brackets are used to represent that these three states are the single states. Now what will be the next step?

[00:06:20]Yes, the next step is to check whether we have received any new state or not in this DFA table. Let's check.

[00:06:30]So we have got two new states Q1 and five because these two states are not present in our DFA. So we need to create the entries for these two states. So here is the entry for the state Q1 and here is the entry for the state five.

[00:06:47]Now we can complete the transitions for these two states. For the state Q1 on input symbol A, what will be the next state? We can find the next state by referring to the NFA transition table.

[00:07:00]For the state Q1 on input symbol A, the next state is Q1. So here we will write Q1. Similarly for the state Q1 and the input symbol B, the next state is Q1. So here also we will write Q1. Now again check do we get any new state. We are getting the states as Q1 and Q1 which is already present in our DFA. That means there is no new state. So we will not create any other entry. Now we will fill the transition for this dead state five.

[00:07:34]Now here we don't have any entry for five. But we know that once we reach the dead state on getting any input symbol we will still remain at the dead state.

[00:07:45]That is why five on a also gives five and five on b also gives five. Now let's check whether we have received any new state or not. We have received two states five and five. But the dead state five is already present in our DFA. That means these are not new states. So we will not create any other entry. And this is how we have reached the termination point of this DFA transition table as we have not received any new state. So we will stop the process of construction of DFA transition table.

[00:08:21]Now let's identify the final state of this DFA. I told you the final state of the DFA will be the state which contains the final state of NFA. The final state of NFA is Q1. So all the states of the DFA that contain Q1 will be the final states of the DFA. As you can see in this DFA only this set contains Q1. That is why this will be the final state of the DFA. So this is the DFA transition table that we have constructed from the NFA transition table and in this way we have completed our step number two also.

[00:09:02]Now let's proceed with our step number three which is a very easy step. In this step we need to convert this DFA transition table into the transition diagram of DFA. So we are having the DFA transition table. And now we need to convert this DFA transition table into the corresponding DFA transition diagram. So here is the transition diagram of the DFA.

[00:09:28]As you can see, we have three states in the DFA transition table. That is why we have drawn three states in the transition diagram also. Q, Q1 and five.

[00:09:40]Now we will make all the transitions.

[00:09:43]Q not on A gives Q1. Q not on A gives Q1. Q not on B gives the dead state five. Q not on B gives the dead state 5.

[00:09:54]Q1 on A gives Q1. Q1 on B also gives Q1.

[00:09:59]So Q1 on A and B gives Q1.

[00:10:02]Five on A gives five. Five on B also gives five. Here you can see we have the dead state five. On getting input symbol A and B. we are getting the same state that is five. So this is the DFA transition diagram for accepting the strings starting with the symbol A. As you can see this is our initial state Q not. If the string begins with the symbol A, the string is getting accepted at the final state. But if the string begins with B, it is getting rejected at the dead state. So this is the required DFA for the given problem. Now if you want you can simply remove these square brackets from the states because as we can clearly see Q not Q1 and PH are the three single separate states of this DFA. So you can simply remove these square brackets. Also if you want you can use any other state identifier instead of five. So you can use any state like Q2 to represent the dead state of this DFA. So this is the solution of the given problem in which we have first constructed an NFA and then we have converted that NFA into its equivalent DFA. Now before I end this lecture, I have one homework problem for you.

[00:11:25]Construct an NFA for accepting the strings ending with zero over the alphabet 0A 1. also convert the NFA into its equivalent DFA. So in this problem, you are required to construct an NFA for accepting the strings made up of zeros and ones ending with the symbol zero.

[00:11:46]And once you are done with the NFA construction, you need to convert that NFA into its equivalent DFA. So solve this problem and once you are done with this problem, kindly write done homework in comment section. So in this way we are done with our topic NFA to DFA conversion. In this lecture I have taken a very simple problem of NFA to DFA conversion to develop a basic and good understanding in your minds. But in the next lecture I will take one advanced problem so that you can open up your mind. So this was all from my side for this lecture. Thank you.