Decidability | Lecture 24 | Prof. Ravindrababu Ravula

[00:09:53]Yeah.

[00:09:56]Okay. So, open the Telegram channel and answer this question.

[00:10:11]when the languages are given you don't have to use the properties you can directly get them right if you use the property this is CFL and you'll convert it to CFL and then you'll say L1 L2 equal to CFL right but that's wrong if I say a A L1 union L2 it is going to be A + B star if I say L1 union L2 it is going to be a plus B star which is regular which is regular right so let's see some pro properties on regular languages okay so if L1 is regular if L1 is regular and L2 is regular If L1 is regular and L2 is regular then we know that L1 union L2 is regular.

[00:11:16]How? Write the regular expression for L1. Write the regular expression for L2 and just put a plus. If L1 is regular and L2 is regular, then L1 union L2 is regular.

[00:11:30]Right?

[00:11:32]Now, now the question is if L1 union L2 is regular, if L1, L2 is regular, then what can you say about L1 and L2 is the question.

[00:11:49]What can you say about L1, L2? Is the question. Try to answer this. Try to answer this.

[00:11:56]Hello. Hello.

[00:11:59]What do you think?

[00:13:15]Okay. If L1 is then L2 is regular then L1 comma L2 may or may not be regular.

[00:13:26]L1 comma L2 may or may not be regular may or may not be regular.

[00:13:37]Right?

[00:13:39]Now if L1 intersection L2 is regular L1 intersection L2 is regular then L1 L2 may or may not be regular.

[00:14:08]If L1 concatenated with L2 is regular.

[00:14:18]If L1 concatenate with L2 is regular then L1 comma L2 may or may not be regular may or may not be regular. You give me all the examples for these cases. Okay, you have to give me all the examples for these cases. But one property is for is very important.

[00:14:46]If L is regular, if L is regular, L complement is regular.

[00:14:56]If L is regular then L power R is regular. Reversal of language is regular.

[00:15:10]Right? Similarly, if L power R is regular, L is regular. If L complement is regular, L is regular. Now I what I want is for these three cases, give me examples.

[00:15:23]Give me examples for these three cases.

[00:15:25]Okay.

[00:16:31]Try and give the examples for these three. Try and give the examples for these three.

[00:16:57]Don't remember.

[00:17:22]That's it.

[00:17:43]Please.

[00:18:23]didn't They got to do something.

[00:19:03]Yeah.

[00:19:04]Now let's talk about union.

[00:19:10]Okay. Now L1 L2 union of L1 L2 is regular. Then L1 and L2 need not be regular. Right? Let us write different cases. Now let's take the case when both are regular. Now let us say here we have a star. We here we have B star. Now what is L1 union L2? L1 union L2 is A* + B star. Therefore it is regular.

[00:19:42]Now let us take a case.

[00:20:00]Let us take a case where L1 is regular and L2 is non-regular.

[00:20:10]L1 is regular and L2 is non-regular.

[00:20:13]Okay. For example, I can write A + B star which is regular and I can write A power N B power N which is non-regular.

[00:20:24]Then if I say L1 union L2 then it is going to be A + B* and then that is it a + B star. If you union anything with universal language, you are going to get the universal language only.

[00:20:43]Right? If you union anything with universal language, you are going to get the universal language only. Now let's take not regular and not regular. Not regular and not regular. Right? So a power n bn n and a power n b power n complement are not regular.

[00:21:08]They are not regular. Right?

[00:21:16]Now union of two non-regular languages is nothing. See if I take a language and its complement and if I apply union then what do I get? L1 union L2 is A + B star. Right? So in all these cases L1 union L2 is regular. Last year they have asked this question in GATE. Last year they have asked this question in GATE.

[00:21:42]Okay.

[00:21:52]Now let's talk about intersection. Can you do this intersection?

[00:21:58]Intersection. Now L1 and L2 they can be regular.

[00:22:04]They can be regular.

[00:22:06]Right? For example, if I write AAR here, B star here. Then what is L1 intersection L2? Only epsilon is present in both of them. Only epsilon is present in both of them. Right? Now regular and non-regular regular and non-regular.

[00:22:29]So phi is regular and a power n b power n is non-regular.

[00:22:38]If I take the intersection I'm going to get five and five is regular.

[00:22:44]Five is regular. Now L1 and L2 can be non-regular right? L1 and L2 can be both of them can be non-regular. For example, A power N b power N and A power N B power N whole complement whole complement. Right? Now L1 intersection L2 is equal to 5 which is regular which is regular.

