Problems on DFA (Set 3)

Hinzugefügt: 2026-05-12

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

[00:00:03]We are learning theory of computation.

[00:00:06]Since the last two lectures, we are solving problems on DFA construction.

[00:00:11]And in this lecture, problems on DFA set three, we are going to solve few more interesting and important problems on DFA. And this is going to be our last lecture on deterministic finite automator. So let's get started.

[00:00:29]In this lecture, we will solve total five problems on deterministic finite automator. So let's see the first problem. Design a transition diagram of a DFA that accepts all strings which don't have the substring babab over the alphabet A, B. which means you are required to draw the transition diagram of a DFA that accepts all the strings made up of A's and B's which don't have the substring BAB. Now if you remember in the previous lecture we have solved a problem which was exact opposite of this problem. There we have constructed a DFA for accepting the strings which have the substring babab and here it is required to construct the DFA to accept the strings which don't have the substring babab. So here is an important point to note. Whenever you are required to construct a DFA that accepts the string which don't have a particular substring, first you need to construct the DFA for the exact opposite condition. That is for accepting the strings that have the particular substring and then you need to interchange the final and the non-final states in order to get the required DFA. So we will follow the similar approach to solve this problem.

[00:01:55]Step number one is design the DFA for accepting the strings that have the substring babab. So this is the DFA for accepting the strings that have substring babab. This DFA we have constructed in the previous lecture and there I have explained you the stepbystep construction of this DFA. If you have any confusion regarding the construction of this DFA, kindly refer to the previous lecture. And now the next step is to interchange the non-final and the final states. So Q, Q1 and Q2 are the non-final states of this DFA while Q3 is a final state of this DFA. According to step number two, we need to interchange or swap the final and non-final states. So Q not Q1 and Q2 are the final states now and Q3 is the non-final state. So we have swapped the final and non-final states and this is the DFA for accepting the strings which don't have the substring babab which was required as per the problem. In this way we have solved the problem number one.

[00:03:07]Now let's proceed to the second problem.

[00:03:10]construct a DFA to check if a given binary number is even. That means you are required to construct a deterministic finite automator to check if a given binary number is even or not.

[00:03:26]Now tell me how to check whether a number is even or not.

[00:03:31]Very simple. We will divide a number by two and if the remainder is zero, it is even number. But if the remainder is one, it is an odd number. But there is a very simple trick also to check whether a given number is even or not. And that is if a binary number ends with zero, it is even. And when it ends with one, it is odd. Which simply means that if the last symbol of your binary number is zero, it means that binary number is even number. But if the last symbol of your binary number is one which means it is an odd number. So we will follow this approach to construct the DFA. Let's see the language.

[00:04:16]Language contains all the strings in which the last symbol is zero. That means our DFA should only accept the even numbers or we can say our DFA will only accept the numbers that are ending with zero. So let's construct the DFA.

[00:04:33]So we are having our initial state Q not and if the number is ending with zero it will be accepted and we will reach the accepting state which is Q1. Now we will complete the transitions for both the states. Q not has a transition for zero but it doesn't have a transition for input symbol one. And if the string is ending with zero, we can have any number of ones in the beginning. So we will simply create a self loop of one over the state Q not. Now if I talk about the state Q1, it doesn't have a transition for zero as well as one. So if the string is already ending with zero, we can have more zeros after that and still it will be accepted. So we will simply create a self loop of zero over the state Q1. But if the next input symbol is one, we need to go back to the initial state so that our string ends with zero. So this is a DFA to check if a given binary number is even or odd and it will only accept the numbers which are even. Now let's proceed to the third question.

[00:05:39]Design a DFA that accepts all the binary numbers that are divisible by three.

[00:05:46]which means you are required to construct a deterministic finite automator which will accept all the binary numbers that are divisible by 3.

[00:05:55]So let's check out the language.

