Problems on DFA (Set 2)

Hinzugefügt: 2026-05-09

[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 solved four problems on DFA construction including designing a DFA for accepting the strings starting with a given substring ending with a given substring containing a given substring and even based on length of a string. And now in this lecture that is problems on DFA set two we are going to solve few more varieties of problems on DFA construction. So let's get started. In this lecture also we will solve total of four problems on deterministic finite automator.

[00:00:45]So here is our very first problem. Let's read it together. Design a transition diagram of a DFA that accepts all strings with exactly two zeros over the alphabet 0A 1. That means in this question you are required to design a transition diagram of a DFA that accepts all the strings made up of zeros and ones with exactly two zeros. That means the number of zeros in your strings should be exactly equal to two. Not less than two, not greater than two. So let's see our language.

[00:01:25]In this language, you can see every string contains exactly two zeros, not less than two, not greater than two. But it is to be noted that there is no restriction on the position of zeros.

[00:01:41]That means it is not necessary that both the zeros will come together. Zeros can come together and zeros in the string can be far apart also.

[00:01:53]Also there is no restriction on the number of ones and the position of ones.

[00:01:59]So there can be no one, single one, two ones, three ones and so on. So we can have one any number of times anywhere in our string. So let's start designing our DFA.

[00:02:14]This is the simplest string that we will consider while designing our DFA because 0 0 is the smallest string and 0 0 contains exactly two zeros. So it will be accepted by our DFA. So first of all we will have our initial state. On processing the first symbol zero we will reach an intermediate state. let's say Q1 and after processing the last zero we will finally reach our accepting state which is Q2 because now the string contains exactly two zeros.

[00:02:47]So these two states that are Q not and Q1 are rejecting the strings having less than two zeros. The state Q2 is accepting the strings having exactly two zeros. But what about the strings having greater than two zeros? So if I get one more zero after processing exactly two zeros, I will reach the dead state that is Q5 because now we have greater than two zeros. So we are reaching the dead state that is Q5. So this is a basic transition diagram for our DFA. But it is still not a valid DFA. In order to make this transition diagram a valid DFA, we need to complete all the transitions for all the states.

[00:03:36]Q, Q1 and Q2 have a transition for zero.

[00:03:41]But these states do not have a transition for input symbol one. And I have just told you that in this question there is no restriction on the number of ones and the position of ones. That means one can come anywhere any number of times. And that is why we will simply create a self loop of one on these three states.

[00:04:04]Now if I talk about the state Q5 that is a dead state. So once I reach the dead state on getting any symbol 0 or 1 I will still remain at dead state. So I can simply create a self loop of 0 and 1 over the dead state Q5.

[00:04:23]Now this is the valid DFA for the given problem. And now we can proceed to our second problem.

[00:04:30]This is the second problem. Let's read it together. Design a transition diagram of a DFA that accepts all strings with at least two zeros over the alphabet 0A 1. That means in this question you are required to draw a transition diagram of DFA that accepts all the strings made up of zeros and ones with at least two zeros. Now at least two zeros means that the number of zeros should be greater than equal to two. Number of zeros cannot be less than two. So let's see our language.

[00:05:07]In this language you can see every string has the number of zeros greater than or equal to two. No string has number of zeros less than two. Here we have two zeros. Here we have three zeros. Here we have four zeros and so on. So no string has number of zeros less than two. Also like the previous question, it is to be noted that there is no restriction on the position of zeros. Also there is no restriction on the position of ones and the number of ones. So one can appear any number of times and anywhere in our string. So let's start designing our DFA. We will consider 0 0 as the simplest possible string because 0 0 is the smallest string and 0 0 is having at least two zeros. So first of all we will have our initial state that is Q not. On processing the input symbol 0 we will reach an intermediate state that is Q1.

[00:06:10]On reading the last symbol that is zero we will reach our accepting state that is Q2. So now our string has at least two zeros in it. Now we simply need to complete all the transitions for all the states.

[00:06:25]Q not and Q1 have the transitions for zero but they do not have a transition for one. And I have already told you that there is no restriction on the number of ones and the position of ones.

[00:06:39]So we can simply have the self loop of one over these two states.

[00:06:45]Now if I talk about our accepting state that is Q2, we can have any number of zeros because we already have two zeros and according to the question our DFA should accept all the strings having at least two zeros. So if more number of zeros come we will remain at the accepting state because our string will be accepted. And if I talk about the transition for input symbol one, that will also be the self loop because we can have any number of ones in the ending also. So we will simply create a self loop of symbols 0 and one over the state Q2.

[00:07:23]This is a complete DFA for problem number two. Now we will proceed to our problem number three.

[00:07:31]Design a transition diagram of a DFA that accepts all strings with at most two zeros over the alphabet 0A 1. Which means you are required to draw a transition diagram of DFA that accepts all strings made up of zeros and ones having at most two zeros. Now what is at most two zeros? At most two zeros means that the number of zeros should be less than or equal to two. Number of zeros should not be greater than two. So let's see our language.

[00:08:06]In this language you can see every string has number of zeros less than or equal to two. No string has number of zeros greater than two. If I talk about this epsylon which is our empty string, it has no symbols neither zero nor one.

[00:08:24]That means the number of zeros is equal to zero which is less than two. That is why it is a valid string. Here we have a single zero. Here we have again no zero.

[00:08:36]Here we have two zeros. So basically in all the strings we don't have number of zeros greater than two. So all these are valid strings. Now we will simply design a DFA for these valid strings. First of all we'll have our initial state that is Q not. And in this case you can see the initial state is the final state itself.

[00:08:58]Why? Because if there is no symbol that will also be accepted. I have just told you in the empty string that empty string has no symbols neither zero nor one. So number of zeros is equal to zero that is less than two. So it will be accepted. And if I have only one zero that will also be accepted. If I have two zeros that will also be accepted.

[00:09:23]But if I have greater than two zeros that means if I get one more zero then I will reach the dead state that is Q5. So the strings having greater than two zeros will not be accepted. Now we will simply complete the transitions for all the states. So Q not Q1 and Q2 have the transitions for zero but they do not have a transition for input symbol one.

[00:09:48]Now exactly like the previous questions here also we have no restriction on the number of ones. So one can come anywhere any number of times. So we can simply create a self loop of one over these three states.

[00:10:05]Now if I talk about dead state you don't have to worry about the transitions of dead state because once we reach the dead state we are trapped at the dead state. So if we get any other symbol from the set of input symbols, we will still remain at dead state. So we will simply create a self loop of symbols 0 and one over our dead state. So this is our deterministic finite automator which will accept all the strings having at most two zeros over the alphabet 0A 1.

[00:10:38]Now we will proceed to our last question that is question number four. Design a transition diagram of a DFA that accepts the given language.

[00:10:49]L is equals to W belongs to 0A 1 asterisk such that second input of W is 0ero and fourth input is 1. That means you are required to draw a transition diagram of DFA that will accept the following language. Now let's understand this language. Here it is written W belongs to 0a 1 asterisk which means the string w can be any combination of 0 and 1. So our language will contain the strings made up of zero and one. Now let's see the second condition.

[00:11:29]Second input of w is zero and fourth input is one.

[00:11:34]So the second symbol of our string W should be zero and the fourth symbol should be one. So there are two restrictions on our string that the second symbol should be zero and fourth symbol should be one. But there are no restrictions on the first symbol, third symbol, fifth symbol, sixth symbol, seventh symbol and so on. Only there are two restrictions. So let's see the refined form of our language.

[00:12:05]In this language you can see all the strings have second symbol as zero and fourth symbol as one. In this string the second symbol is zero and the fourth symbol is one. The second symbol is zero and the fourth symbol is one and so on.

[00:12:22]So let's start designing our DFA.

[00:12:25]We will have our initial state that is Q not. And now we will process our very first symbol. As you can see there is no restriction on the first symbol. So first symbol can be either zero or one.

[00:12:39]So on getting the first symbol we can reach the next state which is Q1. Now we will process the second symbol and there is a restriction on the second symbol which should be only zero. So if the second symbol is zero then we will reach the next state. Now again there is no restriction on the third symbol. So third symbol can also be either zero or one and we will reach the state Q3.

[00:13:04]Again there is a restriction on fourth symbol which should only be one. So if I get one as the fourth symbol then I will reach Q4 which is our accepting state.

[00:13:15]Now we will simply complete the transitions for all the states.

[00:13:20]Q not has both the transitions for zero as well as one.

[00:13:25]Q1 has a transition for zero but doesn't have a transition for one. And we already know if the second symbol is zero, it is moving towards the accepting state. But if the second symbol is one, it will reach the dead state that is Q5.

[00:13:42]Because on getting one as the second symbol, our condition is failing.

[00:13:48]For the state Q2, we have both the transitions. For the state Q3, we have a transition for input symbol one, but we don't have the transition for input symbol zero. And according to the question, if the fourth input is one, then we reach the accepting state. But if the fourth symbol is zero, then we will reach the dead state because on getting fourth symbol is zero, our condition is failing. Now once we reach the dead state, we don't need to worry about the transitions. So we will simply create a self loop of 0 and 1. And for the final state Q4 we have already got 0 as our second input and one as our fourth input. So it doesn't matter what comes after that. So we will simply have a self loop of 0a 1 over the state Q4. So this is a complete deterministic finite automator for the following language. And in this way we have completed all the four problems on DFA.

[00:14:51]But still there are few more exciting problems left to cover. So we will solve those problems in our next lecture. So this was all from my side for this lecture. Thank you and I'll see you in the next lecture.