[00:23:14]Right?

[00:23:16]And we know that if L is regular then L complement is also regular.

[00:23:32]If L complement is regular then L is regular. Right? Now regular so regular languages are closed under complementation.

[00:23:47]regular languages are closed under complementation.

[00:23:54]Regular languages are closed under closed gender complementation.

[00:24:13]So what does that mean? Regular language are closed complementation means L comma L complement L comma L complement are both are both regular or L comma L complement are both non-regular.

[00:24:39]They are both regular or they are both non-regular.

[00:24:47]Right.

[00:24:48]Right.

[00:24:55]Now one thing you have to understand is when you do complementation regular is closed.

[00:25:04]I'll do in a separate page. Okay. When you talk about complementation, when you talk about complementation, so one thing that you have to understand is if a language L is there which is regular DCFL CSL and REC regular DCFL CSL and this is a very frequently asked question that is why I'm giving you separately actually this is in RBI table one okay actually this is in RBI table one so if I take complementation of a regular I mean language. If it is regular result will be regular. If it is DCFL result will be DCFL. If it is CSL register will be CCL CSL and if it is result will be.

[00:26:20]So what are the various points can we write about it?

[00:26:25]So what are the various points can we write about it?

[00:27:17]What are the points can you write about it? I'm seeing your WhatsApp channel, sorry, Telegram channel.

[00:27:27]What are the points that you can write about it?

[00:28:12]right? So you can say that you can say that L and L complement both are regular. If L is regular, L complement is regular. Both are regular or both are non-regular.

[00:28:35]This point you can say this is as in gate. Okay. Now L and L complement both are DCFL or both are non DCFL.

[00:28:58]Non DCFL. Right. Right.

[00:29:41]Similarly, you can say L and L complement both are CSL or both are not CSL.

[00:29:58]Similarly you can say L and L complement both are recursive or both are not recursive. Both are not recursive.

[00:31:25]groups Okay fine.

[00:31:51]Now same thing can be applied to closure also. clean closure also.

[00:31:57]Right. Right. Now let us say L = A power N² such that N is greater than or equal to 1. L= A power N² such that N is greater than or equal to 1.

[00:32:16]Right?

[00:32:19]Now this language is non-regular because we don't have a linear power. The language is non-regular.

[00:32:28]Now what is Lar?

[00:32:32]What is Lar?

[00:32:36]What is Lar?

[00:32:39]Let us say the L square, right?

[00:32:46]What is Lar?

[00:32:49]Can someone answer this in the telegram channel?

[00:32:55]Can someone answer this in the telegram channel?

[00:33:28]Oh no, phone number.

[00:34:01]Okay. Now let's see what is L. In place of N if you put one it is a. In place of N if you put one it is a power 4. In place of N if you put three it is a power 9. In place of n if you put four it is a power 16 so on right now what is lar applying a star to this now when I apply star we can repeat all these any number of times therefore a will also be repeated any number of times since star is there if I put a zero epsilon is in the language and a can repeat any number of times therefore you are going to get a star.

[00:34:46]Very good.

[00:34:49]Very good. Nsw answer is a star.

[00:34:55]Now answer this question.

[00:34:59]L = a power 2 power n such that n is greater than or equal to 1.

[00:35:10]Now what is lar?

[00:35:13]What is Lar?

[00:35:15]a power two power n such set n is greater than or equal to 1. What is lstar?

[00:35:41]Try it everyone.

[00:35:43]Not very easy, but you can try it.

[00:36:11]solve.

[00:36:16]So guys, now what is L?

[00:36:19]In place of N, if you put one, it is going to be a power 2. In place of N, if you put two, it is going to be a power 4. In place of N, if you put three, it is going to be a power, right? If you put four it is going to be a power 16 so on. Now if I put a star here and if I put a star here. Now if I put a zero in place of star I'll get epsilon.

[00:36:48]Now if you see this a square can be repeated any number of times. It is not a it is a square which will be repeated any number of times. Therefore the answer is a a star.

[00:37:01]Therefore the answer is yeah a star.

[00:37:05]So what did you observe here? What did you observe here? See if a language is regular. Let me write language L1.

[00:37:19]If a language L1 is regular then if a language L1 is regular then then L1 star is regular.

[00:37:40]L1 star is regular.

[00:37:43]Similarly, if a language L1 is non-regular, then L1 star then L1 star may or may not be regular.

[00:38:06]may or may not be regular.

[00:38:13]May or may not be regular.

[00:38:17]Right? Now, what do you mean by decidability?

[00:38:22]If for a problem, if for a problem, if an algorithm exists, if for a problem an algorithm exists, then we can say that the problem is decidable.

[00:38:37]Right? If for a problem an algorithm exists, we can say that it is decidable.

[00:38:44]Right? Now, there are lot of questions on this table. Now we are going to discuss something called as RBR table 3.

[00:38:54]You have seen RBR table one. RBR table two. I asked you to apply table two first then table one. Now the table three.

[00:39:03]I think we have seen RBI table three also. This is table number four.

[00:39:08]We have seen three tables. Right? We have seen three tables. This is table number four. And this table is about decidability. Lot of questions.

[00:39:22]Lot of questions have come in this.

[00:39:25]Lot of questions have come in this decidability.

[00:39:29]Lot of questions have come in this. If you can remember this table, it is very easy to score two marks right. So first I will write the table. You just give some gaps. Okay? Don't write it because you don't know how to give the gap. I will write the table and I will give you the time to write. Okay, I will write the table. You don't know how much space to give. Just let me write the table.

[00:39:55]Okay.

[00:39:57]Membership, emptiness, finitness, equivalence, regularity.

[00:40:24]Ambiguity, completeness, disjointness.

[00:40:49]Just see how big the table is going to be. Later you copy it. Don't draw it now because you may not have enough space allotted. So just see how I am doing it.

[00:41:02]Then you can copy this. Okay, I'll give you time. Okay. Now the languages are regular.

[00:41:12]We don't have DCFL. We have CFL.

[00:41:20]We have CFL and we have CSL and we have REC and we have RE and we have RE right so this is decidable decidable decidable decidable and undecidable And this is decidable. Decidable.

[00:41:54]Undecidable. Undecidable.

[00:41:58]Undecidable.

[00:42:00]And this is decidable. Decidable.

[00:42:05]Undecidable.

[00:42:07]Undecidable.

[00:42:08]Undecidable.

[00:42:11]Decidable means there is algorithm.

[00:42:14]Undecidable means there is no algorithm.

[00:42:16]Now equivalence decidable undecidable undecidable undecidable undecidable.

[00:42:29]Now regularity decidable undecidable undecidable undecidable undecidable ambiguity.

[00:42:46]Decidable.

[00:42:48]Undecidable.

[00:42:49]Undecidable.

[00:42:51]Undecidable.

[00:42:52]Undecidable.

[00:42:56]Completeness.

[00:42:58]Decidable.

[00:43:00]Undecidable. Undecidable.

[00:43:03]Undecidable.

[00:43:05]Undecidable.

[00:43:07]Undecidable.

[00:43:09]Undecidable.

[00:43:10]Undecidable. Undecidable. Right. How will the question be asked? Given a string, does it belong to the language that is membership?

[00:43:20]Given a language, is it equal to five empty?

[00:43:27]And is L finite?

[00:43:31]Is L finite?

[00:43:37]What about equivalence?

[00:43:39]Is L1 = L2?

[00:43:44]What about regularity?

[00:43:46]Is L = R? What about ambiguity? Is L ambiguous? What about completeness?

[00:43:58]Is L = sigma*?

[00:44:02]What about disjointness? Is L1 intersection L2?

[00:44:08]Is L1 intersection L2?

[00:44:13]Write the table. Take time and copy the table.

[00:48:22]Okay.

[00:48:24]So most of the table is undecidable. If you see this only this part and this part is decidable. Most of the table is undecidable. Okay. This is also decidable. Okay. So whenever they give an exam in the exam you can directly answer that it is undecidable. Okay. You can directly answer that it is undecidable.

[00:48:51]Right.

[00:48:53]Now let us see various applications of finite automator.

[00:48:59]Let us see various applications of finite automator.

[00:49:11]Various applications of finite automata one is lexical analysis. So in compiler design we are going to use lexical analyzer and second one is text editors. We have various text editors right there. Finite automata is used for what? Per search.

[00:49:41]And there is a command called grapin Unix that uses regular expressions.

[00:49:47]And then auto suggestions.

[00:49:50]For auto suggestions also for auto suggestions also regular expressions are used.

[00:50:02]Right.

[00:50:06]And then third one is in digital you are going to see something called as sequential circuits.

[00:50:15]Sequential circuits or circuit there we are going to use mur and millie. Mur and mele are not over. Okay.