[00:05:58]Language L is equal to W belongs to 0A 1 asterisk such that W mod 3 is equal to 0. Which means that our language L will only contain the strings made up of zeros and ones. And we know the strings that are made up of only zeros and ones are called as binary strings. But in this question we are checking the divisibility by three which is a mathematical operation. And that is why we cannot use the word strings. We can say that language L will contain all the binary numbers such that W mod 3 is equal to zero. Now mod operator is used to calculate the remainder. So when the binary number w is divided by 3, the remainder should be zero. That means the number should be completely divisible by three. Only the numbers which will be divisible by three will be the part of the given language. So now shall we start constructing the deterministic finite automator?

[00:07:04]No, we cannot start constructing the DFA right now because this question is not a very straightforward question. We first need to take few binary numbers. We need to calculate the remainders when we divide those numbers by three. Then we have to develop logic and only after that we can solve this problem by constructing the DFA. So here I have taken few binary numbers. I have taken total 10 numbers from 0 to 9 and I have also taken the binary representation of these numbers. I have also calculated the remainders when these binary numbers are divided by 3. As you can see when 0 is divided by 3 the remainder is 0. When 1 is divided by 3 the remainder is 1.

[00:07:50]When 2 is divided by 3 the remainder is 2. When 3 is divided by 3 the remainder is again zero and so on.

[00:07:58]You can see that when a number is divided by three, there can only be three possible remainders either 0, 1 or 2.

[00:08:09]So to represent these three remainders, we can use three states in our DFA and that are Q, Q1 and Q2. The state Q not is used to represent the remainder zero.

[00:08:23]The state Q1 for one and the state Q2 for two. Now we can start constructing DFA for this problem. As you can see that there are only three states Q not Q1 and Q2. Let's first draw these three states Q1 and Q2. Q not is our initial state and you can see that Q not is used to represent the remainder zero and remainder zero means that the binary number is completely divisible by three and that's what needs to be accepted by this DFA that is why Q not is going to be our accepting state also so Q not is the initial state also as well as the final state for this problem now we will complete all the transitions for these three states. For completing the transitions, we need to process these input strings one by one. So let's take the first input string which is 0 0 0.

[00:09:23]As you can see 0 0 0 is completely divisible by 3 and leaving the remainder zero. That is why it will be accepted by our DFA. So in order to accept 0 0 0 we will simply create a self loop of 0. So that 0 0 0 can be accepted. The next is 0 0 0 1. The remainder is 1. That is why the processing needs to stop at Q1. So we can process 0 01 as 0 0 1. Now the next is 0 1 0. The remainder is 2. So the processing will stop at the state Q2.

[00:10:06]0 1 0 can be processed like 0 1 0. The next is 0 1 1. The remainder is zero.

[00:10:15]That means this will be divisible by 3.

[00:10:18]And that is why the processing needs to be stopped at the accepting state Q not.

[00:10:24]So 0 1 1 can be processed like 0 1 1 at the accepting state. Now the next is 1 0 0. The processing needs to be stopped at Q1. So 1 0 0. The next one is 1 0 1. And the processing needs to be stopped at Q2. So 1 0 and 1. And we can see the processing is stopped at the state Q2 which means the remainder is two. Now in this way we have completed our DFA and you can check every state has a transition for both the input symbols for zero as well as one. Now we will check these remaining strings and we will see whether it is a valid DFA or not. So the next string is 1 1 0 remainder is zero which means this will be divisible by three. So the processing needs to be ended at the state Q not which is an accepting state. Let's check the processing of 1 1 0 1 1 0 accepted.

[00:11:39]Now let's check the number seven which is 1 1 1. Processing needs to be ended at the state Q1 1.

[00:11:49]That is why it is rejected. And similarly you can process these remaining strings also. So this was the standard way to solve such type of problems. But as you can see this is a very lengthy approach and if you use this approach in your exam then your time will be consumed. So I will give you a very simple trick to solve such type of questions.

[00:12:13]For applying that trick you first need to construct the transition table and then you can convert that transition table into the transition diagram.

