Problems on NFA (Set 2)

Added: 2026-05-25

[00:00:00]Hello everyone. Welcome to Nesso Academy. We are learning theory of computation and in the previous lecture we have solved four important problems on NFA construction. And today in this lecture, that is problems on NFA set two, we are going to solve few more remaining questions on NFA construction based on the length of the string. So let's get started.

[00:00:26]In this lecture we will solve total three problems on NFA construction. So let's read the very first problem.

[00:00:33]Design an NFA that accepts all strings with length exactly two over the alphabet A, B.

[00:00:42]Which means you are required to construct a non-deterministic finite automata that will accept all the strings made up of A's and B's such that the length of the string is exactly equal to two.

[00:00:57]Now length exactly equal to two means that the number of symbols in the strings should be exactly equal to two.

[00:01:05]Not less than two, not greater than two.

[00:01:08]Now what are these two symbols in the strings?

[00:01:12]As you can see our alphabet is A, B.

[00:01:15]So these two symbols can be either A or B. So the first symbol can also be either A or B and the second symbol will also be either A or B. Let's start designing our NFA.

[00:01:28]First we will have our initial state, which is Q0. On getting the first symbol, which can be either A or B, we will reach the state Q1.

[00:01:37]And on getting the second symbol, which also can be either A or B, we will reach the final state, which is Q2. And now our string is having two symbols, that is why the string is getting accepted.

[00:01:52]So this is the required NFA for this problem. Now if it was required to create the DFA for the same problem, then we need to add one more transition for the state Q2 for the symbols A and B.

[00:02:06]That would depict the strings of length greater than two, which will lead to the dead state. But in case of NFA, we usually focus only on the acceptance path. The path which is not present in NFA will automatically lead to rejection of the string.

[00:02:23]So, let's move towards the second question.

[00:02:26]Design an NFA that accepts all the strings with length at most two over the alphabet A {comma} B.

[00:02:35]That means you are required to construct an NFA that accepts all the strings made up of A's and B's such that the length of the string is at most two.

[00:02:46]Now, length at most two means the number of symbols in the strings should be less than or equal to two.

[00:02:53]The number of the symbols in the strings should not be greater than two. So, let's start designing our NFA.

[00:03:00]First, we will have our initial state, which is Q0. And you can see Q0 is the final state also.

[00:03:07]Why?

[00:03:09]Because as per this question, the length of the string should be at most two.

[00:03:14]So, the length of the string can be zero, length of the string can be one, and length of the string can be two.

[00:03:22]If the length of the string is zero, that means there is no symbol in the string.

[00:03:27]And here you can see if there is no symbol in the string, that will also be accepted because zero is also less than two.

[00:03:35]If I get only one symbol from A or B, that will also be accepted because one is also less than two.

[00:03:42]If I get one more symbol, either A or B, that will also be accepted because two is also less than equal to two.

[00:03:51]But if I get one more symbol, that will be rejected, and we need not to show the rejection path in case of NFA. So, this is the complete, required, and valid NFA for this problem. Now, let's proceed to our last problem.

[00:04:06]Design an NFA that accepts all the strings with length at least two over the alphabet a {comma} b.

[00:04:14]Which means you are required to construct an NFA that will accept all the strings made up of a's and b's such that the length of the string is at least two.

[00:04:26]Length at least two means that the number of symbols in the strings should be greater than equal to two. The number of symbols in the string should not be less than two. Let's start designing our NFA.

[00:04:39]First, we will have our initial state, which is q0. If I get only one symbol, our string is not getting accepted. It is reaching an intermediate state, which is q1. But, if I get one more symbol, the number of symbols are two. That means our string will be accepted because as per the question, the number of symbols should be greater than or equal to two. So, if we get more symbols after getting the second symbol, that will also be accepted because number of symbols can be greater than two. So, we will simply create a self loop over the state q2 for the symbols a and b, which depict that there can be more than two symbols in the string, which will be accepted.

[00:05:21]So, these were the three important problems based on NFA construction that required the knowledge of length of the string.

[00:05:29]Now, before ending this lecture, I have one homework problem for you.

[00:05:35]So, here is the homework problem. In this problem, you are required to select the correct NFA out of these four NFA that accepts all the strings over the alphabet 0,1 such that the third symbol from the right end of the string is zero.

[00:05:54]So, solve this problem and once you find the correct option, do not forget to post it in the comment section. So, in this way we have completed our topic problems on NFA.

[00:06:06]So, till now we have completed two major topics of theory of computation, the deterministic finite automata and the non-deterministic finite automata. From the next lecture onwards, we are going to start with one of the most important topics of TOC that is repeatedly asked in your examinations.

[00:06:26]Conversion of NFA into DFA.

[00:06:29]So, this was all from my side for this lecture. Thank you and I'll see you in the next lecture.

[00:06:38]>> [music] [music]