[00:50:32]Mle and Mia are not over. Now let us see various variations of finite automator.

[00:50:40]A finite automator can have many variations.

[00:50:46]Variations of finite automator. Right?

[00:50:50]One is multitape finite automator.

[00:50:55]Multitape finite automator. Right? What do I mean by multitape finite automator? We have a finite automator with finite number of states. But input can be in multiple tips.

[00:51:12]Input can be in multiple tips.

[00:51:16]Right? Now you can see one symbol from each state and you can decide. Okay.

[00:51:24]Okay. But then it is found out that multi-state multi-ave finite automator has same power as finite automator.

[00:51:34]It has same power as finite automator.

[00:51:40]And then multi- heads finite automator.

[00:51:46]Multi- head finite automator. So what does this mean? If you have a If you have a finite automator, If you have a finite automator, these are the states, then it can have multiple heads.

[00:52:06]It can have multiple heads.

[00:52:11]Similarly, finite automator with read write head.

[00:52:22]Finite automator with read write head.

[00:52:24]So what does this mean? You have a finite automator.

[00:52:32]You have a finite automator.

[00:52:35]And then you have read write head.

[00:52:41]Read right head.

[00:52:47]And then we have finite automator which can move both the sides. Generally finite automator moves in only one side.

[00:52:54]Right? But it can move right or it can move left. Even this has same power as finite automator.

[00:53:05]Same power as finite automator.

[00:53:10]Same power as finite automator. Right.

[00:53:26]Now to the finite automator.

[00:53:30]To the finite automator.

[00:53:33]If I allow it to read and write and if it can move right or left then this will become cheuring machine.

[00:53:44]Then it will become cheuring machine.

[00:53:49]Now per finite automator if I add one stack per finite automator if I add one stack then it will become push down automator and we know that cheuring machine is more powerful than finite automator and push down automator is more powerful than finite automator and also cheuring machine is more powerful than finite automator. If you want to write all of these three, curing machine is more powerful than push down automator is more powerful than finite automator.

[00:54:32]Finite automator.

[00:54:35]Right? Now there is a different machine which does not have a name. Okay? Now let us say finite automator plus one counter.

[00:54:48]finite automator plus one counter. So what do I mean by one counter?

[00:54:54]One counter is a stack with only one symbol.

[00:54:58]One counter is a stack with only one symbol.

[00:55:09]One counter in a stack with only one symbol. You can put any symbol but only one symbol. Like you can put only one one one.

[00:55:19]Now this machine doesn't have any name.

[00:55:22]Let us call it as X. We don't have any name. Let us call it as X. Right? Now X is more powerful than finite automator.

[00:55:31]And X is less powerful than pushdown automator. And X is more powerful than finite automator.

[00:55:40]Less powerful than pushon automator.

[00:55:44]Right now using this counters concept you can extend it a little bit. Okay. So finite automata plus two counters.

[00:55:55]Finite automator plus two counters is cheing machine. Even if you add more counters plus three counters is also chewing machine plus four counters is also cheing machine. So on so on so on right now let's talk about the last concept of to so probably today to is going to be over okay today to is I mean sorry lost concept of regular regular languages today we are going to finish it take a quick break for 3 4 minutes Then we will see Mur and Millie with this regular languages is completed. We have to do PQS. Okay.

[00:56:49]Probably this Sunday we will do PQs or I will take PQ session on a weekday on weekdays every day. Okay. Fine.

[00:57:03]Take break for 3 minutes. Okay.

[00:59:22]Okay.

[00:59:48]What?

[01:02:07]Now let's look at mur and mele machines.

[01:02:10]Okay.

[01:02:12]So let's look at mur machines first.

[01:02:17]Murray machines.

[01:02:20]Okay.

[01:02:22]So I'll just with examples it will be clear. Okay.

[01:02:28]Construct a mur.

[01:02:34]Construct a mur.

[01:02:41]Construct a murray machine that takes that takes set of all strings set of all strings over set of all strings over a comma b set of all strings over a comma b and and prints and prints one as output and prints one as output. For every occurrence of For every occurrence of For every occurrence of AB as a substring AB as a substring for every occurrence of AB as a subspring, right? How are you going to do this? Tell me in the telegram channel.

[01:03:59]How are you going to do this? Tell me in the telegram channel.

[01:06:14]Google.