[00:12:22]Here you can see I have written the three states Q not, Q1 and Q2 which I have already told you that when a number is divided by three there are only three possible remainders 0 1 and 2. And to represent each of these remainders we have three states Q not Q1 and Q2. And I have also told you that Q not will be the initial state as well as the final state. Since we are considering only the binary numbers that is why the input symbols are 0 and one. And now we will fill these blank cells.

[00:12:57]How to fill these blank cells? We just need to remember and keep in mind this sequence Q not Q1 and Q2. Now we will fill horizontally row-wise this sequence Q1 and Q2. Q1 Q2 again Q1 Q2 In this way we have simply constructed this transition table. Now we will convert this transition table into the transition diagram of DFA. So we are having three states Q not Q1 and Q2. Q not Q1 and Q2. Q not on input symbol 0 gives Q not. Q not on input symbol 0 gives Q not. Q on one gives Q1.

[00:13:45]Q not on 1 gives Q1. Similarly Q1 on 0 gives Q2. Q1 on 1 gives Q. Q2 on 0 gives Q1 and Q2 on 1 gives Q2. This is the complete deterministic finite automator for this problem. Now to implement this trick quickly I have taken one more question. Let's check out design a DFA that accepts all the turnary numbers that are divisible by four. There we have considered the binary numbers but here it is written turnary numbers. Binary means two that is why the binary numbers are 0 and 1.

[00:14:29]But the word turnary means three. So the turnary numbers are 0 1 and 2. And here we are checking the divisibility by the number four. So let's see the language.

[00:14:41]Language L is equals to W belongs to 0a 1A 2 asterisk such that W mod 4 is equal to 0. Which means our language will contain all the numbers consisting of only 0, 1 and 2 such that when the number is divided by four, it leaves zero as the remainder. Which means the number should be completely divisible by four. Now we will implement the trick.

[00:15:09]And to implement the trick, we need to draw the transition table. Here is the transition table for this question. You can see that we are considering the turnary numbers. That is why the input symbols are 0, 1 and 2. And when a number is divided by four, there can be four possible remainders 0, 1, 2 or 3.

[00:15:32]That is why the states are Q, Q1, Q2 and Q3. Q being the initial as well as the final state. Now we will apply the trick. To apply the trick, we just need to keep this sequence in mind. that is Q1 Q2 Q3. Now we will fill this sequence one after another row-wise horizontally.

[00:15:57]Q1 Q2 Q3 Q1 Q2 Q3 again Q1 Q2 Q3 again Q1 Q2 Q3. In this way we have completely constructed the transition table and I hope to convert this transition table into transition diagram is not a big deal for you. So I hope you will convert this table into a DFA. In this way we have completed this problem and now we'll proceed to our last problem that is question number five. Identify the language from the given DFA. So here is a DFA and you need to find out the language corresponding to the given DFA.

[00:16:39]Till now we have solved the problems in which the language has been given to you and you need to construct the DFA for that language. But this is a different question. Different but not difficult.

[00:16:51]In this question you are already given with a DFA but you need to find out the language for this DFA. So let's find out. We will start from the initial state which is Q not. We are having two transitions for input symbol A and for input symbol B. But as you can see this transition gives the dead state. So we cannot choose this transition. That is why we will choose this transition and our first input symbol is A. Now let's talk about the state Q1. It also has two transitions for input symbol A as well as for input symbol B. We cannot select this transition because it is giving us the dead state. So we will choose this transition and our second symbol is B.

[00:17:37]Now we have the state Q2. This transition we cannot select because it is giving the dead state. So we will choose this transition and our third input symbol is also B. Now we have reached the final state which is Q3. And after reaching on the final state we can get any combination of a and b and that will be accepted. So after getting a b we can get any number of a and we can also get any number of bs that will be accepted. By seeing this we can conclude that our language will be W belongs to A B asterisk such that W starts with ABB which means our language will contain all the strings that are starting with the substring abb.

[00:18:26]I hope this language is now clear to you. In this way we have completed all the five questions on DFA and from the next lecture we are going to begin with the second type of finite automator that is NFA non-deterministic finite automator. So this was all from my side for this lecture. Thank you and I'll see you in the next lecture.