cs3102: Theory of Computation Class 11: Moore, Mealy,

cs3102: Theory of Computation Class 11: Moore, Mealy, and Markov Models Spring 2010 University of Virginia David Evans Menu Exam Review Variations on DFAs: Moore Machine: states produce output Mealy Machine: edges produce output Markov Model: transitions have probabilities

Moore Machine Edward Moore, Gedanken-experiments on Sequential Machines, 1956. http://people.mokk.bme.hu/~kornai/MatNyelv/moore_1956.pdf Moore Machine Example 0 q0; 1 1 0

1 q1; 0 Power of a Machine Power of a DFA, NFA, DPDA, NPDA/CFG: Set of languages it can recognize/produce. Power of a Moore Machine: Set of functions it can perform. Language Set of strings Function Set of

(input/output) pairs Formal Definition Computing Model DFA Moore Computing Model DFA Moore

Moores Experiments Okay...guess the machine! You LOSE! 0 q0; 1 1 0

0 0 q1; 0 q2; 0 1 1 1

0 q6; 1 q3; 0 1 0 q5; 0

1 q4; 0 1 0 You always lose. Sometimes you win... Lorenz Cipher Machine

used by Nazi high command: links between conquered capitals Machine determined by Bill Tutte (1941) from intercepted messages Colossus Arguably, the first electronic, digital, programmable computer. Bletchley Park, 1943

Decoded 63 million letters in Nazi command messages Learned German troop locations to plan D-Day (knew the deception was working) Bletchley Park, 2004 (rebuilt) A More Fair Game Reveal: n, maximum number of states in the machine (and , input alphabet) Equality Rule: two machines are the same if they compute the same function

= {0, 1} n = 3 0 0 q1; 0 q2; 0 1 q3; 1

1 0 How many experiments is enough? Alternate Game Given: state machine Experiment: input -> output Win: guess what state the machine started in Moore proved for some machines where all states are distinguishable, it is impossible to know the starting state from one experiment.

Mealy Machine George Mealy, A Method for Synthesizing Sequential Circuits, 1955 0; 1 q0 1; 0 0; 1 1; 0 q1 Mealy

Machine Moore Machine Computing Model Mealy Machine Moore Machine

Computing Model Which is more powerful? Moor e Mealy For any Moore Machine M, we can construct a Mealy Machine M that performs the same function: qb; y qa; z

qi; x For any Moore Machine M, we can construct a Mealy Machine M that performs the same function: qb qb; y qa qa; z

x x qi; x qi For any Mealy Machine M, we can construct a Moore Machine M that performs the same function: qb qa y x

qi For any Mealy Machine M, we can construct a Moore Machine M that performs the same function: qb qb qa qa y x

qi qi1; x qi2; y Both have all the same outgoing transitions as qi Equally Powerful Moor e

Mealy (Moore may need more needs more states) Are they good models? 0; 1 q0 0; 1 1; 0 1; 0

q1 Markov Model 1.0 0.3 Happy Grumpy 0.2

0.4 0.7 0.3 Sleepy 1 0. Sneezy 0.1 0.9

Andrey Markov, 1856-1922 Markov Model with1.0Outputs 0.3 ARRGH Grumpy 0.3 0.7 0.7 Happy

0.3 Sleepy 0.5 1.0 0.5 ho ho ho! Sneezy 0.1

wahoowa! 0.9 1.0 achoo! #%#$& Zzzzzzzz Markov Model Examples

Nodes: URLs Links: hyperlinks Probabilities: 1/n number of nonself outgoing links a.com b.com 3 1/ 1/3

1/2 c.org 3 1/ 1/2 Pr(u) = probability of reaching u starting from random seed states d.com

1/2 1/2 Lawrence Page, Sergey Brin, Rajeev Motwani and Terry Winograd Garkov http://www.joshmillard.com/garkov/ Hidden Markov Model 1.0 0.3

0.4 Happy 0.3 0.7 0.7 0.3 Sleepy