[01:06:30]>> Okay. So whenever you get a a you are going to print one. Okay. So how can I make sure that so you have to make sure that whenever you get a a b you have to reach a state right so you see this a b I will reach this state okay I will reach this state now the question is even if I get one more ab again I have to reach this state so what I will do is if I get a a I'll go back and once I get a AB I'll reach this state and any number of B's I will wait for a A and any number of A I will wait here till I get a B so let us say this is state A output is zero this is state B output is zero this is state C output is one now this is nothing but ending with so if I get a B I have to wait for entire AB so this is nothing but finite automator which accept set of all strings ending with AB. This is nothing but finite automator where set of all strings are ending with AB.

[01:07:48]Finite automator where set of all states are ending with AB.

[01:07:57]Right?

[01:08:03]So how do you trace it? Now let us say you have ab a b two abs are there. So you are supposed to get two ones.

[01:08:12]Initially you'll be in state a output is zero. Now on seeing a a you'll go to b output is zero. And on seeing a b you go to c output is 1. And on seeing a a you'll go to A output is zero you'll go to B right C on seeing a A will go to B and B on seeing a B will go to C and output is one which means whenever you see A a B you are printing a output one whenever you see a AB you are printing a output one right right now what if I change the question a little bit.

[01:08:58]What if I change a question a little bit and say for every occurrence of BAA for every occurrence of BAA?

[01:09:20]For every occurrence of BAA, Okay.

[01:12:40]So it has to end with BAA. Whenever you get a BA, one should be output, right?

[01:12:48]So whenever you get B A output should be one. So for A output is zero. For B output is zero. For C output is zero. For D output is one.

[01:13:09]For D output is one.

[01:14:00]Okay, this is ending with B AAA. Now any number of A may come, I will wait for a BA. Now here any number of B's may come, I'll wait for a AA. Right? Now here I want BA. If a A comes, I go here. If a B comes, I'll go back and wait for a AA.

[01:14:21]Here if a A comes, I have to wait for entire B AAA.

[01:14:27]Here if a B comes, I had to wait for AA.

[01:14:33]I had to wait for AA.

[01:14:36]Right? Now let us say the string is B A followed by B A A. Now initially you'll be in state A output will be zero.

[01:14:50]Now from state A on seeing a B you'll go to B output will be zero and from B on seeing a A you'll go to C output will be zero and C on seeing a A will go to D output will be one. Which means when I see B a A output is getting one. Now from D if I get a B I will go to B and output will be zero. From B if I get a A from B if I get a A from B if I get a A I will go to C.

[01:15:32]I'll go to C and output will be zero.

[01:15:34]from C if I get a A I'll go to D and output will be zero right so for every occurrence of BA we got one now one thing that you have to notice in mur is if the input is n symbols then the output will be n +1 symbols this one you have to remember if the input is n symbols output will be n +1 symbols see this 1 2 3 4 5 6 1 2 3 4 5 6 7 Right.

[01:16:05]Right. Right.

[01:16:30]Okay.

[01:16:36]Now tell me about this.

[01:16:39]Tell me about this. Okay. Take time and do it. It is not easy.

[01:16:44]Construct.

[01:16:47]Construct a mur.

[01:16:52]Construct a murray machine that takes Construct a Murray machine that takes set of all strings.

[01:17:05]Set of all strings.

[01:17:10]Set of all strings over over 0 comma 1 over 0 comma 1 and produces and produces a as output and produces a as output. If If input If input ends with 1 0 If input ends with 1 0 if input once with 1 0 or produces or produces B as output produces B as output.

[01:18:08]If if input if input ends with 1 one if input ends with 1 one or produces or produces C otherwise or produces C otherwise produces C otherwise produces C otherwise That's it.

[01:26:24]Okay, construct a murray machine that takes set of all strings and produces a as output. If input ends with 1 zero and if it runs with 1 one, it is going to produce b right otherwise it is going to produce c. So c is the output. If in the beginning let any number of zeros come we will not do anything. Now once I get a one then I may get a one ending with one or I may get a zero ending with zero.

[01:27:00]Right?

[01:27:02]If the input ends with 1 0 let's see this. So if the input ends with 1 0 A has to be produced and if the input ends with 1 1 B has to be produced otherwise C has to be produced.

[01:27:20]Now remember one thing both the Millie machines and Murray machines are DFS not NFS. Okay both the Mur and Millie machines are DFS not the NFS.

