Scribd Logo
Upload

Welcome to Scribd!

  • 31 views

    Automata Lecture15

    Uploaded by

    RIMSHA
    1. The document outlines the theory of automata including finite automata with output, Moore machines, and Mealy machines. 2. It provides definitions and examples of Moore machines and Mealy machines. Moore machines output based on their current state, while Mealy machines output based on their current state and current input. 3. Examples are given for Moore and Mealy machines that implement logical NOT, divide input in half, complement values, and increment values. The last example also discusses the overflow state that can occur in Mealy machines.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Automata Lecture15

    Uploaded by

    RIMSHA
    31 views20 pages
    1. The document outlines the theory of automata including finite automata with output, Moore machines, and Mealy machines. 2. It provides definitions and examples of Moore machines and Mealy machines. Moore machines output based on their current state, while Mealy machines output based on their current state and current input. 3. Examples are given for Moore and Mealy machines that implement logical NOT, divide input in half, complement values, and increment values. The last example also discusses the overflow state that can occur in Mealy machines.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1. The document outlines the theory of automata including finite automata with output, Moore machines, and Mealy machines. 2. It provides definitions and examples of Moore machines and Mealy machines. Moore machines output based on their current state, while Mealy machines output based on their current state and current input. 3. Examples are given for Moore and Mealy machines that implement logical NOT, divide input in half, complement values, and increment values. The last example also discusses the overflow state that can occur in Mealy machines.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    31 views20 pages

    Automata Lecture15

    Uploaded by

    RIMSHA
    1. The document outlines the theory of automata including finite automata with output, Moore machines, and Mealy machines. 2. It provides definitions and examples of Moore machines and Mealy machines. Moore machines output based on their current state, while Mealy machines output based on their current state and current input. 3. Examples are given for Moore and Mealy machines that implement logical NOT, divide input in half, complement values, and increment values. The last example also discusses the overflow state that can occur in Mealy machines.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 20

    THEORY OF AUTOMATA– Lecture

    1
    Lecture Outline
    • Finite Automata with output
    • Moore machine
    • Mealy Machine
    5

    Finite Automata with output


    • In Finite Automata, the input string represents
    the input data to a computer program. Reading
    the input letters is very much similar to how a
    computer program performs various
    instructions.
    • The concept of states tell us that what we are
    printing and what we have printed so far.
    6

    • Our goal in this chapter is to prove that the


    mathematical models that we have studied so far
    can be represented as machines.
    • We will study two machines created by G.H
    Mealy (1955) and by E.F Moore (1956).
    • Initially both models were intended for
    sequential circuit design.
    7

    Moore machine Definition


    A Moore machine consists of the following
    1. A finite set of states q0, q1, q2, … where q0 is
    the initial state.
    2. An alphabet of letters  = {a,b,c,…} from
    which the input strings are formed.
    3. An alphabet Г={x,y,z,…} of output
    characters from which output strings
    are generated.
    8

    Moore machine continued …


    4. A transition table that shows for each state
    and each input letter what state is entered the
    next.
    5. No final state, so no question of acceptance
    of input strings.
    9

    Moore Machine
    10

    Example: Moore NOT machine


    11

    Example: Divide an Input in to half


    12

    Mealy machine
    A Mealy machine consists of the following
    1. A finite set of states q0, q1, q2, … where q0 is
    the initial state.
    2. An alphabet of letters  = {a,b,c,…} from
    which the input strings are formed.
    3. An alphabet Г={x,y,z,…} of output
    characters from which output strings
    are generated.
    13

    Example Mealy machine


    14

    Complementing Mealy Machine


    15

    Incrementing Mealy Machine


    Consider the following additions
    a) 100101100 b) 1001111111
    + 1 +1
    100101101 1010000000

    a) If the right most bit is 0 then…


    b) If the right most bit is 1 then…
    16

    Incrementing Mealy Machine


    • The machine will have three states: start, owe-
    carry (OC), and no-carry(NC). Owe-carry state
    will output 0 when two 1 bits are added.
    • The concept of states tell us that what we are
    printing and what we have printed so far.
    17
    Constructing the incrementing
    machine continued …
    The Mealy machine have the states
    q0, q1, q2 , where q0 is the start state and
     = {0,1},
    Г={0,1}
    18

    Overflow state
    Due to typical property of Mealy machines of
    having input bits equals to outputs, if string 1111 is
    run as input, the output will be 0000 and not
    10000. This is called overflow state.
    19

    Summing Up

    • Example of Moore machine,


    • Two halves Moore machine
    • Mealy machine, Examples
    • Example Moore and Mealy Machines Repeat
    • Incrementing Mealy machines
    • Overflow state.
    Reference
    • Theory of computation by Daniel. I
    .Cohen
    • Lecture slides compilation resource [Theory Of
    Automata by Dr. M M Alam]

    You might also like