Automata Tutorial

What is Automata What is Automata theory Finite Automata Minimization of Finite Automata Conversion from NFA to DFA using Transition diagram Finite Automata with output Minimization of Finite Automata with output Conversion From Moore Machine to Mealy Machine Conversion From Mealy Machine to Moore Machine What do you mean by Regular Expression? Conversion from DFA to Regular expression Converting Finite Automata to Regular Conversion using Arden’s Theorem Pumping Lemma for Regular Languages Closure Properties of Regular Languages What do you mean by Context Free Grammar? Derivation Tree of Context Free Grammar What do you mean by Ambiguity in Context Free Grammar? Simplification in Context Free Grammar Chomsky Normal Form Greibach Normal Form Pumping Lemma for Context Free Languages Push Down Automata Non-deterministic Turing Machine Grammar in Automata How to Construct DFA NFA to Regular Expression Recursive Grammar in Automata Recursive Grammar in Automata Grammar in Automata | Types of Grammar How to Construct DFA? Expression Parsing

Conversion from Mealy Machine to Moore Machine
2020-12-27 08:16:23

Conversion from Mealy Machine to Moore Machine

Conversion from Mealy Machine to Moore Machine

In this topic, we will see different ways that are used for the conversion of Mealy Machine to Moore Machine.

Moore Machine

The output of Moore machine depends only on the present state of the machine. In Moore Machine, if the input string is of length n, then the generated output string will be of length n+1.

Mealy Machine

In Mealy machine, value of output function depends on the current state and current input. In mealy machine, if the input string of length n, then the generated output string will also be of length n.

Methods used for conversion of Mealy Machine to Moore Machine

Following are the two methods that are used for converting a Moore Machine to Mealy Machine:

  • Converting a Mealy Machine to Moore Machine using transition diagram
  • Converting a Mealy Machine to Moore Machine using transition table

Converting a Mealy Machine to Moore Machine using transition diagram

In this method, we convert the Mealy Machine to Moore Machine using transition diagram of Mealy machine:

Following steps are used to convert Mealy Machine to Moore Machine:

Step1: Start from initial state q0.

Step2: Check how many edges are entering into that state.

Step3:  If any edge has different output, then make copy of that state. Let say, one edge has output a, and another has output b, then we make the copies of state q0 to q0’/a and q0’’/b corresponding to the output a and b. As we have assumed that q0 is the start state, and we make copies of it, which means from initial state q0, we got two states q0’ and q0’’.

Now any one of them can be used as start state of Moore machine M, because they give identical direction for processing to other states.

Step4:  If the edges have same output, then do not make copies, instead just remove output from edges and put the output in the state. Suppose two edges are entering in q0 have same output, say a, then we put the output a into state q0 and relabel it without output.

Step5: Now check if the state has a loop. If the sate loop is labelled with 1/b, then two copies of q0 (q0’/a and q0’’/b) are connected by an edge labelled 1 from q0’ to q0’’.  Also add a loop labeled 1 on state q0’’.

Step6: If there are no edges entering into the state then we can assign it any output.

Step7: Repeat above steps for all other states.

Example

Convert the following Mealy machine to Moore machine using transition diagram.

Solution:

In this method, we will convert the mealy machine to Moore machine by using the transition diagram of mealy machine.

We start form initial state q0. Two edges are entering in this state. One edge is labelled 1/b, and another is labelled with 1/a. Therefore, we create two copies of q1, one is q1’ and second is q1’’ with output a and b respectively. State q1 also have loop, which means these copies are connected to each other by an edge labelled 1 from q1’ to q1’’ so that output is b. Also add a loop labelled 1 on state q1’. Connect these copies with state q2 through an edge labelled 0/a.

The partial Moore Machine is shown below:

We can make any state from q1’ and q1’’ as initial state, but we are selecting q1’. After applying same steps on partial Mealy machine, we got the following Moore Machine:

The final Moore machine is given below:

Converting a Mealy Machine to Moore Machine using transition table

We can convert a Mealy Machine to Moore Machine by using transition table of Mealy Machine. In this method, we split state q1 into transition table of Mealy machine with several states, the number of such states are equal to number of different outputs associated with q1. We split state q1, if it is associated with different outputs, otherwise leave this state as it is. After splitting the columns of the Mealy machine table, we get the Moore machine equivalent to Mealy machine.

Example:

Convert the following Mealy machine into Moore Machine.

Solution:

The equivalent transition table for Mealy Machine is given below:

Only state q0 in the table have different output, all other states have same output. So, we will split state q0 into two states q0’ and q0’’.

The modified table is shown below:

After rearranging the column, we get the following transition table for Moore machine.

The final transition table for Moore machine is given below: