NFA - Transition Diagram and Transition Table

本站收录: 2026-05-19

[00:00:00]Hello everyone, welcome to NESO Academy.

[00:00:03]We are learning theory of computation and in the previous lecture we have understood the major differences between DFA and NFA. Before that I have already explained you what is a nondeterministic finite automator and its fiveuple representation. Now in this lecture we are going to understand the transition diagram and transition table of a non-deterministic finite automator. So without any further delay, let's see all the topics of this lecture. Our first topic is transition diagram of NFA and our second topic is transition table of NFA. So let's get started with our very first topic that is transition diagram of NFA.

[00:00:47]I hope you all remember what we have studied under the transition diagram of a DFA. There I have explained you the multiple components in the transition diagram of a DFA like the states, the transitions, the input symbols and the state identifiers. Now in case of NFA also we have exactly same components.

[00:01:11]Let's see. So here is a transition diagram of an NFA. Let's see the various components of this diagram. The first component is the circle which is the representation for the state in an NFA.

[00:01:25]As you can see there are three circles in this diagram which represents the three states of an NFA. The next one is the circle with an inward arrow which is also a state of an NFA but it is a special type of state called as the initial state. In this diagram you can see Q not is the initial state of this NFA. The third component is the double circle which is called as the final state of an NFA. This is also a type of state but it is also a special type of state called as the final state or the accepting state. In this diagram Q2 is the final state of an NFA. Next we have the transition between the states. Let's say this is the state number one. This is the state number two. So this arrow represents the transition from state number one to state number two. In this diagram you can see this is a transition from Q to Q1. This is a transition from Q1 to Q2 and this is a transition from Q2 to Q1.

[00:02:32]You can see all the transitions are involving two states. But there is a special type of transition called as a self loop transition which only involves the one state. So this transition is originating from the given state and coming back to the same state. That means this transition is only involving one state and this transition is called as a self loop transition.

[00:02:58]A self loop transition can be repeated any number of times. So while processing any string using this NFA we can have any number of A's because it will still remain on the same state using the self loop transition you cannot go to any other state. The next component is input symbols. A and B are the two input symbols used in this NFA. These input symbols are the part of input alphabet sigma. The next and the last component is the state identifiers which are Q, Q1 and Q2. As you can see in this diagram, Q not, Q1 and Q2 are the names given to these three states. That is why they are called as the state identifiers.

[00:03:44]So this was the transition diagram of NFA and its various components. So in this way we have completed our first topic that is the transition diagram of NFA. Now let's proceed with our second topic that is transition table of NFA. I have already told you that transition table is important because it is a tabular notation which is more organized and more structured as compared to the diagrammatic representation. So let's see how to convert a given transition diagram of an NFA into the transition table of an NFA. So here we have the same diagram of an NFA which we have just understood. Now let's convert this diagram into a transition table. Here I have the basic structure of the transition table of NFA. In the first column we have the states of NFA. Q not Q1 and Q2. Q not is the initial state of an NFA while Q2 is the final state of an NFA. Q1 is just a normal intermediate state of an NFA. In the first row I have input symbols A and B. As we can see there are only two input symbols used in this NFA A and B. So we have written A and B as our input symbols. So these are the current states represented by Q.

[00:05:02]These are the input symbols represented by sigma. And in these empty cells we are going to fill the next states. So if Q not is the current state, A is the input symbol, what will be the next state? Let's check. If Q not is the current state, A is the input symbol, then the next state is Q1. So we will write Q1.

[00:05:23]Now why I have written this Q1 in the form of a set.

[00:05:28]So if you remember the transition function of NFA returns the set of states. In case of DFA we only have a single state. But in case of NFA we can have more than one next states. That is why we write the next states in the form of a set. Now if the current state is Q not and the input symbol is B, what will be the next state? As you can see there is no transition from Q not for the input symbol B. That is why we will leave this cell empty. This thing is not allowed in DFA because in case of DFA for every state you should have all the transitions but in case of NFA it is allowed. Now let's talk about the state Q1. For the state Q1, there is no transition for input symbol A. So we will leave this cell blank. Now Q1 has a transition for input symbol B and the next state is Q2. So here we will write Q2. For the state Q2, we have two transitions for the input symbol A. So the next states are Q1 as well as Q2. So we will write the next states as Q1, Q2.

[00:06:39]This was also not allowed in case of DFA because in case of DFA we only have one next state. But in NFA more than one next states are also allowed. Now the last cell if the current state is Q2 and the input symbol is B, what will be the next state? As you can see Q2 doesn't have a transition for input symbol B.