[01:27:34]Okay fine. Now if I get a zero here it will be ending with 1 zero. Any number of ones it will be ending with 1 1. Now here if I get a zero it is actually 1 0 0. Now again I have to wait for entire 1 0 or 1 1. So if I get a zero I'll go back and wait for 1 0 or 1 1. Now if I get a 1 0 1 I have to wait for either 0 or 1. If I get a 1 0 1, I have to wait for 0 or 1, I have to wait for 0 or 1. So this is the mur machine for the question.

[01:28:17]Right now I'll give you one question.

[01:28:20]You try to solve it. Construct a mur.

[01:28:27]Construct a mur.

[01:28:32]Construct a murray machine that takes Construct a Murray machine that takes binary numbers that takes binary numbers as input.

[01:28:51]Binary numbers as input and produces and produces residue residue modulo 3 and produces residue modulo 3. Which means when I divide the number whatever remainder we are getting that residue has to be printed. Now assume epsilon is divisible by 3.

[01:29:30]Assume epsilon is divisible by 3. Try to answer this question.

[01:29:36]Try to answer this question.

[01:30:20]time >> YouTube community as well as um what the app notifications Telegram.

[01:32:56]I'm sorry.

[01:34:41]Why no one is able to do this?

[01:34:44]You have to divide a number by three and you have to just put the remainder.

[01:34:49]Right?

[01:34:51]Why is no one able to do this?

[01:34:54]See this I'll do. See this I will do.

[01:34:57]Okay. So we know divisible by three.

[01:35:02]Binary number divisible by three. Right?

[01:35:05]We have seen it many times. 0 1 1 0 0 1 1.

[01:35:21]Right? So this is the DFA. Now the remainder in this state is zero.

[01:35:28]Remainder in this state is one. element in the state is two that outputs will be printed or if you want to do it in a faster way. If you want to do it in a faster way, you can also write like this. There are three states Q1 Q2. Right? Now there are two two inputs 0 and 1. So Q1 Q2 Q1 Q2 and now output output can be zero here, one here and two here. Right? If you write like this, it will be direct and simple.

[01:36:09]If you write like this, it will be direct and simple. Right? Now solve one more question.

[01:36:22]Base four number modulo Okay.

[01:36:48]It takes base four number, right? and produces residue modulo five assuming epsilon is divisible by five.

[01:37:03]Try doing this.

[01:37:05]Try doing this.

[01:39:31]Okay, you can use the table method, right? Table method will be faster. So when I divide a number with five, how many remainders do I get? Q, Q1, Q2, Q3, Q4. And Q not is the final state. Q not is the final state. Right? Now this is a base four number which means 0 1 2 3. So you are going to write Q1 Q2 Q3 Q4 and again Q1 Q2 Q3 Q4 and again Q1 Q2 Q3 Q4 and again Q1 Q2 Q3 Q4 Right? Now what will be the output?

[01:40:33]Output is going to be for Q not it is 0.

[01:40:36]For Q1 it is 1. Q2 it is 2. Q3 it is 3.

[01:40:40]Q4 it is 4. 0 1 2 3 4.

[01:40:46]0 1 2 3 4. Simple right? Simple right?

[01:40:54]Now let us see Millie.

[01:40:56]Let us see one or two problems on Millie as we have time.

[01:41:01]Okay, Millie.

[01:41:11]So in mur output is associated with this state. In millie machine output is associated with the transition. What do I mean by that? If you look at the previous problems, if you look at the previous problems here, every state is getting the output, right? That is about mur. Now coming to me, every transaction, every trans transition will get a output. Every transition will get a output. Right? Now do this simple one. Construct Construct a Millie machine.

[01:41:51]Construct a millie machine that takes Construct a Millie machine that takes That takes binary numbers that takes binary numbers as input.

[01:42:13]binary numbers as input and produces and produces once complement as output and produces once complement as output.

[01:42:33]So we are done. This is the last topic.

[01:42:35]Okay, we are done with regular languages.

[01:42:38]Probably in one more class I will I will tell you about Okay. So what is once complement?

[01:46:08]Whenever there is zero, you are going to make it one. Whenever there is one, you are going to make it zero. Simple. Let us say state A is there. Whenever there is zero, you'll make it one. And whenever there is one, you'll make it zero. Right? For example, if I have the string 1 0 1 0. Right? Now I'll be in the state A and if I see a one I'm going to make it zero. I'll be in state A. If I see a zero I'll make it one. I'll be in state A. If I see a one I'll make it zero. I'll be in state A. And if I see a zero I will make it one. Simple, right?

[01:46:44]Okay. We will end the class here. There are few more problems in millie machine.

[01:46:49]Okay.