0.5 1.0 1 0. 0.5 ho ho ho! Sneezy 0.1

wahoowa! ARRGH Grumpy 0.2 0.9 1.0 From just the outputs guess the states (and machine)

achoo! #%#$& Zzzzzzzz Hidden Markov Model Example No Review Question No Review Question No Review

Question No Review Question No Review Question No Review Question No Review Question No Review Question No Review Question

No Review Question No Review Question No Review Question No Review Question No Review Question No Review Question

No Review Question No Review Question No Review Question No Review Question No Review Question No Review Question

No Review Question No Review Question No Review Question No Review Question Sent Review Topics No Review Question No Review

Question No Review Question No Review Question No Review Question No Review Question No Review Question No Review

Question No Review Question No Review Question No Review Question No Review Question No Review Question No Review Question

No Review Question No Review Question No Review Question No Review Question No Review Question No Review Question

No Review Question No Review Question No Review Question No Review Question Hidden Markov Model Want more challenging exam

Lazy 0.9 1.0 No Review Question 0.1 Sent Review

Topics Active Student 1.0 Hidden Markov Model AA Flop: 222 Opponent Raises 0.4

0.6 0.8 AK 0.9 72 0.02 0.08 Raise

Call Fold Return PS3 front of room A-D E-K L-R

S-Z

Recently Viewed Presentations

  • How would you, right now, describe your faith

    How would you, right now, describe your faith

    Matthew 7:7-8 NLT "When Jesus came by, he looked up at Zacchaeus and called him by name. "Zacchaeus!" he said. "Quick, come down! I must be a guest in your home today." Zacchaeus quickly climbed down and took Jesus to...
  • SPEAK

    SPEAK

    SPEAK Trees & Symbolism Trees & Symbolism SPEAK Trees & Symbolism Trees & Symbolism SYMBOL: an object that stands for or represents something else (usually an abstract idea) As you examine the following works of art, consider what emotion each...
  • VOCA Funding Overview/Update John Mahoney DCJS Virginia Department

    VOCA Funding Overview/Update John Mahoney DCJS Virginia Department

    Statewide Grant Programs to Support Specialized Treatment and Services for Victims of Child Abuse. ... Revising/Redesigning CIMS and other data collection tools and software. Enter (LOTS) of PMT data. New Initiative Guidelines to be issued Spring 2017. Author:
  • Balances and Micropipettes - Kennesaw State University

    Balances and Micropipettes - Kennesaw State University

    Balances and Micropipettes By: Paola Restrepo and Ankita Desai Balances Types Micro balances Top Loaders Analytical Balances Floor Scales Validation Pre-purchase meeting with QA, users, and a member of Metrology Discuss the user requirements and the suitability of the proposed...
  • Federal Acquisition Service - GSA SmartPay

    Federal Acquisition Service - GSA SmartPay

    Agencies should pay close attention to the "defaults" in the Master Contract that provide flexibility at the task order level. You will notice these defaults as you read through the Master Contract requirements. Key words to find the defaults are...
  • Safety and Health Programs Slide Presentation

    Safety and Health Programs Slide Presentation

    Provide training to all managers, supervisors and workers as well as contractors and temporary workers on: safety policies and procedures, program functions, emergencies, injury illness reporting, and their rights under the OSH Act. Ensure the training is provided in a...
  • Formal Syntax and Language Change

    Formal Syntax and Language Change

    Arial 新細明體 Default Design Loss and gain in grammar: Aspect, case, and definiteness in Early Middle English Outline Model of language acquisition/change (based on Andersen 1973) Internal Grammar Reanalysis is crucial Cycles tell us which features matter And about processing/economy...
  • Women of the 1916 Rising - Scoilnet

    Women of the 1916 Rising - Scoilnet

    Dr. Kathleen Lynn was born into a Protestant family in Co. Mayo. She became one of the first women doctors in Ireland. ... Kathleen's husband Tom and her brother Edward (Ned) Daly were both executed after the Rising. Kathleen was...