[00:07:00]That is why this cell will also be vacant. Now you have two choices. You can leave these three cells wakened to represent that there are missing transitions or you can also use the symbol phi to represent that these transitions are missing in case of NFA because phi also means that for the given current state and the input symbol there is no transition. So this was the transition table for this transition diagram. So we have understood the transition diagram of NFA, the transition table of NFA and we also know how to convert the transition diagram into a transition table. Now we will solve one problem based on NFA construction from scratch in which we will design an NFA for the given problem. And after designing the NFA, we will convert the transition diagram of an NFA into its transition table. So let's see the problem.

[00:07:58]Design a transition diagram and transition table of an NFA that accepts the strings of the form 01 W 1 0 where W belongs to 0a 1 asterisk over the alphabet 0A 1. Now let's understand this question. In this question, you are required to draw the transition diagram and transition table of an NFA that accepts the strings of the form 01 W 1.

[00:08:29]Which means your string should have 01 in the beginning, 1 0 at the end and in between 0 1 and 1 0 you should have W.

[00:08:41]Now what is W? W is just a substring which is any combination of 0 and 1. So W can be a single zero, W can be a single one, it can be multiple zeros or multiple ones or it can be any combination of zero or one. Here you can see we have an asterisk symbol and we know this is a representation for clean star closure and clean star closure also includes the null string that is epsylon. So the value of W can also be epsylon that is a null string. So we can replace this W also by a null string. Now let's see what will be the simplest possible string for this language. So when we will replace this W by the null string epsylon, we will get the string as 0 1 1 0. and 0 1 1 0 will be our simplest possible string because 0 1 1 0 is beginning with 0 1 and ending with 1 0.

[00:09:44]So first of all we will draw a basic transition diagram to accept the string 0 1 1 0. Let's start from the initial state which is Q not. Now on processing the string 0 1 1 0 as 0 1 1 0 it will be accepted because this is a valid string. It is beginning from 01 and it is ending with 1 0. Now it is not true that always the value of w will be epsylon because here you can see w can be any combination of 0 or 1. So between 0 1 and 1 0 there is W. So we will simply create a self loop of the symbol 0 and 1 over the state Q2 to represent the substring W. And this is our non-deterministic finite automator for the given language. Here you can see all the strings are starting with 0 1 ending with 1 0 and in between we can have any combination of 0 and 1. Now, what about the missing transitions in this transition diagram? As you can see, Q not has a transition for zero, but it doesn't have a transition for one. Q1 has a transition for one, but it doesn't have a transition for zero. So, in NFA, we do not need to complete these missing transitions because that's what we do in the case of deterministic finite automator. In case of NFA, it is allowed to have the incomplete transitions because in case of NFA, we only make the transitions that are sufficient and necessary to recognize the given language. And this is a complete and valid NFA for this given problem. Now let's see how to construct the transition table for this transition diagram of NFA.

[00:11:38]Here we have the basic structure of the transition table of this NFA. Here we have the states Q not Q1 Q2 Q3 and Q4. Q not is the initial state. Q4 is the final state. 0 and 1 are the input symbols used in this NFA. Now we will fill these cells.

[00:11:59]Q not on input symbol zero gives the state Q1. So here we will write Q1. Now Q doesn't have a transition for input symbol 1. So we will not write anything in this cell. If we talk about the state Q1, Q1 has a transition for input symbol one, but it doesn't have a transition for input symbol zero. So we will not write anything here. But we will write Q2 in this cell because the next state for input symbol one is Q2. Now if we talk about the state Q2 for the input symbol zero, the next state is Q2 itself. For the input symbol 1, we have two next states Q2 as well as Q3. So here we will write Q2 as well as Q3 in the form of set. Now let's talk about the state Q3. Q3 on input symbol 0 gives the next state as Q4 and Q3 doesn't have a transition for input symbol 1. So we will not write anything in this cell.

[00:12:58]Now for the state Q4, we don't have any transition for input symbol zero as well as for input symbol one. So we will not write anything in these two cells. This is the complete and valid transition table for this transition diagram of NFA. So this is the complete solution for this problem. In this way we have completed our second topic that is transition table of NFA. So in this lecture we have understood two topics transition diagram of NFA and transition table of NFA. From the next lecture we will solve few interesting and important problems based on NFA construction like we did in the case of DFA. So this was all from my side for this lecture. Thank you and I'll see you in the next lecture.