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

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

  • Rhetorical Analysis Annotation Acronyms

    Rhetorical Analysis Annotation Acronyms

    Think about the author's message; what attitude comes through in his/her main point? Style—refers to the writer's use of language; is it formal, informal, technical? What details did the writer choose to include or omit? Examine the various elements of...
  • Computer Networks

    Computer Networks

    It is also called Unipolar-Non-return-to-zero, because there is no rest condition In this case, to represent binary 1, high voltage is transmitted and to represent 0, no voltage is transmitted * * Polar Encoding Polar encoding uses two voltage levels...
  • Doping: Depositing impurities into Si in a controlled manner

    Doping: Depositing impurities into Si in a controlled manner

    Doping: Depositing impurities into Si in a controlled manner Overview Goal: Diffusion & Ion Implanatation Diffusion & Ion Implantation Mechanism , Models Models Models Models Diffusivity Diffusion Junction Formation Diffusion: Drive In: Dopant re distribution Diffusion: Steps Diffusion: Dep: schematic...
  • Phases of Matter and Energy - WordPress.com

    Phases of Matter and Energy - WordPress.com

    PHASE diagram vs. heating curve. Phase diagram. Heating curve. Pressure - y axis. Temperature - x axis. Shows all 6 phase changes. Shows equilibrium temperatures and pressures for all phase changes. Temperature - y axis. Heat over time - x...
  • On the Power of Discrete and of Lexicographic Helly Theorems

    On the Power of Discrete and of Lexicographic Helly Theorems

    / 28. Applications. Lifetime consumption strategy with risk exposure [Phe62] Cash management of mutual funds [HW01] Stochastic ordered knapsack [DGV04]
  • NASA-SPoRT products at WFO MRX

    NASA-SPoRT products at WFO MRX

    The LMA coverage area only covers the western half of our area, but we wish it covered more. A procedure has been created in AWIPS to incorporate the LMA Source Density data with other radar products. Using the Panel Combo...
  • Recipe for Steel - ESP Specialty Steel

    Recipe for Steel - ESP Specialty Steel

    Recipe for Steel ("Pig Iron") Iron (or iron-bearing material) Coke (baked coal) Limestone. Oxygen and Water. Heat to 3400˚ F. Limestone promotes slag formation when the iron ore is melted. It combines with the acid impurities and floats to the...
  • Welcome to nd 2 Grade 2014-2015 Meet the

    Welcome to nd 2 Grade 2014-2015 Meet the

    Good-Fit Books (independent reading) Reading and Writing for. different reasons: (fiction and non-fiction) Narrative, Informative, and Persuasive Writings. What is fluency? Ability to read quickly and easily. Students who don't read smoothly have to work hard to figure out the...