Mealy Machines

[00:00:00]Hello everyone. Welcome to Nesso Academy. We are learning theory of computation and in the previous lecture we have understood a basic introduction of finite automata with output. And today in this lecture we are going to start with the very first type of finite automata with output. That is Mealy machines. So the topic for this lecture is Mealy machine. Let's get started.

[00:00:30]Mealy machine is a finite state machine in which output depends on the present state and the current input symbol.

[00:00:41]What does that mean?

[00:00:42]It means that Mealy machine is a type of finite state machine or you can say Mealy machine is a type of finite automata with output in which output depends on the present state and the current input symbol.

[00:01:01]So the output in Mealy machine depends on the present state and the current input symbol.

[00:01:09]Let's look at this diagram.

[00:01:11]Zero and one are the output symbols while A and B are the input symbols. Now the present state Q0 and the current input symbol A determine the output symbol zero.

[00:01:27]Similarly the present state Q0 and the current input symbol B determine the output symbol one.

[00:01:35]The present state Q1 and the current input symbol A determine the output symbol zero. Similarly the present state Q1 and the current input symbol B determine the output symbol one. Which means the present state and the current input symbol determine the output symbol. Which means that output depends on the present state and the current input symbol.

[00:02:05]In case of DFA, I have explained you that present state and the current input symbol determine the next state.

[00:02:14]Similarly, in case of Mealy machines also, present state and current input symbol determine the next state. But additionally, present state and current input symbol also determine the output symbol. Like in this diagram, the present state q0 and input symbol b determine the next state, which is q1.

[00:02:37]But it also determine the output symbol, which is one.

[00:02:42]I hope this is clear now.

[00:02:45]Now, if you look at this diagram, you will find that on every transition, we have input {slash} output.

[00:02:55]So, we can say that transition label format, this particular transition label format, is input {slash} output. That means first, you will write the input symbol.

[00:03:09]Then there is a {slash}. Then you will write the output symbol. This is a particular format for transition in case of Mealy machines.

[00:03:19]I hope the transition diagram of Mealy machine is clear to you.

[00:03:23]Now, let's understand how to construct the transition table of Mealy machine.

[00:03:30]This is the basic structure of transition table of Mealy machine.

[00:03:35]Now, here you can see this column is for present state.

[00:03:39]And the present states are q0 and q1.

[00:03:42]So, in this column, we will write q0 and q1.

[00:03:46]Obviously, q0 is the initial state. And q1 is just an ordinary state of Mealy machine.

[00:03:53]As I have already explained you, in case of finite automata with output, there is no final or accepting states. That is why in this diagram, we don't have any final state.

[00:04:06]Now, we have two columns for input symbol A and input symbol B.

[00:04:12]And as I have just explained you, the next state and the output is dependent on the present state and the input symbol. So, the present state and the input symbol will determine the next state. Similarly, the present state and the input symbol will also determine the output symbol.

[00:04:35]Now, we have to fill these cells. Let's start with our very first state, which is Q0. So, Q0 and input symbol A.

[00:04:45]Q0 and input symbol A, the next state is also Q0. So, here we will write Q0. And Q0 and input symbol A, the output symbol is zero. So, here we will write zero.

[00:05:00]Now, Q0 on input symbol B.

[00:05:03]So, Q0 on input symbol B, the next state is Q1 and the output symbol is one. So, here we will write Q1 and output symbol is one.

[00:05:14]Now, let's talk about the state Q1. This is the state Q1. Q1 on input symbol A.

[00:05:22]So, Q1 on A gives Q1 and output symbol zero. So, here we will write Q1 and output symbol zero.

[00:05:31]Now, let's talk about the input symbol B.

[00:05:34]So, Q1 on the input symbol B, the next state is Q0 and the output symbol is one. So, the next state is Q0 and the output symbol is one.

[00:05:45]This is how we have the transition table for Mealy machine.

[00:05:51]I hope you have now understood how to construct the transition table from the transition diagram of Mealy machine.

[00:05:59]Now, let's understand the six-tuple representation of Mealy machine.

[00:06:05]So, the basic six-tuple representation of finite automata with output, I have already explained you in the previous lecture.

[00:06:14]Let's understand all these elements one by one.

[00:06:18]In the previous lecture, I have explained you that Q is simply the set of states that we have in our transition diagram.

[00:06:26]Sigma is the input alphabet, which is the set of input symbols.

[00:06:31]Capital delta is the output alphabet, which is the set of output symbols. In that particular diagram, A and B were the input symbols, and 0 and 1 were the output symbols.

[00:06:43]Delta is the transition function, and this is same as the transition function of a DFA.

[00:06:49]That is, for present state and the current input symbol, we determine the next state. So, the next state is dependent on the present state and the current input symbol.

[00:07:01]Now, lambda is the output function.

[00:07:04]And in the previous lecture, I have explained you that lambda or the output function is different for both Mealy machines and Moore machines. So, in Mealy machine, output function is represented using this particular equation. That is, lambda Q cross sigma gives us delta. What does that mean?

[00:07:29]Q is the present state, delta is the input symbol, and from the present state and the current input symbol, we determine the output symbol.

[00:07:39]That I have just explained you.

[00:07:41]So, present state and current input symbol will determine the output symbol.

[00:07:47]So, in case of Mealy machine, the present state and the current input symbol will determine the next state as well as the output symbol.

[00:07:56]Now, Q0 is the initial state of the Mealy machine.

