Problems on DFA (Set 1)

本站添加: 2026-05-13

[00:00:00]Hello everyone, welcome to Nesso Academy. We are learning theory of computation and in the previous lecture we have already understood what is a transition diagram and what is a transition table of a DFA and now in this lecture that is problems on DFA set one we are going to understand few interesting problems on DFA. So in this lecture we will understand total four problems on deterministic finite automator. So let's get started with our very first problem. Let's read this problem together. Design a transition diagram of a DFA that accepts all strings beginning with zero over the alphabet 0A 1. Which means we are required to design a transition diagram of a deterministic finite automator which will accept every possible string of 0 and 1 that is beginning with the symbol zero. That means our DFA should accept all the strings beginning with zero and should also reject all the strings beginning with one.

[00:01:14]That means our DFA should be able to handle both the scenarios accepting the strings starting with zero and rejecting the strings starting with one. So now let's start our solution.

[00:01:28]First of all, this is the language of our DFA. The language set L contains all the strings that are valid according to the problem statement. Here you can see all the strings are starting from the symbol zero. That means these all strings are valid strings and our DFA should be able to accept all these valid strings and should be able to reject all the invalid strings. Now before designing the DFA, let me tell you three important steps that we will follow during the designing of our DFA. Step number one is you will need to select the simplest possible string from this language. And here you can see the simplest possible string out of the string is zero.

[00:02:20]In the step number two, you are required to draw the transition diagram to accept the simplest possible string. And the last step is you need to complete all the transitions for all the states in the DFA. So while constructing the transition diagram to accept the simplest possible string, there may be many missing transitions. So in step number three, we will complete those missing transitions. So now let's start designing our deterministic finite automator which will accept all the strings beginning with zero. So the step number one is select the simplest possible string and we already know 0 is the simplest possible string here. Why?

[00:03:07]Because 0 is of length 1 and the string 0 is also beginning with the symbol zero. Now in the second step we will draw the transition diagram to accept this simplest possible string. So first of all we will have our initial state that is Q not and on getting the input symbol zero it will reach the final state or the accepting state let's say Q1 because 0 is a valid string that is why it will be accepted. So we have completed our step number two in which we have drawn the transition diagram to accept the simplest possible string. Now in the step number three, we will try to complete all the missing transitions of this diagram. You can see that the state Q not has the transition for input symbol zero. But there is no transition for input symbol one. Similarly for the state Q1, the transitions for both input symbols 0 and 1 are missing. So let's try to complete all the transition.

[00:04:12]Let's start with state number Q1.

[00:04:16]At Q1, you can see zero is already processed. That means we have got our first symbol as zero. And according to the question, if the first symbol is zero, DFA will accept that string. So it doesn't matter what comes after that zero. So any combination of 0 and one will be accepted that will come after zero.

[00:04:41]So we will simply create a self loop for the symbol 0 and 1 over the state Q1.

[00:04:48]And in this way we have completed both the transitions for the state Q1. And now we will try to complete the transition for state Q.

[00:04:58]Here you can see Q not already has a transition for zero but doesn't have a transition for one. Now if we get the first symbol as zero the string is getting accepted. But if the first symbol is one then the string will get rejected. And to reject the string we will reach a state which is called as dead state and from dead state you can never go to the accepting state again because once the string starts with one it can never start from zero.

[00:05:32]So I hope this diagram is now clear to you. Now I think we have completed all the three steps of designing a DFA. So do you think this is a valid DFA?

[00:05:44]No, it is still not a valid DFA. Though we have completed the transitions for the state Q and Q1, but we also have the state Q2 and we have still not completed the transitions for the state Q2.

[00:05:59]Now if the first symbol is one it doesn't matter what comes after that because once the string is started from one it will be rejected. So after that if we get any other symbol we will still remain at the dead state and for this reason we will simply create a self loop for both the input symbols 0 and 1 over the state Q2. Now we can say that this is a valid DFA.

[00:06:27]So after designing the DFA I will write the five tuple representation of the DFA.

[00:06:33]Here we have the five tuple representation of DFA. Our DFA M is the collection of five elements Q, sigma, delta, Q not and F. These five elements are used to entirely represent a deterministic finite automator. Every part of this DFA can be represented using these five elements. Now let's see the values of these five elements. Q which we already know is the set of states. And in this DFA we have total of three states Q not Q1 and Q2. So the set Q will have three elements Q1 and Q2.

