Problems on NFA (Set 1)

本站收录: 2026-05-22

[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 what is a transition diagram and a transition table of a nondeterministic finite automator and now in this lecture that is problems on NFA set one. We are going to solve few interesting problems on NFA construction that are very important for your exams.

[00:00:27]So in this lecture we will solve total four problems on NFA construction. So without any further delay let's start with our very first problem. Let's read this together. Design a transition diagram of an NFA that accepts all strings beginning with zero over the alphabet 0A 1. which means you are required to draw the transition diagram of an NFA that accepts all the strings made up of zeros and ones that are beginning with the symbol zero. So your NFA should accept all the strings that are starting with zero. Let's see the language here. You can see our language L contains all the strings beginning with the symbol zero. That means these all strings are valid strings and our NFA should accept these valid strings.

[00:01:25]If you remember we have solved the same problem when we were solving the questions on DFA construction and there we have designed a DFA that looks like this.

[00:01:37]So in this DFA you can see Q not is the initial state and if the string is beginning with zero it is getting accepted and once the string begins with zero it doesn't matter what comes after that. So we have simply created a self loop of 0a 1 which means any combination of 0 and 1 can come after this symbol zero because the string is beginning with zero. There is no restriction on the ending of the string. And we have also drawn one more transition. If the string is beginning with one, we reached the dead state. And once we reach the dead state on getting any symbol zero or one, we will still remain at the dead state. So this was the DFA for the same problem. And in this case, we are required to draw each and every transition for all the input symbols because that was the condition of DFA.

[00:02:33]But in case of NFA, we are not required to complete all the transitions for all the input symbols. As I have already told you, in case of NFA, we only make the transitions that are necessary and sufficient to represent the given language. And now we will see the NFA for the same question.

[00:02:54]Here is the NFA for the same question.

[00:02:57]We have just removed the transition for input symbol one. And now you have got the valid NFA. So Q not is the initial state. On getting the input symbol zero, we reach the final state that is Q1.

[00:03:10]Which means if the string is beginning with zero, it will be accepted. And it doesn't matter what comes after this zero. So we can have any combination of 0 and one after the string begins with zero. So this is the valid NFA for this problem for accepting the strings beginning with the symbol zero. Now let's see the transition table for this NFA.

[00:03:35]This is the transition table for this transition diagram. And you can see Q not and Q1 are the states. Q not is the initial state and Q1 is the final state.

[00:03:46]0 and 1 are the input symbols for this question. And now you can see Q not on getting the input symbol zero next state is Q1. So Q not on getting the input symbol zero our next state is Q1. That is why we have written Q1. Why in the form of set? I have already told you that in case of NFA we can have more than one possible next states. That is why we write the states in the form of set. Now as you can see Q not doesn't have a transition for input symbol one.

[00:04:20]That is why we will not write anything in this cell. For the state Q1 on getting input symbol zero the next state is Q1. As you can see for the state Q1 on getting the input symbol zero the next state is again Q1. Similarly for the input symbol 1. Q1 on getting the input symbol one the next state is Q1 itself. So this is the transition diagram and the transition table for accepting the strings beginning with the symbol zero. I hope you have understood this problem. Now let's proceed to our second problem.

[00:04:56]Design an NFA that accepts the given language. L is equal to X belongs to A, B asterisk such that X is ending with AB.

[00:05:08]That means we are required to construct an NFA to accept the given language.

[00:05:13]Let's understand this language.

[00:05:16]X belongs to A, B asterisk which means X can be any combination of A and B. So our language will contain all the strings made up of A's and B's. It is not always necessary that W is used to represent a string. Some other letter can also represent a string. like here x is used. So our language will contain all the strings made up of a and b's such that x is ending with a a b. So the string x should end with a a b. That means our MFA will only accept the strings ending with a a b. So what will be the simplest possible string for this problem?

[00:06:03]A A B will be the simplest possible string because A A B is made up of A and B and A A B is also ending with A A B.

[00:06:14]So it will be the simplest possible string. And now we will construct a basic transition diagram to accept the string A A B. Here is our initial state Q not. First symbol is A and we will reach the next state Q1. Second symbol is A and we will reach the next state Q2. Third symbol is B and we will reach the final state which is Q3. In this way we have accepted the string A A B. Now the string should end with A A B which means it doesn't matter what comes in the beginning. So in the beginning we can have any combination of A and B and for this reason we have simply created a self loop of A and B. So this is the valid NFA for the given language. In this NFA you can see we have not completed all the transitions for all the input symbols because that's what we do in the case of DFA. In case of NFA we only make the transitions that are sufficient and necessary to represent the given language. Now we will quickly see the transition table corresponding to the transition diagram.

[00:07:27]This is the transition table for this NFA.

[00:07:30]Q not on getting input symbol A. The next states are Q not and Q1. Here you can see Q not on getting the input symbol A. The first next state is Q not and the second next state is Q1. So we are getting two next states on getting the input symbol A. Now Q not on getting the input symbol B. There is only one next state which is Q not. Q1 on getting the input symbol A. The next state is Q2. And since there is no transition from Q1 for the input symbol B, so we will leave this cell empty. For the state Q2, there is a transition for B.

[00:08:11]But there is no transition for A. So we will not write anything in the cell. Now Q2, for the input symbol B, the next state is Q3 as you can see here. And for the state Q3 you can see there is no transition for input symbol A and B. So we will not write anything in these two cells. So this is the transition diagram and the transition table for this language. Till now we have solved two problems on NFA construction. And it is to be noted that if such questions comes in your exams then first you have to identify the language then you have to draw the transition diagram. After that you need to write the five tuple representation of NFA as we have done in the case of DFA construction problems.

[00:08:59]And at last you need to construct the transition table for the transition diagram of NFA. Now let's proceed to our next problem.

[00:09:09]Design an NFA that accepts all the strings containing the substring 0 1 01 over the alphabet 0A 1. Which means you are required to design the transition diagram of NFA that accepts all the strings containing the substring 0 1 01.

[00:09:30]That means your string should contain the string 0 1 0 1. It doesn't matter what comes before that and what comes after that. Our string should just contain 0 1 0 1 as a part of it. So what will be the simplest possible string?

[00:09:48]Obviously 0 1 01 will be the simplest possible string because 0 1 0 1 itself contains 0 1 0 1. So let's make a basic transition diagram to accept the string 0 1 01.

[00:10:04]Here we have our initial state Q not and the first symbol is zero. We will reach the state Q1. The next symbol is one and we will reach the state Q2. The third symbol is zero and we will reach the state Q3. The last symbol is 1 and we will reach our accepting state which is Q4. Now you can see the string 0 1 01 is accepted by this transition diagram. Now as you can see our string contains the substring 0 1 0 1. So it doesn't matter what comes before and after 0 1 0 1. So we can simply create a self loop in the beginning for the input symbol 0 and 1.

[00:10:46]And similarly we will create a self loop in the ending also for the symbol 0a 1.

[00:10:52]In this way we have completed our transition diagram of NFA for accepting the strings containing the substring 0 1 01. Now let's move forward towards our last question.

[00:11:05]Construct an NFA that accepts binary numbers having first and last bit same.

[00:11:12]Which means you are required to construct an NFA that accepts all the binary numbers having first and last bit same or you can say having first and last digit same which means if the number starts with one it should end with one or if the number starts with zero it should end with zero. So if your number is starting with the symbol one, it should also end with the symbol one.

[00:11:39]And if your number starts with the symbol zero, it should also end with the symbol zero. That's what this problem means. So what will be the simplest possible string for this language?

[00:11:52]A single zero or a single one will be the simplest possible strings for this language. How? Now let's talk about a single zero. A single zero is starting with zero and you can also say it is ending with zero. That means it is starting and ending with the same symbol zero. So it is a valid string.

[00:12:14]Similarly, if I talk about a single one, it is also starting and ending with the same symbol that is one. So that is why a single zero and a single one are the valid and the simplest possible strings for this language. So let's make the transition diagram to accept these two strings. First of all, we will have our initial state that is QI. On getting the input symbols zero or one, we will reach the final state that is QF. In this way, these simplest possible valid strings, a single zero or a single one are accepted by this transition diagram. Now for some time, let's ignore these strings of length one. Now tell me what will be the simplest possible strings. If we don't consider the strings of length one.

[00:13:06]So if we don't consider the strings of length one then obviously the strings of length two will be the simplest possible strings.

[00:13:15]So 0 0 or 1 1 will be the simplest possible strings according to this language. How 0 0 0 is a string which is starting with zero also it is ending with zero which means it is a valid string also if we talk about the string 1 it is also starting with one and ending with one so it is also going to be a valid string.

[00:13:40]Now let's make the transitions to accept the string 0 0. On getting the first zero we will reach the state Q1 and on getting the last zero we will reach the state that is QF which is our final state. In this way our string 0 0 will be accepted. If the string is starting with zero and ending with zero, it doesn't matter what comes in between these two zeros. So we will simply create a self loop of 0a 1. which means any combination of 0 and 1 can come in between 0 and 0. Similarly, let's make the transitions for the string 1.

[00:14:22]On getting the first one, we will reach the state Q2 and on getting the second or last one, we will reach our final state which is QF. In this way, our second simplest possible string 1 is also accepted. So if the string starts with one and the string ends with one, it doesn't matter what comes in between.

[00:14:45]So similarly we can have any combination of 0 and 1 in between these two ones. So we have simply created a self loop of 0, 1. This is the complete and valid transition diagram of NFA for accepting the binary numbers having the first and last bit same. I hope you have understood this diagram. So in this way we have solved all the four problems on NFA construction but still there are few important problems remaining and in the next lecture we will try to cover all the remaining problems. So this was all from my side for this lecture. Thank you and I'll see you in the next lecture.