[00:08:01]Now, it is to be noted that this cross represents the cross product, which means for every present state, there should be a transition for every input symbol, which is same as that of a DFA. So, this condition of Mealy machine is same as that of a deterministic finite automata.

[00:08:22]I hope the six-tuple representation of Mealy machine is now clear to you.

[00:08:27]Now, let's find out the values of each of these elements one by one.

[00:08:33]So, now let's find out the values of Q, sigma, capital delta, small delta, lambda, and Q0 with respect to this particular diagram of a Mealy machine.

[00:08:46]Let's first find out the values of Q, sigma, capital delta, and Q0.

[00:08:54]So, Q is equal to Q0, Q1. As you can see in this diagram, we have only two states, Q0 and Q1.

[00:09:02]And this capital Q means the set of states.

[00:09:06]So, we will have only two states in this particular set, that is Q0, Q1.

[00:09:12]Now, let's talk about sigma. Sigma is the input alphabet, which is the set of input symbols. And I have explained you that there are only two input symbols in this particular case, A and B.

[00:09:24]So, sigma is equal to set of two symbols, A and B.

[00:09:28]Similarly, output alphabet delta is the set of output symbols. And in this particular diagram, we have two output symbols, 0 and 1. So, delta is equal to the set of 0 and 1.

[00:09:43]Now, Q0 is the initial state, and in this particular case, the initial state is Q0 only. So, Q0 will be equal to Q0.

[00:09:52]Now, let's find out the values of transition function.

[00:09:57]So, these are the values of transition function, which is basically the set of different transition rules.

[00:10:06]So, delta Q0, A is giving us Q0.

[00:10:10]Q0 on A is giving us Q0. Q0 on B is giving us Q1. Q0 on B is giving us Q1.

[00:10:18]Q1 on A is giving us Q1 itself. And Q1 on B, Q1 on B is giving us Q0.

[00:10:27]So, these are all the transition rules, and collectively all the transition rules is called as the transition function.

[00:10:35]Basically, the present state and the current input symbol determine the next state.

[00:10:42]This is what the transition function is.

[00:10:44]Now, let's find out the values of output function.

[00:10:49]So, these are the values of output function. As I have explained you, the present state and the current input symbol determine the output.

[00:10:59]So, Q0 on A gives the output 0. Q0 on A gives the output 0. Q0 on B gives 1. Q0 on B gives 1.

[00:11:10]Q1 on A gives 0. Q1 on A gives 0.

[00:11:16]Q1 on B gives 1. Q1 on B gives 1. So, the present state and the current input symbol determine the output symbol.

[00:11:27]I hope the six-tuple representation of Mealy machine is now clear to you.

[00:11:34]Now, let's talk about input to output generation in case of Mealy machines.

[00:11:41]I have explained you that in case of finite automata with output, we give a particular input string and finite automata with output transduce or translate that input string into the corresponding output sequence.

[00:11:58]So, now we are going to understand how an input string is converted into its corresponding output sequence.

[00:12:06]So, for this particular diagram, I have taken an input string a b b a. And now we will translate this input string into its corresponding output sequence with the help of this diagram of Mealy machine.

[00:12:22]Let's start with the initial state, which is q0. So, first we will write the initial state, that is q0.

[00:12:29]Now, q0 is the initial state and the first input symbol is a. So, the first input symbol is a and now q0 on a.

[00:12:40]So, q0 on a gives q0. So, the next state is also q0.

[00:12:47]What is the output symbol?

[00:12:49]q0 on a, the output symbol is zero. So, here we will write zero, which is the output symbol.

[00:12:56]Now, the next symbol is b. The next input symbol is b. So, q0 on b. Let's check.

[00:13:05]q0 on b gives q1.

[00:13:08]So, we will write the next state, which is q1.

[00:13:13]Now, let's see the output symbol.

[00:13:15]q0 on b, the output symbol is one. So, here we will write one.

[00:13:21]Now, the next input symbol is b.

[00:13:24]So, we will check q1 on B.

[00:13:28]So, Q1 on B gives the state Q0.

[00:13:33]So, we will get Q not. Let's see the output. Q1 on B gives the output 1.

[00:13:41]So, here we will get 1 as the output symbol.

[00:13:45]Now, the last input symbol is A.

[00:13:47]So, Q0 on A will give us Q0 on A will give us Q0.

[00:13:55]So, we will get Q0.

[00:13:57]And the output symbol, Q0 on A, the output symbol is 0.

[00:14:02]So, output symbol we will get 0.

[00:14:04]So, finally we are getting the output string as 0 1 1 0. So, for the input string A B B A, the output string is 0 1 1 0.

[00:14:16]And if you clearly observe, you will find that on getting the input string of length n in Mealy machine, the output is also of length n.

[00:14:29]What is the length of input string? 1 2 3 4. 4 is the length of input string.

[00:14:35]Then, what is the length of output string? 1 2 3 4.

[00:14:39]4 is also the length of output string.

[00:14:42]That means, in case of Mealy machine, if the input string is of length n, then output string is also of the length n.

[00:14:51]That is what we can conclude from input to output generation for Mealy machine.

[00:14:57]And in this way, we are done with our topic Mealy machine.

[00:15:01]I hope you have understood this topic perfectly.

[00:15:05]Now, in the next lecture, we will understand Moore machine in detail. So, this was all from my side for this lecture. Thank you, and I'll see you in the next lecture.

[00:15:18]>> [music] >> Mhm.