[00:07:17]Sigma is the set of symbols and we have only two symbols 0 and 1. So it has two elements 0 and one. Now delta is the transition function which is the collection of transition rules. In this DFA we have three states and two input symbols. That is why we will have total of six transitions.

[00:07:40]So Q not on getting input symbol zero the next state is Q1. Similarly Q not on getting input symbol one the next state will be Q2. Q1 on getting input symbol zero the next state is Q1 itself. So in this way I have written only three transitions and I want you all to write the remaining three transitions in the comment section. Now the next element is Q not which is the initial state of the DFA. And in this DFA Q not is the initial state. So the value of Q not is Q not. F is the set of final states. And in this diagram q1 is the only final state. So this set will contain only one element which is Q1. So by this we have completed with the five tuple representation of this DFA. Now we will quickly understand the construction of transition table for this DFA. Here is the transition table of this DFA. In the first column I have written the states that are Q, Q1 and Q2. In the first row I have written the input symbols that are 0 and 1. And in the remaining cells I have written the next states.

[00:09:00]So Q not on getting the input symbol zero will reach the state Q1. You can check Q not on getting the input symbol zero will reach the state Q1. Similarly, Q not on getting input symbol 1 will reach the next state which is Q2. Now Q1 on getting both the input symbols 0 and 1 will remain at the same state Q1 and similarly Q2 will also remain at the same state Q2 on getting input symbols 0 and 1. So in this way we have solved our problem number one in which we have written the language drawn the transition diagram then we have seen the five tuple representation of the DFA and after that we have constructed the transition table. So keep this thing in mind whenever you will encounter any question on DFA construction. First of all you have to write the language. Then you have to draw the transition diagram.

[00:09:59]Then you have to write the fivele representation of DFA and at last you need to construct the transition table for the DFA. So now let's proceed to our second problem which is design a transition diagram of a DFA that accepts all the strings ending with 1 0 over the alphabet 0A 1. That means in this problem we are required to design the transition diagram of a DFA that will accept all the strings ending with 1 zero. So our DFA should accept all the strings ending with 1 0 and should be able to reject the strings not ending with 1 0. So let's see the language for this problem.

[00:10:43]In this language you can see all the strings are ending with 1 zero. So these strings are valid strings and our DFA should accept these valid strings and should also reject the invalid strings.

[00:10:58]Now for designing the transition diagram of the DFA, we will follow the same steps that we have followed in the previous question. Step number one, select the simplest possible string. In these strings, the string 1 0 is the simplest possible string because it is the smallest and 1 0 is beginning with 1 0 as well as ending with 1 0. So this is going to be our simplest possible string. Now in step number two we will draw a transition diagram to accept this string 1 0. So first of all we will have our initial state that is Q not. On getting the input symbol 1 we will reach an intermediate state let's say Q1 and after reading the last symbol which is zero our whole string is processed now that is 1 0. So we will reach the accepting state that is Q2. In this way we have completed our step number two and we have drawn a transition diagram to accept the simplest string that is 1 zero. Now in the step number three we have to complete all the missing transitions of all the states. Q not has a transition for symbol one but doesn't have a transition for zero. Q1 has a transition for zero but doesn't have a transition for one. And Q2 doesn't have a transition for zero as well as one. So let's start with Q not in the question.

[00:12:27]We can see that our DFA should accept all the strings ending with 1 0. So if the string is ending with 1 0 we can have any number of zeros before that. It doesn't matter what comes before 1 0. If the string is ending with 1 0 so I will simply create a self loop of the symbol zero over the state Q not. In this way we have completed both the transitions for the state Q not. Now let's talk about the state Q1.

[00:12:59]Now Q1 has a transition for input symbol zero but it doesn't have a transition for 1. So if I get input symbol one at Q1, I need to remain at the same state so that my string ends with 1 0. And for the state Q2, I don't have any transition for 0 or 1. And you can already see that 1 zero is already processed. So if I get another zero after 1 0, it will destroy the whole pattern and I need to go back to the state Q not so that my string ends with 1 0. And if I get the input symbol 1, then I will go back to the state Q1 so that my string ends with 1 0. So this was the transition diagram for the problem number two.

[00:13:49]And now I'm not going to write the five elements of this DFA. But in examinations you are required to write the five tpple representation of the DFA after drawing the transition diagram.

[00:14:02]And here is the transition table for this DFA. And you can simply check the next states.

[00:14:08]So we have solved the problem number two. And now we will proceed to problem number three.

[00:14:15]Design a transition diagram of a DFA that accepts all strings having substring BAB over the alphabet A, B.

[00:14:25]That means our DFA should accept all the strings having BAB and should reject the strings which do not have Bab. So that means what comes before BAB and what comes after BAB doesn't matter. Your string should contain BAB. If we see the language you can see all the strings are the valid strings because in this string we have babab. In this string we also have babab. Here you can also see babab and in this string also you can see babab.

[00:14:58]In this string we have just bab. Here babab is at ending. Here babab is at starting. And in this string we have babab in somewhere middle of the string.

[00:15:08]That means the position of BAB doesn't matter. What comes before BAB and after BAB doesn't matter. It should just contain BAB. So now let's draw the transition diagram for this problem.

[00:15:21]So we'll select the simplest possible string which is B A B and we'll have our initial state that is Q not. On reading the input symbol B, we'll reach an intermediate state that is Q1. On reading the input symbol A, we'll reach again an intermediate state that is Q2.

[00:15:38]And after reading the last symbol which is B, our entire string is processed now that is B A B. So we'll finally reach the accepting state let's say Q3.

[00:15:49]Now I will complete the transition for all these states. Q not has a transition for B but it doesn't have a transition for A. And as per the question, our string should contain BAB. And if the string is already containing bab, it doesn't matter what comes before bab. So we can have any number of a. So for this reason, I will simply create a self loop of a over the state q not. Now for the state q1, I have a transition for a but I don't have a transition for b. So if I get input symbol B at Q1, I will remain at the same state so that my string contains B A B. For the state Q2, I have transition for B, but I don't have any transition for A. And you can see the string BA is already processed. So if I get the input symbol A, the string will be like B A A which will destroy the whole pattern. So I again need to go back to the state Q not so that my string contains BAB.

[00:16:54]Now for our accepting state Q3 we can see that the string BAB is already processed which means our string contains BAB. So what comes after BAB?

[00:17:06]It doesn't matter. So we can have any combination of A and B for the state Q3.

[00:17:12]And for this reason, we'll simply create the self loop for the symbols A and B over the state Q3. So this was the transition diagram for our problem number three. Now let's proceed to our problem number four.

[00:17:25]Design a transition diagram of a DFA that accepts all strings having length three over the alphabet A, B. Which means we are required to draw a transition diagram of DFA that accepts all the strings having length equal to three. Now length of a string I have already told you length of a string is defined as the number of symbols in that string. That means this DFA should only accept the strings which have number of symbols equal to three and it should reject the strings having number of symbols less than three or greater than three. So let's see the language.

[00:18:05]In this language you can see all the strings are having length equal to three. And this is an example of a finite language. In the last three questions we were having the infinite language. But here you can see that there are only eight strings having length three and that is why this is a finite language. Now we will start constructing our deterministic finite automator for this language. Here you can see that there is no particular simplest possible string because all the strings have the same length. So we will consider all the strings while designing our DFA. First of all we'll have our initial state which is Q not. And now we will read the first symbol. In these strings you can see the first symbol can be either A or B. So we can have the first symbol as either A or B and we will reach our state Q1. Again we will process the second symbol and the second symbol can also be either A or B. So we will read the second symbol which is A or B and we will reach the state Q2.

[00:19:14]Two symbols are already processed and now we are going to read the third symbol. In these strings the third symbol can also be either A or B. So we will read the third symbol which can be either A or B. And finally we will reach our accepting state that is Q3.

[00:19:33]So these three states will reject the strings having length less than three.

[00:19:37]And this state will accept the strings having length equal to three. But what about the strings having length greater than three. So if I read one more symbol from A and B, I will reach dead state because now the length of the string is greater than three. And at dead state, if I get any other symbol, the length of the string will still be more than three. So I will remain at the same state, which is the dead state. So this was our transition diagram. Now tell me, is this a complete DFA?

[00:20:13]Yes, this diagram is a complete DFA because for every state we are getting the transitions for both the input symbols. For example, for state Q not we are getting the transition for input symbol A as well as for input symbol B.

[00:20:29]And similarly for all the states we have both the transitions. So this is a complete and a valid DFA. And I hope you can simply construct the transition table for this DFA. In this way we are done with the problems on deterministic finite automator and in the next lecture we will solve few more varieties of problems on DFA. So this was all from my side for this lecture. Thank you and I'll see you in the next lecture.