Automata

2's complement by Mealy and Moore Machine

The first one is Mealy Machine and the second one is Moore Machine for 2's complement.

0Comment

thumbs up down

Mealy Machine

A Mealy machine is a machine in which output symbol depends upon the present input symbol and present state of the machine. In the Mealy machine, the output is represented with each input symbol for each state separated by /.

The Mealy machine can be described by 6 tuples (Q, q0, ∑, O, δ, λ') where

Q: a finite set of states

q0: the initial state of the machine

∑: a finite set of the input alphabet

O: output alphabet

δ: transition function where Q × ∑ → Q

λ: output function where Q × ∑ →O

// If the input has n symbol, the output will contain n+1 symbol

Example 1: Design a mealy machine that scans sequence of input of 0 and 1 and generates output 'A' if the input string terminates in 00, output 'B' if the string terminates in 11, and output 'C' otherwise.

Solution:

Example 2: Draw a mealy machine for 2's complement.

Solution:

The logic to construct a Mealy machine for 2's complement is:

Start scanning symbol from the right side and long as you see 0 leave it as 0 but when you see first 1 leave it as 1 and after that write down the 1's complement of every symbol you see.

for example: 2's complement for 1100101100 is 0011010100

0Comment

thumbs up down

Moore Machines

Moore Machines:

In the theory of computation, a Moore machine is a finite-state machine whose output values are determined only by its current state.
If the input has n symbol, the output will contain n+1 symbol because at the intial state we already have one symbol present before we start the actual computation of input symbol.

Example of Moore Machine:

Here you can clearly see that for every state is associated with output.

Moore Transition Table for the above machines is:

for this, you try to form the Transition table.

0Comment

thumbs up down

Introduction to Mealy and Moore Machines

Introduction: - These are the finite Automata with output

The tuples are like

Q: is a finite set of states.
q₀: is the initial state.
∑ : is the input alphabet.
$\Delta$ : is the output alphabet.
δ: is an input transition function which maps Q×∑ → Q.
λ: is the output function which maps Q → O.

Moore machine: In Moore machine output is associated with each state. Here output depends on the present state.

The output function is λ: Q → $\Delta$

it has more states than Mealy Machine.

Mealy machine: In Miley machine output is dependent on the current state as well as present input

The output function is λ: Q ×∑ → $\Delta$

It has fewer states than Moore Machine.

*****

When you are doing conversions from Mealy machine to Moore machine, the no. of states may be increased. But when from Moore to Miley no. of states are remain the same.

0Comment

thumbs up down

Automata theory (also known as Theory Of Computation) is a theoretical branch of Computer Science and Mathematics, which mainly deals with the logic of computation with respect to simple machines, referred to as automata.

Automata* enables the scientists to understand how machines compute the functions and solve problems. The main motivation behind developing Automata Theory was to develop methods to describe and analyse the dynamic behavior of discrete systems.

Automata is originated from the word “Automaton” which is closely related to “Automation”.

0Comment

thumbs up down