🧠 MM Fundamentals

🎯 What are Mealy & Moore Machines?

Mealy and Moore machines are finite-state transducers — they produce output based on state and input. A Mealy machine outputs on transitions (depends on state + input), while a Moore machine outputs on states (depends only on current state). Both are fundamental to digital circuit design, protocol modeling, and control systems.

Why MM Matters

Transducers: Machines that produce output. Sequential logic: Foundation of digital circuits. Protocols: Model communication. Control: Traffic lights, vending machines. Compilers: Lexers, parsers. Real-time: Embedded systems.

📌 Finite States📌 Output Function📌 Sequential Logic📌 Transducers

# Mealy & Moore Machines — the big picture
# Both are finite state machines that produce output.

# CONCEPTUAL OVERVIEW
print("""
=== Mealy vs Moore ===

MEALY MACHINE:
  Output depends on: current state + input
  Output on: transitions (edges)
  States: fewer (typically)
  Response: faster (output in same cycle)
  
MOORE MACHINE:
  Output depends on: current state only
  Output on: states (nodes)
  States: more (typically)
  Response: delayed (output next cycle)

Both are:
  - Finite state machines
  - Deterministic (usually)
  - Used in digital design
  - Equivalent in power
""")

# SIMPLE EXAMPLE: VENDING MACHINE
print("=== Example: Vending Machine ===")
print("""
A vending machine that dispenses a product for 25 cents.

Mealy Model:
  States: {0, 5, 10, 15, 20} (cents inserted)
  Input: {nickel, dime, quarter}
  Output: {dispense, nothing}
  
  Transition example:
    (20, nickel) → dispense, go to 0
    (20, dime)   → dispense, go to 5 (overpay)
    (0, dime)    → nothing, go to 10

Moore Model:
  States: {0, 5, 10, 15, 20, 25} (25 = dispense state)
  Input: {nickel, dime, quarter}
  Output: {dispense, nothing} (on state)
  
  State 25 outputs "dispense"
  Other states output "nothing"
""")

# SIMPLE IMPLEMENTATION
class MealyMachine:
    """
    Mealy machine: output on transitions.
    """
    def __init__(self, states, alphabet, output_alphabet, transitions, outputs, initial):
        self.states = states
        self.alphabet = alphabet
        self.output_alphabet = output_alphabet
        self.transitions = transitions  # (state, input) -> next_state
        self.outputs = outputs          # (state, input) -> output
        self.state = initial
        self.initial = initial
    
    def step(self, input_symbol):
        """Process one input, return output."""
        output = self.outputs[(self.state, input_symbol)]
        self.state = self.transitions[(self.state, input_symbol)]
        return output
    
    def run(self, input_string):
        """Process a string, return outputs."""
        self.state = self.initial
        outputs = []
        for symbol in input_string:
            outputs.append(self.step(symbol))
        return outputs


class MooreMachine:
    """
    Moore machine: output on states.
    """
    def __init__(self, states, alphabet, output_alphabet, transitions, state_outputs, initial):
        self.states = states
        self.alphabet = alphabet
        self.output_alphabet = output_alphabet
        self.transitions = transitions      # (state, input) -> next_state
        self.state_outputs = state_outputs  # state -> output
        self.state = initial
        self.initial = initial
    
    def step(self, input_symbol):
        """Process one input, return output of new state."""
        self.state = self.transitions[(self.state, input_symbol)]
        return self.state_outputs[self.state]
    
    def run(self, input_string):
        """Process a string, return outputs."""
        self.state = self.initial
        outputs = [self.state_outputs[self.state]]  # initial output
        for symbol in input_string:
            outputs.append(self.step(symbol))
        return outputs


# EXAMPLE: Binary counter (counts 1s mod 3)
print("=== Example: Count 1s Mod 3 ===")
print("""
Mealy Machine:
  States: {0, 1, 2} (remainder mod 3)
  Input: {0, 1}
  Output: {0, 1, 2} (remainder)
  
  Output on transition: (state, input) -> output

Moore Machine:
  States: {0, 1, 2}
  Input: {0, 1}
  Output: {0, 1, 2} (remainder)
  
  Output on state: state -> output
""")

# Mealy implementation
mealy = MealyMachine(
    states={0, 1, 2},
    alphabet={'0', '1'},
    output_alphabet={0, 1, 2},
    transitions={
        (0, '0'): 0, (0, '1'): 1,
        (1, '0'): 1, (1, '1'): 2,
        (2, '0'): 2, (2, '1'): 0,
    },
    outputs={
        (0, '0'): 0, (0, '1'): 1,
        (1, '0'): 1, (1, '1'): 2,
        (2, '0'): 2, (2, '1'): 0,
    },
    initial=0
)

# Moore implementation
moore = MooreMachine(
    states={0, 1, 2},
    alphabet={'0', '1'},
    output_alphabet={0, 1, 2},
    transitions={
        (0, '0'): 0, (0, '1'): 1,
        (1, '0'): 1, (1, '1'): 2,
        (2, '0'): 2, (2, '1'): 0,
    },
    state_outputs={0: 0, 1: 1, 2: 2},
    initial=0
)

# Test
print("Input: '10110'")
print(f"Mealy outputs: {mealy.run('10110')}")
print(f"Moore outputs: {moore.run('10110')}")
print("\nNote: Moore output is delayed by one step.")
print("      Moore includes initial state output.")
print("      Mealy outputs on each transition.")

# KEY PROPERTIES
print("""
=== Key Properties ===

1. DETERMINISTIC
   - One transition per (state, input)
   - One output per (state, input) or state

2. FINITE STATE
   - Bounded memory
   - Only current state matters

3. SEQUENTIAL
   - Output depends on history
   - But only through current state

4. EQUIVALENT POWER
   - Mealy and Moore are equivalent
   - Can convert between them

5. HARDWARE
   - Directly implementable in digital logic
   - Flip-flops + combinational logic
""")

📐 Formal Definition

🎯 The 6-Tuple

A Mealy machine is formally defined as a 6-tuple (Q, Σ, Γ, δ, λ, q₀) and a Moore machine as (Q, Σ, Γ, δ, λ, q₀) where the output function differs.

Formal Components

Q: Finite set of states. Σ: Input alphabet. Γ: Output alphabet. δ: Transition function. λ: Output function. q₀: Initial state.

Q StatesΣ InputΓ Outputδ Transitionλ Outputq₀ Initial

# Formal definition of Mealy and Moore machines
from dataclasses import dataclass
from typing import Dict, Set, Tuple, Callable

@dataclass
class MealyMachine:
    """
    Mealy machine: M = (Q, Σ, Γ, δ, λ, q₀)
    
    Q: Finite set of states
    Σ: Input alphabet
    Γ: Output alphabet
    δ: Q × Σ → Q  (transition function)
    λ: Q × Σ → Γ  (output function, depends on state AND input)
    q₀: Initial state
    """
    Q: Set[int]
    Sigma: Set[str]
    Gamma: Set[str]
    delta: Dict[Tuple[int, str], int]
    lam: Dict[Tuple[int, str], str]
    q0: int
    
    def __post_init__(self):
        assert self.q0 in self.Q, "Initial state must be in Q"
        for (q, s), q_next in self.delta.items():
            assert q in self.Q, f"State {q} not in Q"
            assert q_next in self.Q, f"Next state {q_next} not in Q"
            assert s in self.Sigma, f"Symbol {s} not in Σ"
        for (q, s), output in self.lam.items():
            assert (q, s) in self.delta, f"No transition for ({q}, {s})"
            assert output in self.Gamma, f"Output {output} not in Γ"
    
    def step(self, state: int, input_symbol: str) -> Tuple[int, str]:
        """Returns (next_state, output)."""
        next_state = self.delta[(state, input_symbol)]
        output = self.lam[(state, input_symbol)]
        return next_state, output
    
    def run(self, input_string: str) -> Tuple[int, list]:
        """Run on input string, return (final_state, outputs)."""
        state = self.q0
        outputs = []
        for symbol in input_string:
            state, output = self.step(state, symbol)
            outputs.append(output)
        return state, outputs


@dataclass
class MooreMachine:
    """
    Moore machine: M = (Q, Σ, Γ, δ, λ, q₀)
    
    Q: Finite set of states
    Σ: Input alphabet
    Γ: Output alphabet
    δ: Q × Σ → Q  (transition function)
    λ: Q → Γ      (output function, depends ONLY on state)
    q₀: Initial state
    """
    Q: Set[int]
    Sigma: Set[str]
    Gamma: Set[str]
    delta: Dict[Tuple[int, str], int]
    lam: Dict[int, str]
    q0: int
    
    def __post_init__(self):
        assert self.q0 in self.Q, "Initial state must be in Q"
        for q in self.Q:
            assert q in self.lam, f"No output for state {q}"
            assert self.lam[q] in self.Gamma, f"Output {self.lam[q]} not in Γ"
        for (q, s), q_next in self.delta.items():
            assert q in self.Q, f"State {q} not in Q"
            assert q_next in self.Q, f"Next state {q_next} not in Q"
            assert s in self.Sigma, f"Symbol {s} not in Σ"
    
    def step(self, state: int, input_symbol: str) -> Tuple[int, str]:
        """Returns (next_state, output of next state)."""
        next_state = self.delta[(state, input_symbol)]
        output = self.lam[next_state]
        return next_state, output
    
    def run(self, input_string: str) -> Tuple[int, list]:
        """Run on input string, return (final_state, outputs)."""
        state = self.q0
        outputs = [self.lam[self.q0]]  # initial output
        for symbol in input_string:
            state, output = self.step(state, symbol)
            outputs.append(output)
        return state, outputs


# EXAMPLE
print("=== Formal Example: Mealy Machine ===")
print("""
Mealy machine for detecting "01" pattern:
  Q = {q0, q1, q2}
  Σ = {0, 1}
  Γ = {0, 1}  (0 = not detected, 1 = detected)
  q0 = q0
  
  δ: (q0, 0) → q1, (q0, 1) → q0
     (q1, 0) → q1, (q1, 1) → q2
     (q2, 0) → q1, (q2, 1) → q0
  
  λ: (q0, 0) → 0, (q0, 1) → 0
     (q1, 0) → 0, (q1, 1) → 1  (detected!)
     (q2, 0) → 0, (q2, 1) → 0
""")

mealy = MealyMachine(
    Q={0, 1, 2},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        (0, '0'): 1, (0, '1'): 0,
        (1, '0'): 1, (1, '1'): 2,
        (2, '0'): 1, (2, '1'): 0,
    },
    lam={
        (0, '0'): '0', (0, '1'): '0',
        (1, '0'): '0', (1, '1'): '1',  # detected
        (2, '0'): '0', (2, '1'): '0',
    },
    q0=0
)

final, outputs = mealy.run('10110')
print(f"Input: '10110'")
print(f"Outputs: {outputs}")
print(f"Final state: {final}")

print("\n=== Formal Example: Moore Machine ===")
print("""
Moore machine for detecting "01" pattern:
  Q = {q0, q1, q2}
  Σ = {0, 1}
  Γ = {0, 1}
  q0 = q0
  
  δ: same as Mealy
  λ: q0 → 0, q1 → 0, q2 → 1  (output on state)
""")

moore = MooreMachine(
    Q={0, 1, 2},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        (0, '0'): 1, (0, '1'): 0,
        (1, '0'): 1, (1, '1'): 2,
        (2, '0'): 1, (2, '1'): 0,
    },
    lam={0: '0', 1: '0', 2: '1'},
    q0=0
)

final, outputs = moore.run('10110')
print(f"Input: '10110'")
print(f"Outputs: {outputs}")
print(f"Final state: {final}")

print("""
Note: Moore output is one step delayed.
      Moore outputs initial state's output first.
      Mealy outputs on each transition.
""")

🔧 Components

🎯 The Building Blocks

Both Mealy and Moore machines share the same core components: states, input alphabet, output alphabet, transition function, and initial state. The difference is in the output function.

Component Details

States: Memory configurations. Input: Symbols read. Output: Symbols produced. Transition: State changes. Output function: Mealy vs Moore. Initial: Start state.

🔲 States📥 Input📤 Output🔄 Transition▶️ Initial

# Components of Mealy and Moore machines
print("=== 1. STATES (Q) ===")
print("""
Finite set of configurations:
  - Represent memory of the machine
  - Mealy: states encode history
  - Moore: states also encode output

Example: Traffic light controller
  States: {NS_GREEN, NS_YELLOW, EW_GREEN, EW_YELLOW}
  
Number of states:
  - Determined by required memory
  - n bits of memory → 2^n states
  - Moore may need more states (output encoding)
""")

print("\n=== 2. INPUT ALPHABET (Σ) ===")
print("""
Finite set of input symbols:
  - What the machine reads
  - Each symbol triggers a transition

Examples:
  Binary: Σ = {0, 1}
  Traffic: Σ = {timer_expired, emergency}
  Vending: Σ = {nickel, dime, quarter}
  Protocol: Σ = {SYN, ACK, FIN, DATA}
""")

print("\n=== 3. OUTPUT ALPHABET (Γ) ===")
print("""
Finite set of output symbols:
  - What the machine produces

Examples:
  Binary: Γ = {0, 1}
  Traffic: Γ = {red, yellow, green}
  Vending: Γ = {dispense, return_coin, nothing}
  Protocol: Γ = {send_ack, send_nak, ignore}
""")

print("\n=== 4. TRANSITION FUNCTION (δ) ===")
print("""
δ: Q × Σ → Q

For each (state, input):
  - Exactly one next state (deterministic)
  - Total function (defined for all pairs)

Example:
  δ(GREEN, timer) = YELLOW
  δ(YELLOW, timer) = RED
  δ(RED, timer) = GREEN
""")

print("\n=== 5. OUTPUT FUNCTION (λ) ===")
print("""
Mealy: λ: Q × Σ → Γ
  - Depends on state AND input
  - Output on transition

Moore: λ: Q → Γ
  - Depends only on state
  - Output on state

This is the KEY DIFFERENCE.
""")

print("\n=== 6. INITIAL STATE (q₀) ===")
print("""
q₀ ∈ Q

Where the machine starts.
For Moore: q₀ also has an output.
For Mealy: no output until first input.
""")

# COMPONENT VISUALIZATION
print("\n=== Visual Comparison ===")
print("""
MEALY MACHINE:
  
  Input:    ──→ (q0) ──0/1──→ (q1) ──1/0──→ (q2) ──→
                  ↑              │              │
                  │              │              │
                  └──────────────┴──────────────┘
  
  Notation: state ──input/output──→ state
  Output on TRANSITIONS

MOORE MACHINE:
  
  Input:    ──→ (q0/0) ──0──→ (q1/0) ──1──→ (q2/1) ──→
                    ↑           │           │
                    │           │           │
                    └───────────┴───────────┘
  
  Notation: state/output
  Output on STATES
""")

# IMPLEMENTATION
print("\n=== Implementation: Component Access ===")

class MMMachine:
    """Base class for Mealy and Moore machines."""
    def __init__(self, Q, Sigma, Gamma, delta, q0):
        self.Q = Q
        self.Sigma = Sigma
        self.Gamma = Gamma
        self.delta = delta
        self.q0 = q0
    
    def get_components(self):
        return {
            'Q': self.Q,
            'Sigma': self.Sigma,
            'Gamma': self.Gamma,
            'delta': self.delta,
            'q0': self.q0
        }

# Example: Traffic light controller (Moore)
print("=== Traffic Light Controller (Moore) ===")
traffic = MooreMachine(
    Q={'NS_G', 'NS_Y', 'EW_G', 'EW_Y'},
    Sigma={'timer'},
    Gamma={'red', 'yellow', 'green'},
    delta={
        ('NS_G', 'timer'): 'NS_Y',
        ('NS_Y', 'timer'): 'EW_G',
        ('EW_G', 'timer'): 'EW_Y',
        ('EW_Y', 'timer'): 'NS_G',
    },
    lam={
        'NS_G': 'green',
        'NS_Y': 'yellow',
        'EW_G': 'green',
        'EW_Y': 'yellow',
    },
    q0='NS_G'
)

print(f"States: {traffic.Q}")
print(f"Input: {traffic.Sigma}")
print(f"Output: {traffic.Gamma}")
print(f"Initial: {traffic.q0}")

# Run
final, outputs = traffic.run(['timer', 'timer', 'timer', 'timer'])
print(f"\nOutputs: {outputs}")
print(f"Final state: {final}")

📤 Mealy Machines

🎯 Output on Transitions

A Mealy machine produces output based on both the current state and the input. Output is associated with transitions (edges) in the state diagram. Mealy machines typically need fewer states than equivalent Moore machines.

Mealy Properties

Output: On transitions (state + input). States: Typically fewer. Response: Faster (same cycle). Glitches: Possible (input-dependent). Hardware: More combinational logic. Diagram: Edge labels.

📤 Output on Edge⚡ Fast Response🔢 Fewer States⚠️ Glitches

# Mealy Machines — output on transitions
print("=== Mealy Machine Definition ===")
print("""
M = (Q, Σ, Γ, δ, λ, q₀)

δ: Q × Σ → Q       (next state)
λ: Q × Σ → Γ       (output)

Output depends on (state, input).
""")

# COMPLETE MEALY IMPLEMENTATION
class MealyMachine:
    def __init__(self, Q, Sigma, Gamma, delta, lam, q0):
        self.Q = Q
        self.Sigma = Sigma
        self.Gamma = Gamma
        self.delta = delta
        self.lam = lam
        self.q0 = q0
        self.state = q0
    
    def reset(self):
        self.state = self.q0
    
    def step(self, input_symbol):
        """Process one input. Returns output."""
        output = self.lam[(self.state, input_symbol)]
        self.state = self.delta[(self.state, input_symbol)]
        return output
    
    def run(self, input_string):
        """Process entire string."""
        self.reset()
        return [self.step(s) for s in input_string]
    
    def trace(self, input_string):
        """Detailed trace."""
        self.reset()
        print(f"Initial state: {self.state}")
        for s in input_string:
            output = self.lam[(self.state, s)]
            next_state = self.delta[(self.state, s)]
            print(f"  {self.state} --{s}/{output}--> {next_state}")
            self.state = next_state


# EXAMPLE 1: Edge detector
print("\n=== Example 1: Edge Detector ===")
print("""
Detects rising edge (0→1 transition).

States: {q0, q1} (q0 = last input was 0, q1 = last input was 1)
Input: {0, 1}
Output: {0, 1} (1 when rising edge detected)

Transitions:
  (q0, 0) → q0, output 0
  (q0, 1) → q1, output 1  (rising edge!)
  (q1, 0) → q0, output 0
  (q1, 1) → q1, output 0
""")

edge_detector = MealyMachine(
    Q={'q0', 'q1'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('q0', '0'): 'q0',
        ('q0', '1'): 'q1',
        ('q1', '0'): 'q0',
        ('q1', '1'): 'q1',
    },
    lam={
        ('q0', '0'): '0',
        ('q0', '1'): '1',  # rising edge
        ('q1', '0'): '0',
        ('q1', '1'): '0',
    },
    q0='q0'
)

print("\nTrace for input '0010110':")
edge_detector.trace('0010110')
print(f"\nOutputs: {edge_detector.run('0010110')}")

# EXAMPLE 2: Sequence detector (Mealy)
print("\n=== Example 2: Sequence Detector (Mealy) ===")
print("""
Detects sequence "101" in input.

States: {q0, q1, q2} (matched 0, 1, 10 characters)
Input: {0, 1}
Output: {0, 1} (1 when "101" detected)

This is a classic Mealy machine example.
""")

seq_detector = MealyMachine(
    Q={'q0', 'q1', 'q2'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('q0', '0'): 'q0',
        ('q0', '1'): 'q1',
        ('q1', '0'): 'q2',
        ('q1', '1'): 'q1',
        ('q2', '0'): 'q0',
        ('q2', '1'): 'q1',
    },
    lam={
        ('q0', '0'): '0',
        ('q0', '1'): '0',
        ('q1', '0'): '0',
        ('q1', '1'): '0',
        ('q2', '0'): '0',
        ('q2', '1'): '1',  # "101" detected
    },
    q0='q0'
)

print("\nTrace for input '101101':")
seq_detector.trace('101101')
print(f"\nOutputs: {seq_detector.run('101101')}")

# EXAMPLE 3: Binary adder (serial)
print("\n=== Example 3: Serial Binary Adder (Mealy) ===")
print("""
Adds two binary numbers bit by bit.

States: {q0, q1} (carry = 0, carry = 1)
Input: {00, 01, 10, 11} (two bits)
Output: {0, 1} (sum bit)

This is a classic Mealy machine.
""")

adder = MealyMachine(
    Q={'carry0', 'carry1'},
    Sigma={'00', '01', '10', '11'},
    Gamma={'0', '1'},
    delta={
        ('carry0', '00'): 'carry0',
        ('carry0', '01'): 'carry0',
        ('carry0', '10'): 'carry0',
        ('carry0', '11'): 'carry1',
        ('carry1', '00'): 'carry0',
        ('carry1', '01'): 'carry1',
        ('carry1', '10'): 'carry1',
        ('carry1', '11'): 'carry1',
    },
    lam={
        ('carry0', '00'): '0',
        ('carry0', '01'): '1',
        ('carry0', '10'): '1',
        ('carry0', '11'): '0',
        ('carry1', '00'): '1',
        ('carry1', '01'): '0',
        ('carry1', '10'): '0',
        ('carry1', '11'): '1',
    },
    q0='carry0'
)

print("\nAdding 1011 + 0110:")
print("(processing from LSB to MSB)")
inputs = ['11', '01', '10', '01']  # LSB first
print(f"Input pairs: {inputs}")
print(f"Sum bits: {adder.run(inputs)}")
print("Expected sum: 10001 (LSB first: 10001)")
print("Check: 11 + 6 = 17 = 10001 ✓")

# MEALY ADVANTAGES/DISADVANTAGES
print("\n=== Mealy: Advantages & Disadvantages ===")
print("""
ADVANTAGES:
  ✓ Fewer states (typically)
  ✓ Faster response (output in same cycle)
  ✓ Less memory
  ✓ Direct output from combinational logic

DISADVANTAGES:
  ✗ Output may glitch (depends on input)
  ✗ Harder to design (more complex logic)
  ✗ Timing analysis more complex
  ✗ Output not synchronized with clock

USE WHEN:
  - Speed is critical
  - State minimization is important
  - Output glitches are acceptable
  - Combinational logic is available
""")

📥 Moore Machines

🎯 Output on States

A Moore machine produces output based solely on the current state. Output is associated with states (nodes) in the state diagram. Moore machines typically need more states but have more stable outputs.

Moore Properties

Output: On states (state only). States: Typically more. Response: Delayed (next cycle). Glitches: No (synchronized). Hardware: Output from flip-flops. Diagram: State labels.

📥 Output on Node🔄 Stable Output🔢 More States✅ No Glitches

# Moore Machines — output on states
print("=== Moore Machine Definition ===")
print("""
M = (Q, Σ, Γ, δ, λ, q₀)

δ: Q × Σ → Q     (next state)
λ: Q → Γ         (output)

Output depends only on state.
""")

# COMPLETE MOORE IMPLEMENTATION
class MooreMachine:
    def __init__(self, Q, Sigma, Gamma, delta, lam, q0):
        self.Q = Q
        self.Sigma = Sigma
        self.Gamma = Gamma
        self.delta = delta
        self.lam = lam
        self.q0 = q0
        self.state = q0
    
    def reset(self):
        self.state = self.q0
    
    def step(self, input_symbol):
        """Process one input. Returns output of new state."""
        self.state = self.delta[(self.state, input_symbol)]
        return self.lam[self.state]
    
    def run(self, input_string):
        """Process entire string. Includes initial output."""
        self.reset()
        outputs = [self.lam[self.q0]]
        for s in input_string:
            outputs.append(self.step(s))
        return outputs
    
    def trace(self, input_string):
        """Detailed trace."""
        self.reset()
        print(f"Initial: {self.state}/{self.lam[self.state]}")
        for s in input_string:
            next_state = self.delta[(self.state, s)]
            output = self.lam[next_state]
            print(f"  {self.state} --{s}--> {next_state}/{output}")
            self.state = next_state


# EXAMPLE 1: Edge detector (Moore)
print("\n=== Example 1: Edge Detector (Moore) ===")
print("""
Detects rising edge (0→1 transition).

States: {q0, q1} (q0 = last input 0, q1 = last input 1)
Output: state q0 → 0, state q1 → 0... but need to detect edge!

Problem: Moore needs a state for "just detected edge".

States: {S0, S1, S2}
  S0: last input was 0, no edge
  S1: last input was 1, no edge (or edge just passed)
  S2: just detected rising edge

Actually, we need:
  S0: initial / last was 0
  S1: last was 1 (edge just detected)

Output: S0 → 0, S1 → 1
""")

edge_moore = MooreMachine(
    Q={'S0', 'S1'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('S0', '0'): 'S0',
        ('S0', '1'): 'S1',
        ('S1', '0'): 'S0',
        ('S1', '1'): 'S1',
    },
    lam={
        'S0': '0',
        'S1': '1',  # output when in S1 (edge detected)
    },
    q0='S0'
)

print("\nTrace for input '0010110':")
edge_moore.trace('0010110')
print(f"\nOutputs: {edge_moore.run('0010110')}")
print("Note: Moore output is one step delayed.")

# EXAMPLE 2: Sequence detector (Moore)
print("\n=== Example 2: Sequence Detector (Moore) ===")
print("""
Detects sequence "101".

States: {q0, q1, q2, q3}
  q0: no match
  q1: matched "1"
  q2: matched "10"
  q3: matched "101" (detected!)

Output: q3 → 1, others → 0
""")

seq_moore = MooreMachine(
    Q={'q0', 'q1', 'q2', 'q3'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('q0', '0'): 'q0',
        ('q0', '1'): 'q1',
        ('q1', '0'): 'q2',
        ('q1', '1'): 'q1',
        ('q2', '0'): 'q0',
        ('q2', '1'): 'q3',
        ('q3', '0'): 'q0',
        ('q3', '1'): 'q1',
    },
    lam={
        'q0': '0',
        'q1': '0',
        'q2': '0',
        'q3': '1',  # detected
    },
    q0='q0'
)

print("\nTrace for input '101101':")
seq_moore.trace('101101')
print(f"\nOutputs: {seq_moore.run('101101')}")

# EXAMPLE 3: Traffic light (Moore)
print("\n=== Example 3: Traffic Light (Moore) ===")
print("""
Classic Moore machine example.

States: {NS_G, NS_Y, EW_G, EW_Y}
Input: {timer}
Output: {red, yellow, green} (per direction)
""")

traffic = MooreMachine(
    Q={'NS_G', 'NS_Y', 'EW_G', 'EW_Y'},
    Sigma={'timer'},
    Gamma={'NS_red', 'NS_yellow', 'NS_green', 'EW_red', 'EW_yellow', 'EW_green'},
    delta={
        ('NS_G', 'timer'): 'NS_Y',
        ('NS_Y', 'timer'): 'EW_G',
        ('EW_G', 'timer'): 'EW_Y',
        ('EW_Y', 'timer'): 'NS_G',
    },
    lam={
        'NS_G': 'NS_green',
        'NS_Y': 'NS_yellow',
        'EW_G': 'EW_green',
        'EW_Y': 'EW_yellow',
    },
    q0='NS_G'
)

print("\nTrace for 4 timer events:")
traffic.trace(['timer', 'timer', 'timer', 'timer'])
print(f"\nOutputs: {traffic.run(['timer', 'timer', 'timer', 'timer'])}")

# MOORE ADVANTAGES/DISADVANTAGES
print("\n=== Moore: Advantages & Disadvantages ===")
print("""
ADVANTAGES:
  ✓ Output synchronized with clock
  ✓ No glitches (stable output)
  ✓ Easier to design
  ✓ Better for safety-critical systems
  ✓ Output available at cycle start

DISADVANTAGES:
  ✗ More states (typically)
  ✗ Slower response (output delayed)
  ✗ More memory
  ✗ May need extra states for output encoding

USE WHEN:
  - Output stability is critical
  - Glitches are unacceptable
  - Design simplicity is important
  - Synchronous output is needed
""")

# COMPARISON
print("\n=== Moore vs Mealy: State Count ===")
print("""
Sequence detector for "101":

Mealy: 3 states (q0, q1, q2)
Moore: 4 states (q0, q1, q2, q3)

Moore needs an extra state to represent "detected".

General rule:
  Moore states ≥ Mealy states
  Difference is usually 0-2 states
""")

⚖️ Mealy vs Moore

🎯 Key Differences

Mealy and Moore machines differ in when output is produced. Mealy outputs on transitions (state + input), while Moore outputs on states. This affects state count, response time, and glitch behavior.

Comparison

Output: Mealy on edges, Moore on nodes. States: Mealy fewer, Moore more. Response: Mealy faster, Moore delayed. Glitches: Mealy possible, Moore none. Hardware: Different logic. Power: Equivalent.

📤 Edge vs Node⚡ Fast vs Stable🔢 Fewer vs More⚠️ Glitch vs Clean

# Mealy vs Moore — detailed comparison
print("=== Side-by-Side Comparison ===")
print(f"{'Aspect':<25} {'Mealy':<30} {'Moore':<30}")
print("-" * 85)
print(f"{'Output depends on':<25} {'State + Input':<30} {'State only':<30}")
print(f"{'Output location':<25} {'Transitions (edges)':<30} {'States (nodes)':<30}")
print(f"{'Output timing':<25} {'Same cycle':<30} {'Next cycle':<30}")
print(f"{'Number of states':<25} {'Typically fewer':<30} {'Typically more':<30}")
print(f"{'Glitches':<25} {'Possible':<30} {'None (synchronized)':<30}")
print(f"{'Design complexity':<25} {'More complex':<30} {'Simpler':<30}")
print(f"{'Hardware':<25} {'Combinational output':<30} {'Registered output':<30}")
print(f"{'Response speed':<25} {'Faster':<30} {'Slower':<30}")
print(f"{'State minimization':<25} {'More important':<30} {'Less critical':<30}")
print(f"{'Safety-critical':<25} {'Less suitable':<30} {'More suitable':<30}")

# CONVERSION EXAMPLE
print("\n=== Conversion: Mealy → Moore ===")
print("""
To convert Mealy to Moore:
  1. For each state, determine possible outputs
  2. If a state has multiple outputs, split it
  3. Add output to each state

Example: Mealy edge detector
  States: {q0, q1}
  Outputs: (q0,0)→0, (q0,1)→1, (q1,0)→0, (q1,1)→0
  
  q0 has outputs: 0 (on 0), 1 (on 1) → split!
  q0_0 (output 0) and q0_1 (output 1)
  
  Moore:
    States: {q0_0, q0_1, q1}
    Outputs: q0_0→0, q0_1→1, q1→0
""")

# CONCRETE EXAMPLE
print("\n=== Concrete Example: Both Models ===")

# Mealy
mealy = MealyMachine(
    Q={'A', 'B'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('A', '0'): 'A',
        ('A', '1'): 'B',
        ('B', '0'): 'A',
        ('B', '1'): 'B',
    },
    lam={
        ('A', '0'): '0',
        ('A', '1'): '1',  # output 1 on A→B
        ('B', '0'): '0',
        ('B', '1'): '0',
    },
    q0='A'
)

# Moore equivalent
moore = MooreMachine(
    Q={'A0', 'A1', 'B'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('A0', '0'): 'A0',
        ('A0', '1'): 'A1',
        ('A1', '0'): 'A0',
        ('A1', '1'): 'B',
        ('B', '0'): 'A0',
        ('B', '1'): 'B',
    },
    lam={
        'A0': '0',
        'A1': '1',
        'B': '0',
    },
    q0='A0'
)

print("Input: '010110'")
print(f"Mealy outputs: {mealy.run('010110')}")
print(f"Moore outputs: {moore.run('010110')}")
print("\nMealy:  output on each transition")
print("Moore:  output on each state (delayed)")

# STATE COUNT
print("\n=== State Count Comparison ===")
print("""
For sequence detector "101":

Mealy:
  States: {q0, q1, q2}
  - q0: no match
  - q1: matched "1"
  - q2: matched "10"
  Output on transitions: (q2, 1) → 1

Moore:
  States: {q0, q1, q2, q3}
  - q0: no match
  - q1: matched "1"
  - q2: matched "10"
  - q3: matched "101" (output 1)
  Output on states: q3 → 1

Moore needs 1 extra state.
""")

# HARDWARE COMPARISON
print("\n=== Hardware Implementation ===")
print("""
MEALY:
  Next State Logic ──→ Flip-Flops ──→ State
         ↑                              │
         │                              │
  Input ─┴──→ Output Logic ←───────────┘
  
  Output = f(State, Input)
  Combinational output → glitches possible

MOORE:
  Next State Logic ──→ Flip-Flops ──→ State
         ↑                              │
         │                              │
  Input ─┘                              │
                                        ↓
                                   Output Logic
                                        │
                                        ↓
                                     Output
                                     
  Output = f(State)
  Registered output → no glitches
""")

# WHEN TO USE WHICH
print("\n=== When to Use Which ===")
print("""
USE MEALY WHEN:
  ✓ Speed is critical
  ✓ Minimizing states is important
  ✓ Output glitches are acceptable
  ✓ Input is stable when clocked
  ✓ Combinational logic is available

USE MOORE WHEN:
  ✓ Output stability is critical
  ✓ Safety-critical system
  ✓ Glitches are unacceptable
  ✓ Design simplicity is important
  ✓ Output should be synchronous

IN PRACTICE:
  - Many designs use Moore for safety
  - Mealy for speed-critical paths
  - Sometimes hybrid approaches
  - Modern tools handle both
""")

# EQUIVALENCE
print("\n=== Equivalence ===")
print("""
Theorem: Mealy and Moore machines are equivalent in power.

Proof:
  - Every Moore machine can be converted to Mealy
    (output on state = output on all incoming transitions)
  - Every Mealy machine can be converted to Moore
    (split states by output)

So for every Mealy machine, there's an equivalent Moore machine,
and vice versa.

The difference is:
  - Number of states
  - Timing of output
  - Hardware implementation
""")

🔄 Conversion

🎯 Mealy ↔ Moore

Mealy and Moore machines can be converted into each other. Mealy → Moore may require splitting states, while Moore → Mealy is straightforward (move output to transitions).

Conversion Methods

Mealy → Moore: Split states by output. Moore → Mealy: Move output to edges. State count: Mealy → Moore may increase. Moore → Mealy: Same or fewer. Equivalence: Same input-output behavior.

🔄 Split States➡️ Move Output🔢 State Count🟰 Equivalence

# Conversion between Mealy and Moore machines
from collections import defaultdict

# MEALY → MOORE CONVERSION
def mealy_to_moore(mealy):
    """
    Convert Mealy machine to Moore machine.
    
    Algorithm:
      1. For each Mealy state q, find all possible outputs
      2. If q has multiple outputs, create one Moore state per output
      3. New states: (q, output)
      4. Moore output of (q, output) = output
      5. Transitions: ((q, out), input) → (delta(q, input), lambda(q, input))
      6. Initial state: (q0, ???) — need special handling
    """
    # Group outputs by state
    state_outputs = defaultdict(set)
    for (q, s), out in mealy.lam.items():
        state_outputs[q].add(out)
    
    # Create new Moore states
    new_Q = set()
    for q, outputs in state_outputs.items():
        for out in outputs:
            new_Q.add((q, out))
    
    # Handle initial state: need to pick an output
    # Often we use a dummy initial state or pick any output
    q0_mealy = mealy.q0
    q0_options = state_outputs[q0_mealy]
    q0_moore = (q0_mealy, next(iter(q0_options)))
    
    # Build transitions
    new_delta = {}
    for (q, s), q_next in mealy.delta.items():
        out_next = mealy.lam[(q, s)]
        # From any Moore state with same q, transition to (q_next, out_next)
        for out_curr in state_outputs[q]:
            new_delta[((q, out_curr), s)] = (q_next, out_next)
    
    # Output function
    new_lam = {state: state[1] for state in new_Q}
    
    return MooreMachine(
        Q=new_Q,
        Sigma=mealy.Sigma,
        Gamma=mealy.Gamma,
        delta=new_delta,
        lam=new_lam,
        q0=q0_moore
    )


# MOORE → MEALY CONVERSION
def moore_to_mealy(moore):
    """
    Convert Moore machine to Mealy machine.
    
    Algorithm:
      1. Same states
      2. Output on transition (q, s) = output of next state
      3. λ_mealy(q, s) = λ_moore(δ(q, s))
    """
    new_lam = {}
    for (q, s), q_next in moore.delta.items():
        new_lam[(q, s)] = moore.lam[q_next]
    
    return MealyMachine(
        Q=moore.Q,
        Sigma=moore.Sigma,
        Gamma=moore.Gamma,
        delta=moore.delta,
        lam=new_lam,
        q0=moore.q0
    )


# EXAMPLE
print("=== Mealy → Moore Conversion ===")
print("""
Original Mealy machine:
  States: {q0, q1}
  Input: {0, 1}
  Output: {0, 1}
  
  (q0, 0) → q0, output 0
  (q0, 1) → q1, output 1
  (q1, 0) → q0, output 0
  (q1, 1) → q1, output 0
""")

mealy_orig = MealyMachine(
    Q={'q0', 'q1'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('q0', '0'): 'q0',
        ('q0', '1'): 'q1',
        ('q1', '0'): 'q0',
        ('q1', '1'): 'q1',
    },
    lam={
        ('q0', '0'): '0',
        ('q0', '1'): '1',
        ('q1', '0'): '0',
        ('q1', '1'): '0',
    },
    q0='q0'
)

print("Mealy trace for '0110':")
mealy_orig.trace('0110')
print(f"Outputs: {mealy_orig.run('0110')}")

moore_converted = mealy_to_moore(mealy_orig)
print(f"\nConverted Moore states: {moore_converted.Q}")
print(f"Moore outputs: {moore_converted.lam}")
print("\nMoore trace for '0110':")
moore_converted.trace('0110')
print(f"Outputs: {moore_converted.run('0110')}")

# Moore → Mealy
print("\n=== Moore → Mealy Conversion ===")
print("""
Original Moore machine:
  States: {A, B}
  Outputs: A → 0, B → 1
""")

moore_orig = MooreMachine(
    Q={'A', 'B'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('A', '0'): 'A',
        ('A', '1'): 'B',
        ('B', '0'): 'A',
        ('B', '1'): 'B',
    },
    lam={'A': '0', 'B': '1'},
    q0='A'
)

print("Moore trace for '0110':")
moore_orig.trace('0110')
print(f"Outputs: {moore_orig.run('0110')}")

mealy_converted = moore_to_mealy(moore_orig)
print("\nConverted Mealy outputs:")
for key, val in mealy_converted.lam.items():
    print(f"  {key} → {val}")

print("Mealy trace for '0110':")
mealy_converted.trace('0110')
print(f"Outputs: {mealy_converted.run('0110')}")

# STATE COUNT
print("\n=== State Count Changes ===")
print(f"Mealy states: {len(mealy_orig.Q)}")
print(f"Converted Moore states: {len(moore_converted.Q)}")
print(f"Original Moore states: {len(moore_orig.Q)}")
print(f"Converted Mealy states: {len(mealy_converted.Q)}")

print("""
Observation:
  - Mealy → Moore may increase states
  - Moore → Mealy keeps same states
  - Moore → Mealy may have fewer states (no output encoding)
""")

# COMPLETE EXAMPLE
print("\n=== Complete Conversion Example ===")
print("""
Sequence detector for "101":

Mealy (3 states):
  q0 --1/0--> q1
  q1 --0/0--> q2
  q2 --1/1--> q1  (detected, output 1)
  
Moore (4 states):
  q0/0 --1--> q1/0 --0--> q2/0 --1--> q3/1
  q3/1 --0--> q0/0
  q3/1 --1--> q1/0
""")

# Build Mealy version
mealy_101 = MealyMachine(
    Q={'q0', 'q1', 'q2'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('q0', '0'): 'q0',
        ('q0', '1'): 'q1',
        ('q1', '0'): 'q2',
        ('q1', '1'): 'q1',
        ('q2', '0'): 'q0',
        ('q2', '1'): 'q1',
    },
    lam={
        ('q0', '0'): '0',
        ('q0', '1'): '0',
        ('q1', '0'): '0',
        ('q1', '1'): '0',
        ('q2', '0'): '0',
        ('q2', '1'): '1',
    },
    q0='q0'
)

# Build Moore version
moore_101 = MooreMachine(
    Q={'q0', 'q1', 'q2', 'q3'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('q0', '0'): 'q0',
        ('q0', '1'): 'q1',
        ('q1', '0'): 'q2',
        ('q1', '1'): 'q1',
        ('q2', '0'): 'q0',
        ('q2', '1'): 'q3',
        ('q3', '0'): 'q0',
        ('q3', '1'): 'q1',
    },
    lam={
        'q0': '0',
        'q1': '0',
        'q2': '0',
        'q3': '1',
    },
    q0='q0'
)

print("Input: '101101'")
print(f"Mealy: {mealy_101.run('101101')}")
print(f"Moore: {moore_101.run('101101')}")
print("\nBoth detect '101' but Moore output is delayed.")

📊 State Tables & Diagrams

🎯 Representing MM

Mealy and Moore machines can be represented as state tables (tabular form) or state diagrams (graphical form). Each representation has advantages for different purposes.

Representations

State table: Tabular, precise. State diagram: Visual, intuitive. Mealy: Output on edges. Moore: Output on nodes. Transition table: Next state + output. ASCII: Text-based diagrams.

📋 Table🎨 Diagram📝 Text🔄 Convert

# State tables and diagrams for Mealy and Moore machines
print("=== State Tables ===")
print("""
A state table shows:
  - Rows: states
  - Columns: inputs
  - Cells: next state (and output)

MEALY STATE TABLE:
  Present State | Input=0      | Input=1
  --------------|--------------|-------------
  → q0          | q0 / 0       | q1 / 1
    q1          | q0 / 0       | q1 / 0
    
  Format: next_state / output

MOORE STATE TABLE:
  Present State | Output | Next(0) | Next(1)
  --------------|--------|---------|--------
  → q0          | 0      | q0      | q1
    q1          | 0      | q0      | q1
    q2          | 1      | q0      | q1
    
  Output is separate column.
""")

# STATE TABLE PRINTER
def print_mealy_table(machine):
    """Print Mealy state table."""
    print("\nMealy State Table:")
    print(f"{'Present':<10} | " + " | ".join(f"Input={s:<8}" for s in sorted(machine.Sigma)))
    print("-" * (12 + 12 * len(machine.Sigma)))
    
    for q in sorted(machine.Q):
        marker = "→" if q == machine.q0 else " "
        row = f"{marker} {q:<8} | "
        cells = []
        for s in sorted(machine.Sigma):
            next_q = machine.delta.get((q, s), '—')
            out = machine.lam.get((q, s), '—')
            cells.append(f"{next_q} / {out:<4}")
        print(row + " | ".join(cells))

def print_moore_table(machine):
    """Print Moore state table."""
    print("\nMoore State Table:")
    header = f"{'Present':<10} | {'Output':<6} | " + " | ".join(f"Next({s})" for s in sorted(machine.Sigma))
    print(header)
    print("-" * len(header))
    
    for q in sorted(machine.Q):
        marker = "→" if q == machine.q0 else " "
        out = machine.lam.get(q, '—')
        row = f"{marker} {q:<8} | {out:<6} | "
        cells = []
        for s in sorted(machine.Sigma):
            next_q = machine.delta.get((q, s), '—')
            cells.append(f"{next_q:<8}")
        print(row + " | ".join(cells))


# EXAMPLE
print("\n=== Example: Sequence Detector '01' ===")

mealy = MealyMachine(
    Q={'q0', 'q1', 'q2'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('q0', '0'): 'q1',
        ('q0', '1'): 'q0',
        ('q1', '0'): 'q1',
        ('q1', '1'): 'q2',
        ('q2', '0'): 'q1',
        ('q2', '1'): 'q0',
    },
    lam={
        ('q0', '0'): '0',
        ('q0', '1'): '0',
        ('q1', '0'): '0',
        ('q1', '1'): '1',
        ('q2', '0'): '0',
        ('q2', '1'): '0',
    },
    q0='q0'
)

print_mealy_table(mealy)

moore = MooreMachine(
    Q={'q0', 'q1', 'q2'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('q0', '0'): 'q1',
        ('q0', '1'): 'q0',
        ('q1', '0'): 'q1',
        ('q1', '1'): 'q2',
        ('q2', '0'): 'q1',
        ('q2', '1'): 'q0',
    },
    lam={'q0': '0', 'q1': '0', 'q2': '1'},
    q0='q0'
)

print_moore_table(moore)

# STATE DIAGRAMS
print("\n=== State Diagrams ===")
print("""
MEALY DIAGRAM:
  - States are circles
  - Transitions are arrows
  - Labels: input / output
  
  Example:
  
      0/0          0/0
    ┌─────┐      ┌─────┐
    │     ↓      │     ↓
  →(q0)       (q1)       (q2)
    │           │         │
    └──1/0──────┘         │
    │                     │
    └──1/0────────────────┘
    
    (q2) --1/1--> (q1)
    (q2) --0/0--> (q1)
    (q1) --1/1--> (q2)
    (q1) --0/0--> (q1)

MOORE DIAGRAM:
  - States are circles with output
  - Transitions are arrows
  - Labels: input only
  
  Example:
  
      0            0
    ┌─────┐      ┌─────┐
    │     ↓      │     ↓
  →(q0/0)      (q1/0)      (q2/1)
    │           │          │
    └──1────────┘          │
    │                      │
    └──1───────────────────┘
    
    (q2/1) --0--> (q1/0)
    (q2/1) --1--> (q0/0)
    (q1/0) --1--> (q2/1)
    (q1/0) --0--> (q1/0)
""")

# ASCII DIAGRAM GENERATOR
def ascii_mealy_diagram(machine, title="Mealy Machine"):
    """Generate simple ASCII state diagram."""
    print(f"\n{title}:")
    print("=" * 40)
    
    for q in sorted(machine.Q):
        marker = "→" if q == machine.q0 else " "
        print(f"{marker} ({q})")
        for s in sorted(machine.Sigma):
            if (q, s) in machine.delta:
                next_q = machine.delta[(q, s)]
                out = machine.lam[(q, s)]
                print(f"    --{s}/{out}--> ({next_q})")
        print()

def ascii_moore_diagram(machine, title="Moore Machine"):
    """Generate simple ASCII state diagram."""
    print(f"\n{title}:")
    print("=" * 40)
    
    for q in sorted(machine.Q):
        marker = "→" if q == machine.q0 else " "
        out = machine.lam[q]
        print(f"{marker} ({q}/{out})")
        for s in sorted(machine.Sigma):
            if (q, s) in machine.delta:
                next_q = machine.delta[(q, s)]
                print(f"    --{s}--> ({next_q}/{machine.lam[next_q]})")
        print()

print("\n=== ASCII Diagrams ===")
ascii_mealy_diagram(mealy, "Mealy: Sequence Detector '01'")
ascii_moore_diagram(moore, "Moore: Sequence Detector '01'")

# CONVERSION BETWEEN REPRESENTATIONS
print("\n=== Converting Representations ===")
print("""
Table → Diagram:
  1. Draw circle for each state
  2. Mark initial state with arrow
  3. For Mealy: label arrows with input/output
  4. For Moore: label states with output
  
Diagram → Table:
  1. List states as rows
  2. List inputs as columns
  3. Fill in next state and output
""")

📉 Minimization

🎯 Finding the Smallest Machine

State minimization reduces the number of states in a Mealy or Moore machine without changing its input-output behavior. Equivalent states are merged.

Minimization

Goal: Fewest states. Method: Partition refinement. Equivalent: Same future behavior. Mealy: Same outputs on all inputs. Moore: Same output + same transitions. Result: Minimal machine.

🔍 Equivalence📊 Partition🔗 Merge📉 Minimal

# Minimization of Mealy and Moore machines
from collections import defaultdict

print("=== State Equivalence ===")
print("""
Two states are equivalent if:
  - They produce the same output for all input sequences
  - They transition to equivalent states

Mealy: q1 ~ q2 if:
  - For all inputs a: λ(q1, a) = λ(q2, a)
  - For all inputs a: δ(q1, a) ~ δ(q2, a)

Moore: q1 ~ q2 if:
  - λ(q1) = λ(q2)
  - For all inputs a: δ(q1, a) ~ δ(q2, a)
""")

# MINIMIZATION ALGORITHM (Partition Refinement)
def minimize_mealy(machine):
    """
    Minimize a Mealy machine using partition refinement.
    """
    # Initial partition: group states by output behavior
    # For Mealy, states are equivalent if outputs match for all inputs
    
    # Actually, we start with all states in one partition
    # and refine based on output and transition behavior
    
    partitions = [set(machine.Q)]
    
    changed = True
    while changed:
        changed = False
        new_partitions = []
        
        for group in partitions:
            # Split group based on output signature and transition targets
            split = split_mealy_group(group, partitions, machine)
            new_partitions.extend(split)
            if len(split) > 1:
                changed = True
        
        partitions = new_partitions
    
    # Build minimized machine
    return build_minimized_mealy(machine, partitions)


def split_mealy_group(group, partitions, machine):
    """Split a group based on Mealy equivalence."""
    if len(group) <= 1:
        return [group]
    
    # Assign partition index
    part_index = {}
    for i, part in enumerate(partitions):
        for state in part:
            part_index[state] = i
    
    # Signature: output + target partition for each input
    signatures = defaultdict(list)
    for state in group:
        sig = []
        for s in sorted(machine.Sigma):
            out = machine.lam[(state, s)]
            target = machine.delta[(state, s)]
            sig.append((out, part_index[target]))
        signatures[tuple(sig)].append(state)
    
    return [set(states) for states in signatures.values()]


def build_minimized_mealy(machine, partitions):
    """Build minimized Mealy machine from partitions."""
    state_to_part = {}
    for i, part in enumerate(partitions):
        for state in part:
            state_to_part[state] = i
    
    new_Q = set(range(len(partitions)))
    new_q0 = state_to_part[machine.q0]
    
    new_delta = {}
    new_lam = {}
    
    for state in machine.Q:
        for s in machine.Sigma:
            next_state = machine.delta[(state, s)]
            output = machine.lam[(state, s)]
            new_delta[(state_to_part[state], s)] = state_to_part[next_state]
            new_lam[(state_to_part[state], s)] = output
    
    return MealyMachine(
        Q=new_Q,
        Sigma=machine.Sigma,
        Gamma=machine.Gamma,
        delta=new_delta,
        lam=new_lam,
        q0=new_q0
    )


# MOORE MINIMIZATION
def minimize_moore(machine):
    """Minimize a Moore machine."""
    # Initial partition: group by output
    output_groups = defaultdict(set)
    for q in machine.Q:
        output_groups[machine.lam[q]].add(q)
    
    partitions = list(output_groups.values())
    
    changed = True
    while changed:
        changed = False
        new_partitions = []
        
        for group in partitions:
            split = split_moore_group(group, partitions, machine)
            new_partitions.extend(split)
            if len(split) > 1:
                changed = True
        
        partitions = new_partitions
    
    return build_minimized_moore(machine, partitions)


def split_moore_group(group, partitions, machine):
    """Split a group based on Moore equivalence."""
    if len(group) <= 1:
        return [group]
    
    part_index = {}
    for i, part in enumerate(partitions):
        for state in part:
            part_index[state] = i
    
    signatures = defaultdict(list)
    for state in group:
        sig = tuple(part_index[machine.delta[(state, s)]] for s in sorted(machine.Sigma))
        signatures[sig].append(state)
    
    return [set(states) for states in signatures.values()]


def build_minimized_moore(machine, partitions):
    """Build minimized Moore machine."""
    state_to_part = {}
    for i, part in enumerate(partitions):
        for state in part:
            state_to_part[state] = i
    
    new_Q = set(range(len(partitions)))
    new_q0 = state_to_part[machine.q0]
    
    # Output for each new state (same for all in partition)
    new_lam = {}
    for i, part in enumerate(partitions):
        state = next(iter(part))
        new_lam[i] = machine.lam[state]
    
    new_delta = {}
    for state in machine.Q:
        for s in machine.Sigma:
            next_state = machine.delta[(state, s)]
            new_delta[(state_to_part[state], s)] = state_to_part[next_state]
    
    return MooreMachine(
        Q=new_Q,
        Sigma=machine.Sigma,
        Gamma=machine.Gamma,
        delta=new_delta,
        lam=new_lam,
        q0=new_q0
    )


# EXAMPLE: Non-minimal Mealy machine
print("\n=== Example: Minimize Mealy Machine ===")
print("""
Original machine has redundant states.
States q1 and q3 are equivalent.
""")

mealy_nonmin = MealyMachine(
    Q={'q0', 'q1', 'q2', 'q3'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('q0', '0'): 'q1', ('q0', '1'): 'q2',
        ('q1', '0'): 'q3', ('q1', '1'): 'q0',
        ('q2', '0'): 'q2', ('q2', '1'): 'q1',
        ('q3', '0'): 'q3', ('q3', '1'): 'q0',  # q3 similar to q1
    },
    lam={
        ('q0', '0'): '0', ('q0', '1'): '1',
        ('q1', '0'): '1', ('q1', '1'): '0',
        ('q2', '0'): '0', ('q2', '1'): '1',
        ('q3', '0'): '1', ('q3', '1'): '0',  # q3 same outputs as q1
    },
    q0='q0'
)

print(f"Original states: {mealy_nonmin.Q}")

minimized = minimize_mealy(mealy_nonmin)
print(f"Minimized states: {minimized.Q}")

# Verify equivalence
def test_equivalence(m1, m2, max_length=6):
    """Test if two machines are equivalent."""
    from itertools import product
    for length in range(max_length + 1):
        for symbols in product(m1.Sigma, repeat=length):
            word = ''.join(symbols)
            out1 = m1.run(word)
            out2 = m2.run(word)
            if out1 != out2:
                return False, word, out1, out2
    return True, None, None, None

equiv, counter, o1, o2 = test_equivalence(mealy_nonmin, minimized)
if equiv:
    print("✓ Machines are equivalent")
else:
    print(f"✗ Differ on '{counter}': {o1} vs {o2}")

# MOORE MINIMIZATION
print("\n=== Example: Minimize Moore Machine ===")

moore_nonmin = MooreMachine(
    Q={'A', 'B', 'C', 'D'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('A', '0'): 'B', ('A', '1'): 'C',
        ('B', '0'): 'A', ('B', '1'): 'D',
        ('C', '0'): 'D', ('C', '1'): 'A',
        ('D', '0'): 'C', ('D', '1'): 'B',
    },
    lam={'A': '0', 'B': '0', 'C': '1', 'D': '1'},
    q0='A'
)

print(f"Original states: {moore_nonmin.Q}")
minimized_moore = minimize_moore(moore_nonmin)
print(f"Minimized states: {minimized_moore.Q}")

equiv, counter, o1, o2 = test_equivalence(moore_nonmin, minimized_moore)
if equiv:
    print("✓ Machines are equivalent")
else:
    print(f"✗ Differ on '{counter}': {o1} vs {o2}")

# WHY MINIMIZE
print("\n=== Why Minimize? ===")
print("""
1. FEWER STATES
   - Less hardware (fewer flip-flops)
   - Lower power consumption
   - Smaller silicon area

2. SIMPLER LOGIC
   - Fewer transitions
   - Simpler next-state logic
   - Easier to verify

3. CANONICAL FORM
   - Unique minimal machine
   - Easy comparison
   - Standard representation

4. OPTIMIZATION
   - Foundation for further optimization
   - State encoding
   - Logic minimization
""")

🟰 Equivalence

🎯 Are Two Machines the Same?

Two Mealy (or Moore) machines are equivalent if they produce the same output for every input sequence. Testing equivalence is decidable and efficient.

Equivalence Testing

Definition: Same output for all inputs. Method: Product construction. Complexity: O(|Q1| × |Q2|). Counterexample: Shortest distinguishing string. Minimization: Check isomorphism. Decidable: Yes.

🟰 Equivalence📊 Product🔍 Counterexample✅ Decidable

# Equivalence testing for Mealy and Moore machines
from collections import deque
from itertools import product
from typing import Optional, Tuple

print("=== Equivalence of Mealy Machines ===")
print("""
Two Mealy machines M1 and M2 are equivalent if:
  For all input strings w:
    output(M1, w) = output(M2, w)

Testing algorithm (product construction):
  1. Start with (q0_1, q0_2)
  2. For each input symbol:
     - Check if outputs match
     - Move to (delta1(q1, a), delta2(q2, a))
  3. If any output mismatch → not equivalent
  4. If all reachable pairs match → equivalent

Complexity: O(|Q1| × |Q2| × |Σ|)
""")

def check_mealy_equivalence(m1, m2) -> Tuple[bool, Optional[str]]:
    """
    Check if two Mealy machines are equivalent.
    Returns (True, None) if equivalent, (False, counterexample) if not.
    """
    if m1.Sigma != m2.Sigma:
        return False, "Different alphabets"
    
    # BFS on product
    start = (m1.q0, m2.q0)
    queue = deque([(start, "")])
    visited = {start}
    
    while queue:
        (q1, q2), word = queue.popleft()
        
        for s in m1.Sigma:
            out1 = m1.lam[(q1, s)]
            out2 = m2.lam[(q2, s)]
            
            if out1 != out2:
                return False, word + s
            
            next_q1 = m1.delta[(q1, s)]
            next_q2 = m2.delta[(q2, s)]
            next_state = (next_q1, next_q2)
            
            if next_state not in visited:
                visited.add(next_state)
                queue.append((next_state, word + s))
    
    return True, None


def check_moore_equivalence(m1, m2) -> Tuple[bool, Optional[str]]:
    """
    Check if two Moore machines are equivalent.
    """
    if m1.Sigma != m2.Sigma:
        return False, "Different alphabets"
    
    # Check initial outputs
    if m1.lam[m1.q0] != m2.lam[m2.q0]:
        return False, ""
    
    start = (m1.q0, m2.q0)
    queue = deque([(start, "")])
    visited = {start}
    
    while queue:
        (q1, q2), word = queue.popleft()
        
        for s in m1.Sigma:
            next_q1 = m1.delta[(q1, s)]
            next_q2 = m2.delta[(q2, s)]
            
            out1 = m1.lam[next_q1]
            out2 = m2.lam[next_q2]
            
            if out1 != out2:
                return False, word + s
            
            next_state = (next_q1, next_q2)
            if next_state not in visited:
                visited.add(next_state)
                queue.append((next_state, word + s))
    
    return True, None


# EXAMPLE 1: Two equivalent Mealy machines
print("\n=== Example 1: Equivalent Mealy Machines ===")

m1 = MealyMachine(
    Q={'q0', 'q1'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('q0', '0'): 'q0', ('q0', '1'): 'q1',
        ('q1', '0'): 'q0', ('q1', '1'): 'q1',
    },
    lam={
        ('q0', '0'): '0', ('q0', '1'): '1',
        ('q1', '0'): '0', ('q1', '1'): '0',
    },
    q0='q0'
)

# Equivalent machine (renamed states)
m2 = MealyMachine(
    Q={'A', 'B'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('A', '0'): 'A', ('A', '1'): 'B',
        ('B', '0'): 'A', ('B', '1'): 'B',
    },
    lam={
        ('A', '0'): '0', ('A', '1'): '1',
        ('B', '0'): '0', ('B', '1'): '0',
    },
    q0='A'
)

equiv, counter = check_mealy_equivalence(m1, m2)
if equiv:
    print("✓ Machines are equivalent")
else:
    print(f"✗ Not equivalent. Counterexample: '{counter}'")

# EXAMPLE 2: Non-equivalent machines
print("\n=== Example 2: Non-Equivalent Machines ===")

m3 = MealyMachine(
    Q={'q0', 'q1'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('q0', '0'): 'q0', ('q0', '1'): 'q1',
        ('q1', '0'): 'q0', ('q1', '1'): 'q1',
    },
    lam={
        ('q0', '0'): '0', ('q0', '1'): '1',
        ('q1', '0'): '1',  # different!
        ('q1', '1'): '0',
    },
    q0='q0'
)

equiv, counter = check_mealy_equivalence(m1, m3)
if equiv:
    print("✓ Machines are equivalent")
else:
    print(f"✗ Not equivalent. Counterexample: '{counter}'")
    print(f"  M1 output: {m1.run(counter)}")
    print(f"  M3 output: {m3.run(counter)}")

# EXAMPLE 3: Moore equivalence
print("\n=== Example 3: Moore Equivalence ===")

m4 = MooreMachine(
    Q={'A', 'B'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('A', '0'): 'A', ('A', '1'): 'B',
        ('B', '0'): 'A', ('B', '1'): 'B',
    },
    lam={'A': '0', 'B': '1'},
    q0='A'
)

m5 = MooreMachine(
    Q={'X', 'Y'},
    Sigma={'0', '1'},
    Gamma={'0', '1'},
    delta={
        ('X', '0'): 'X', ('X', '1'): 'Y',
        ('Y', '0'): 'X', ('Y', '1'): 'Y',
    },
    lam={'X': '0', 'Y': '1'},
    q0='X'
)

equiv, counter = check_moore_equivalence(m4, m5)
if equiv:
    print("✓ Moore machines are equivalent")
else:
    print(f"✗ Not equivalent. Counterexample: '{counter}'")

# MINIMIZATION + EQUIVALENCE
print("\n=== Minimization + Equivalence ===")
print("""
Two machines are equivalent iff:
  their minimal forms are isomorphic.

Algorithm:
  1. Minimize M1 → M1_min
  2. Minimize M2 → M2_min
  3. Check if M1_min and M2_min are isomorphic

This is often the most efficient approach.
""")

# DECISION PROBLEMS
print("\n=== Decidable Problems ===")
print("""
For Mealy and Moore machines, these are DECIDABLE:

1. EQUIVALENCE
   "Do M1 and M2 produce same output for all inputs?"
   → Product construction
   → O(|Q1| × |Q2|)

2. MINIMIZATION
   "What is the smallest equivalent machine?"
   → Partition refinement
   → O(n log n)

3. EMPTINESS OF OUTPUT
   "Does M ever produce output X?"
   → Reachability
   → O(|Q|)

4. UNIVERSALITY
   "Does M produce X for all inputs?"
   → Complement + emptiness
   → Decidable

5. LANGUAGE EQUIVALENCE
   "Do M1 and M2 accept same inputs?"
   → Reduce to DFA equivalence
   → Decidable
""")

# COMPLEXITY
print("\n=== Complexity Summary ===")
print(f"{'Problem':<25} {'Complexity':<20} {'Method':<30}")
print("-" * 75)
print(f"{'Equivalence':<25} {'O(|Q1|×|Q2|)':<20} {'Product construction':<30}")
print(f"{'Minimization':<25} {'O(n log n)':<20} {'Partition refinement':<30}")
print(f"{'Isomorphism':<25} {'O(n)':<20} {'BFS mapping':<30}")
print(f"{'Membership':<25} {'O(|w|)':<20} {'Simulation':<30}")

💼 Applications

🎯 Real-World Impact

Mealy and Moore machines are used everywhere: digital circuits, protocol design, compilers, control systems, and embedded devices. They're the foundation of sequential logic design.

Application Areas

Digital design: Controllers, FSMs. Protocols: TCP, USB, UART. Compilers: Lexers, parsers. Embedded: Traffic lights, appliances. Games: AI, state management. VLSI: Test generation.

🔌 Digital Design🌐 Protocols💻 Compilers🎮 Games

# Applications of Mealy and Moore machines
print("=== 1. Digital Circuit Design ===")
print("""
Finite State Machines (FSMs) are the foundation of digital design:

Moore FSM:
  - Output registered (stable)
  - Used in: control units, safety systems
  - Example: Traffic light controller

Mealy FSM:
  - Output combinational (fast)
  - Used in: data path control, protocol handlers
  - Example: UART transmitter

Hardware Description Languages:
  - Verilog: always @(posedge clk)
  - VHDL: process(clk)
  - Both support Mealy and Moore

Design flow:
  1. Specify FSM (state diagram)
  2. Choose Mealy or Moore
  3. Encode states (binary, one-hot)
  4. Synthesize to gates
  5. Implement on FPGA/ASIC
""")

print("\n=== 2. Communication Protocols ===")
print("""
Protocols are naturally modeled as state machines:

UART (Serial):
  States: IDLE, START, DATA, PARITY, STOP
  Mealy: output data on transitions
  Moore: output on states

TCP Connection:
  States: CLOSED, LISTEN, SYN_SENT, ESTABLISHED, ...
  Events: SYN, ACK, FIN, DATA
  Output: send packets

USB:
  States: ATTACHED, POWERED, DEFAULT, ADDRESSED, CONFIGURED
  Complex state machine with many transitions

SPI/I2C:
  Master/slave state machines
  Clock synchronization
  Data transfer
""")

print("\n=== 3. Compilers and Language Processing ===")
print("""
Lexical Analysis:
  - Tokenizer as Mealy machine
  - Input: characters
  - Output: tokens
  - States: token types

Example: Number lexer
  States: START, INT, FLOAT, EXP
  Input: digits, '.', 'e', '+', '-'
  Output: token type

Parsing:
  - LR parsers use state machines
  - Shift/reduce actions
  - State stack

Regular Expressions:
  - Compiled to FSM
  - Mealy for matching
  - Moore for acceptance
""")

print("\n=== 4. Embedded Systems ===")
print("""
Traffic Light Controller:
  Moore machine (safety-critical)
  States: NS_G, NS_Y, EW_G, EW_Y
  Output: which lights are on
  Input: timer

Vending Machine:
  Mealy machine (fast response)
  States: 0, 5, 10, 15, 20
  Input: coins
  Output: dispense, return

Washing Machine:
  States: FILL, WASH, RINSE, SPIN, DONE
  Input: start, timer
  Output: motor, valve, pump

Elevator:
  States: IDLE, MOVING_UP, MOVING_DOWN, DOOR_OPEN
  Input: floor requests, sensors
  Output: motor, door
""")

print("\n=== 5. Game Development ===")
print("""
Game AI:
  - Enemy behavior states: PATROL, CHASE, ATTACK, FLEE
  - Boss patterns: phase 1, 2, 3
  - NPC dialogue states

UI State Machines:
  - Menu navigation
  - Character animation
  - Game flow: MENU, PLAYING, PAUSED, GAME_OVER

Example: Platformer character
  States: IDLE, RUN, JUMP, FALL, ATTACK
  Input: arrow keys, space
  Output: animation frame
""")

print("\n=== 6. VLSI and Testing ===")
print("""
VLSI Design:
  - FSM for control logic
  - Mealy for datapath control
  - Moore for control signals

Test Pattern Generation:
  - FSM for test sequencing
  - Fault coverage
  - Built-in self-test (BIST)

Formal Verification:
  - Model checking
  - Equivalence checking
  - Property verification
""")

# PRACTICAL EXAMPLE: TRAFFIC LIGHT
print("\n=== Practical Example: Traffic Light Controller ===")

class TrafficLight:
    """Moore machine for traffic light."""
    def __init__(self):
        self.state = 'NS_G'
        self.outputs = {
            'NS_G': {'NS': 'green', 'EW': 'red'},
            'NS_Y': {'NS': 'yellow', 'EW': 'red'},
            'EW_G': {'NS': 'red', 'EW': 'green'},
            'EW_Y': {'NS': 'red', 'EW': 'yellow'},
        }
    
    def step(self, input_signal):
        """Input: 'timer' or 'emergency'."""
        if input_signal == 'emergency':
            # Emergency: all red
            return {'NS': 'red', 'EW': 'red'}
        
        transitions = {
            'NS_G': 'NS_Y',
            'NS_Y': 'EW_G',
            'EW_G': 'EW_Y',
            'EW_Y': 'NS_G',
        }
        self.state = transitions[self.state]
        return self.outputs[self.state]

# Simulate
traffic = TrafficLight()
print("Traffic light simulation:")
print(f"Initial: {traffic.outputs[traffic.state]}")

for i in range(4):
    output = traffic.step('timer')
    print(f"  After timer {i+1}: {output}")

# EMERGENCY
print(f"Emergency: {traffic.step('emergency')}")

# PRACTICAL EXAMPLE: VENDING MACHINE
print("\n=== Practical Example: Vending Machine ===")

class VendingMachine:
    """Mealy machine for vending machine."""
    def __init__(self):
        self.state = 0  # cents
        self.values = {'nickel': 5, 'dime': 10, 'quarter': 25}
    
    def insert(self, coin):
        """Insert coin, return (dispense, change)."""
        if coin not in self.values:
            return (False, 0)
        
        self.state += self.values[coin]
        
        if self.state >= 25:
            change = self.state - 25
            self.state = 0
            return (True, change)
        else:
            return (False, 0)

# Simulate
vm = VendingMachine()
print("Vending machine simulation (product = 25¢):")
print(f"Insert dime: {vm.insert('dime')}")      # (False, 0)
print(f"Insert dime: {vm.insert('dime')}")      # (False, 0)
print(f"Insert nickel: {vm.insert('nickel')}")  # (True, 0)
print()
print(f"Insert quarter: {vm.insert('quarter')}") # (True, 0)
print()
print(f"Insert dime: {vm.insert('dime')}")      # (False, 0)
print(f"Insert quarter: {vm.insert('quarter')}") # (True, 10) — overpay

# SUMMARY
print("\n=== Application Summary ===")
print(f"{'Domain':<25} {'Use Case':<30} {'Type':<15}")
print("-" * 75)
print(f"{'Digital Design':<25} {'Control units':<30} {'Both':<15}")
print(f"{'Protocols':<25} {'UART, TCP':<30} {'Both':<15}")
print(f"{'Compilers':<25} {'Lexers':<30} {'Mealy':<15}")
print(f"{'Embedded':<25} {'Traffic lights':<30} {'Moore':<15}")
print(f"{'Games':<25} {'AI behavior':<30} {'Both':<15}")
print(f"{'VLSI':<25} {'Test generation':<30} {'Both':<15}")
print(f"{'Automotive':<25} {'ECU control':<30} {'Moore':<15}")
print(f"{'Aerospace':<25} {'Flight control':<30} {'Moore':<15}")

🔌 Hardware Design

🎯 From State Machines to Silicon

Mealy and Moore machines map directly to digital hardware: states become flip-flops, transitions become combinational logic, and outputs become either combinational (Mealy) or registered (Moore) signals.

Hardware Mapping

States: Flip-flops (registers). Transitions: Next-state logic. Mealy output: Combinational logic. Moore output: Registered output. Clock: Synchronizes state changes. Reset: Initializes to q₀.

🔲 Flip-Flops🔣 Logic Gates⏰ Clock🔄 Reset

# Hardware design of Mealy and Moore machines
print("=== Digital Logic Structure ===")
print("""
MEALY MACHINE HARDWARE:

  ┌─────────────────────────────────────────┐
  │                                         │
  │   ┌──────────────┐    ┌──────────────┐  │
  │   │  Next State  │    │   Output     │  │
  │   │    Logic     │    │    Logic     │  │
  │   └──────┬───────┘    └──────┬───────┘  │
  │          │                   │          │
  │          │                   │          │
  │   ┌──────▼───────┐           │          │
  │   │   Flip-Flops │           │          │
  │   │   (State)    │           │          │
  │   └──────┬───────┘           │          │
  │          │                   │          │
  │          └───────────────────┤          │
  │                              │          │
  │   Input ─────────────────────┤          │
  │                              │          │
  │                              ▼          │
  │                           Output        │
  └─────────────────────────────────────────┘

MOORE MACHINE HARDWARE:

  ┌─────────────────────────────────────────┐
  │                                         │
  │   ┌──────────────┐                      │
  │   │  Next State  │                      │
  │   │    Logic     │                      │
  │   └──────┬───────┘                      │
  │          │                              │
  │   ┌──────▼───────┐    ┌──────────────┐  │
  │   │   Flip-Flops │    │   Output     │  │
  │   │   (State)    │───→│    Logic     │  │
  │   └──────┬───────┘    └──────┬───────┘  │
  │          │                   │          │
  │          │                   ▼          │
  │   Input ─┘                Output        │
  └─────────────────────────────────────────┘
""")

# VHDL EXAMPLE
print("\n=== VHDL Example: Mealy Machine ===")
print("""
-- Mealy machine: sequence detector "01"
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;

entity mealy_seq is
    Port ( clk    : in  STD_LOGIC;
           reset  : in  STD_LOGIC;
           input  : in  STD_LOGIC;
           output : out STD_LOGIC);
end mealy_seq;

architecture Behavioral of mealy_seq is
    type state_type is (q0, q1, q2);
    signal state, next_state : state_type;
begin
    -- State register
    process(clk, reset)
    begin
        if reset = '1' then
            state <= q0;
        elsif rising_edge(clk) then
            state <= next_state;
        end if;
    end process;

    -- Next state logic
    process(state, input)
    begin
        case state is
            when q0 =>
                if input = '0' then
                    next_state <= q1;
                else
                    next_state <= q0;
                end if;
            when q1 =>
                if input = '0' then
                    next_state <= q1;
                else
                    next_state <= q2;
                end if;
            when q2 =>
                if input = '0' then
                    next_state <= q1;
                else
                    next_state <= q0;
                end if;
        end case;
    end process;

    -- Mealy output logic (combinational)
    process(state, input)
    begin
        if state = q1 and input = '1' then
            output <= '1';  -- detected "01"
        else
            output <= '0';
        end if;
    end process;
end Behavioral;
""")

# VERILOG EXAMPLE
print("\n=== Verilog Example: Moore Machine ===")
print("""
// Moore machine: traffic light controller
module moore_traffic (
    input clk,
    input reset,
    input timer,
    output reg [1:0] ns_light,  // 00=red, 01=yellow, 10=green
    output reg [1:0] ew_light
);

    // State encoding
    localparam NS_G = 2'b00;
    localparam NS_Y = 2'b01;
    localparam EW_G = 2'b10;
    localparam EW_Y = 2'b11;
    
    reg [1:0] state, next_state;
    
    // State register
    always @(posedge clk or posedge reset) begin
        if (reset)
            state <= NS_G;
        else
            state <= next_state;
    end
    
    // Next state logic
    always @(*) begin
        case (state)
            NS_G: next_state = timer ? NS_Y : NS_G;
            NS_Y: next_state = timer ? EW_G : NS_Y;
            EW_G: next_state = timer ? EW_Y : EW_G;
            EW_Y: next_state = timer ? NS_G : EW_Y;
            default: next_state = NS_G;
        endcase
    end
    
    // Moore output logic (registered)
    always @(posedge clk or posedge reset) begin
        if (reset) begin
            ns_light <= 2'b10;  // green
            ew_light <= 2'b00;  // red
        end else begin
            case (next_state)
                NS_G: begin ns_light <= 2'b10; ew_light <= 2'b00; end
                NS_Y: begin ns_light <= 2'b01; ew_light <= 2'b00; end
                EW_G: begin ns_light <= 2'b00; ew_light <= 2'b10; end
                EW_Y: begin ns_light <= 2'b00; ew_light <= 2'b01; end
            endcase
        end
    end
endmodule
""")

# STATE ENCODING
print("\n=== State Encoding ===")
print("""
Binary Encoding:
  - log2(n) flip-flops for n states
  - Compact but more complex logic
  - Example: 4 states → 2 flip-flops
  
One-Hot Encoding:
  - n flip-flops for n states
  - Simpler logic, faster
  - More flip-flops
  - Example: 4 states → 4 flip-flops
  
Gray Encoding:
  - Only one bit changes between adjacent states
  - Reduces glitches
  - Good for low-power

Trade-offs:
  - Binary: fewer FFs, more logic
  - One-hot: more FFs, simpler logic
  - Choice depends on FPGA/ASIC target
""")

# TIMING
print("\n=== Timing Considerations ===")
print("""
Mealy Machine:
  - Output changes with input
  - May glitch during input changes
  - Setup time: input → output
  - Hold time: input must be stable
  
Moore Machine:
  - Output changes only on clock edge
  - No glitches
  - Output stable for entire cycle
  - Easier timing analysis

Clock frequency limited by:
  - Longest combinational path
  - Mealy: input → output path
  - Moore: state → output path

For high-speed designs:
  - Moore preferred for stability
  - Mealy for reduced latency
""")

# IMPLEMENTATION
print("\n=== Simple Hardware Implementation ===")

class HardwareFSM:
    """Simulate a hardware FSM with clock."""
    def __init__(self, machine_type='moore'):
        self.machine_type = machine_type
        self.state = 0
        self.clock = 0
    
    def clock_edge(self, inputs):
        """Simulate one clock edge."""
        self.clock += 1
        # In real hardware, this would be a synchronous update
        return self.state

# SUMMARY
print("\n=== Hardware Design Summary ===")
print(f"{'Aspect':<25} {'Mealy':<25} {'Moore':<25}")
print("-" * 75)
print(f"{'Output logic':<25} {'Combinational':<25} {'Registered':<25}")
print(f"{'Flip-flops':<25} {'log2(n)':<25} {'log2(n)':<25}")
print(f"{'Glitches':<25} {'Possible':<25} {'None':<25}")
print(f"{'Timing':<25} {'Input→Output':<25} {'Clock→Output':<25}")
print(f"{'Speed':<25} {'Faster':<25} {'Slower':<25}")
print(f"{'Area':<25} {'Less':<25} {'More':<25}")
print(f"{'Safety':<25} {'Less':<25} {'More':<25}")

💻 Software Modeling

🎯 State Machines in Code

Mealy and Moore machines are widely used in software: protocol implementations, game AI, parsers, and workflow engines. They provide a clean, maintainable way to model stateful systems.

Software Patterns

State pattern: OOP implementation. Enum + switch: Simple approach. Table-driven: Data-driven FSM. Statechart: Hierarchical FSM. Actor model: Concurrent FSM. Workflow: Business processes.

🎨 State Pattern📋 Table-driven🔀 Hierarchical⚡ Concurrent

# Software modeling with Mealy and Moore machines
print("=== Software Implementation Patterns ===")
print("""
1. ENUM + SWITCH (simple)
2. STATE PATTERN (OOP)
3. TABLE-DRIVEN (data)
4. HIERARCHICAL (statecharts)
5. ACTOR MODEL (concurrent)
""")

# PATTERN 1: ENUM + SWITCH
print("\n=== Pattern 1: Enum + Switch ===")
from enum import Enum

class State(Enum):
    IDLE = 0
    RUNNING = 1
    PAUSED = 2
    STOPPED = 3

class SimpleFSM:
    """Simple enum-based FSM."""
    def __init__(self):
        self.state = State.IDLE
    
    def process(self, event):
        if self.state == State.IDLE:
            if event == 'start':
                self.state = State.RUNNING
                return 'started'
        elif self.state == State.RUNNING:
            if event == 'pause':
                self.state = State.PAUSED
                return 'paused'
            elif event == 'stop':
                self.state = State.STOPPED
                return 'stopped'
        elif self.state == State.PAUSED:
            if event == 'resume':
                self.state = State.RUNNING
                return 'resumed'
            elif event == 'stop':
                self.state = State.STOPPED
                return 'stopped'
        elif self.state == State.STOPPED:
            if event == 'reset':
                self.state = State.IDLE
                return 'reset'
        return 'no_change'

fsm = SimpleFSM()
events = ['start', 'pause', 'resume', 'stop', 'reset']
print("Enum+Switch FSM:")
for e in events:
    output = fsm.process(e)
    print(f"  {e} → {fsm.state.name} ({output})")

# PATTERN 2: TABLE-DRIVEN
print("\n=== Pattern 2: Table-Driven FSM ===")

class TableDrivenFSM:
    """Table-driven FSM (data-driven)."""
    def __init__(self, transitions, outputs, initial):
        self.transitions = transitions  # (state, event) -> next_state
        self.outputs = outputs          # (state, event) -> output
        self.state = initial
    
    def process(self, event):
        key = (self.state, event)
        if key not in self.transitions:
            return 'invalid'
        output = self.outputs.get(key, '')
        self.state = self.transitions[key]
        return output

# Define FSM as data
transitions = {
    ('idle', 'start'): 'running',
    ('running', 'pause'): 'paused',
    ('running', 'stop'): 'stopped',
    ('paused', 'resume'): 'running',
    ('paused', 'stop'): 'stopped',
    ('stopped', 'reset'): 'idle',
}
outputs = {
    ('idle', 'start'): 'started',
    ('running', 'pause'): 'paused',
    ('running', 'stop'): 'stopped',
    ('paused', 'resume'): 'resumed',
    ('paused', 'stop'): 'stopped',
    ('stopped', 'reset'): 'reset',
}

tdfsm = TableDrivenFSM(transitions, outputs, 'idle')
print("Table-driven FSM:")
for e in ['start', 'pause', 'resume', 'stop']:
    out = tdfsm.process(e)
    print(f"  {e} → {tdfsm.state} ({out})")

# PATTERN 3: STATE PATTERN (OOP)
print("\n=== Pattern 3: State Pattern (OOP) ===")

class StateBase:
    def on_event(self, event):
        return self

class IdleState(StateBase):
    def on_event(self, event):
        if event == 'start':
            return RunningState()
        return self
    def __str__(self):
        return 'Idle'

class RunningState(StateBase):
    def on_event(self, event):
        if event == 'pause':
            return PausedState()
        elif event == 'stop':
            return StoppedState()
        return self
    def __str__(self):
        return 'Running'

class PausedState(StateBase):
    def on_event(self, event):
        if event == 'resume':
            return RunningState()
        elif event == 'stop':
            return StoppedState()
        return self
    def __str__(self):
        return 'Paused'

class StoppedState(StateBase):
    def on_event(self, event):
        if event == 'reset':
            return IdleState()
        return self
    def __str__(self):
        return 'Stopped'

class StatePatternFSM:
    def __init__(self):
        self.state = IdleState()
    def process(self, event):
        self.state = self.state.on_event(event)
        return str(self.state)

spfsm = StatePatternFSM()
print("State pattern FSM:")
for e in ['start', 'pause', 'resume', 'stop', 'reset']:
    state = spfsm.process(e)
    print(f"  {e} → {state}")

# PATTERN 4: HIERARCHICAL (Statecharts)
print("\n=== Pattern 4: Hierarchical FSM ===")
print("""
Statecharts (Harel, 1987):
  - Hierarchical states (nested)
  - Parallel regions
  - History states
  - Guards and actions

Example: Game character
  Character
    ├── Alive
    │   ├── Idle
    │   ├── Running
    │   └── Jumping
    └── Dead

Transitions:
  Alive --hit--> Dead
  Idle --move--> Running
  Running --jump--> Jumping
  Jumping --land--> Idle
""")

# PATTERN 5: ACTOR MODEL
print("\n=== Pattern 5: Actor Model ===")
print("""
Actor model (Hewitt, 1973):
  - Each FSM is an actor
  - Actors communicate via messages
  - Concurrent and distributed

Example: TCP connection actor
  States: CLOSED, LISTEN, SYN_SENT, ESTABLISHED
  Messages: SYN, SYN_ACK, ACK, FIN
  
  Actor processes messages:
    receive(msg):
      state, output = transition(state, msg)
      send(output)
      become(state)
""")

# COMPARISON
print("\n=== Pattern Comparison ===")
print(f"{'Pattern':<25} {'Pros':<30} {'Cons':<30}")
print("-" * 85)
print(f"{'Enum + Switch':<25} {'Simple, fast':<30} {'Not scalable':<30}")
print(f"{'Table-Driven':<25} {'Data-driven, flexible':<30} {'No type safety':<30}")
print(f"{'State Pattern':<25} {'OOP, extensible':<30} {'More classes':<30}")
print(f"{'Hierarchical':<25} {'Manages complexity':<30} {'Complex to implement':<30}")
print(f"{'Actor Model':<25} {'Concurrent, distributed':<30} {'Message overhead':<30}")

# PRACTICAL EXAMPLE: GAME AI
print("\n=== Practical Example: Game AI (State Pattern) ===")

class EnemyState:
    def update(self, enemy, player_dist):
        return self
    def __str__(self):
        return self.__class__.__name__

class Patrol(EnemyState):
    def update(self, enemy, dist):
        if dist < 5:
            print("  Enemy spotted player! Chasing...")
            return Chase()
        print("  Patrolling...")
        return self

class Chase(EnemyState):
    def update(self, enemy, dist):
        if dist > 10:
            print("  Lost player. Returning to patrol.")
            return Patrol()
        elif dist < 2:
            print("  Player in range! Attacking!")
            return Attack()
        print("  Chasing player...")
        return self

class Attack(EnemyState):
    def update(self, enemy, dist):
        if dist > 3:
            print("  Player escaped. Chasing again.")
            return Chase()
        print("  Attacking player!")
        return self

class Enemy:
    def __init__(self):
        self.state = Patrol()
        self.health = 100
    
    def update(self, player_dist):
        self.state = self.state.update(self, player_dist)

# Simulate
print("Game AI simulation:")
enemy = Enemy()
distances = [15, 12, 8, 4, 1, 3, 6, 12, 20]
for d in distances:
    print(f"Distance {d}:")
    enemy.update(d)

# BEST PRACTICES
print("\n=== Best Practices ===")
print("""
1. KEEP IT SIMPLE
   - Use enum+switch for simple FSMs
   - State pattern for complex FSMs

2. SEPARATE CONCERNS
   - States: behavior
   - Transitions: logic
   - Outputs: actions

3. TEST THOROUGHLY
   - Test all transitions
   - Test edge cases
   - Test invalid inputs

4. DOCUMENT
   - State diagram
   - Transition table
   - Output specification

5. USE TOOLS
   - State machine libraries
   - Code generation
   - Visualization tools
""")

🚀 Future: MM in Modern Computing

🎯 Where Mealy & Moore Are Going

Mealy and Moore machines remain fundamental to computing. Modern applications include AI behavior trees, quantum finite automata, and advanced hardware design. Their principles are more relevant than ever.

Future Directions

AI: Behavior trees, state machines. Quantum: Quantum FSM. Hardware: High-level synthesis. IoT: Edge computing. Formal: Verification. ML: Learned FSMs.

🤖 AI⚛️ Quantum🔌 Hardware🌐 IoT

# Future of Mealy and Moore machines
print("=== 1. AI and Behavior Trees ===")
print("""
Behavior Trees (BTs):
  - Hierarchical state machines for AI
  - Used in game AI, robotics
  - Nodes: sequence, selector, action, condition

Comparison with FSM:
  - BTs are more modular
  - BTs are more scalable
  - BTs can be learned from data

Hybrid approaches:
  - FSM for high-level states
  - BT for low-level behaviors
  - Example: Boss AI with phases

Tools:
  - Unreal Engine Behavior Trees
  - ROS (Robot Operating System)
  - Custom implementations
""")

print("\n=== 2. Quantum Finite Automata ===")
print("""
Quantum FSM:
  - States are quantum superpositions
  - Transitions are unitary operators
  - Measurement at the end

Types:
  - Measure-once QFA
  - Measure-many QFA
  - Latvian QFA

Advantages:
  - Exponential state compression
  - Quantum parallelism
  - New computational capabilities

Applications:
  - Quantum protocol design
  - Quantum error correction
  - Quantum algorithms

Challenges:
  - Decoherence
  - Error correction
  - Limited qubits
""")

print("\n=== 3. High-Level Synthesis ===")
print("""
HLS (High-Level Synthesis):
  - Compile C/C++ to hardware
  - FSM extraction from code
  - Automatic Mealy/Moore selection

Tools:
  - Xilinx Vitis HLS
  - Intel HLS Compiler
  - Cadence Stratus

Benefits:
  - Faster design time
  - Higher abstraction
  - Automatic optimization

Future:
  - AI-assisted HLS
  - Automatic state encoding
  - Formal verification integration
""")

print("\n=== 4. IoT and Edge Computing ===")
print("""
Edge devices:
  - Low power
  - Real-time
  - Limited resources

FSM advantages:
  - Predictable timing
  - Low memory
  - Easy to verify

Applications:
  - Smart home controllers
  - Industrial automation
  - Wearable devices
  - Automotive ECUs

Trends:
  - TinyML with FSMs
  - FSM-based security
  - Energy harvesting
""")

print("\n=== 5. Formal Verification ===")
print("""
Model Checking:
  - Verify FSM properties
  - Temporal logic (LTL, CTL)
  - Automatic verification

Tools:
  - NuSMV
  - SPIN
  - UPPAAL

Applications:
  - Safety-critical systems
  - Protocol verification
  - Hardware verification

Future:
  - Integration with design tools
  - AI-assisted verification
  - Quantum verification
""")

print("\n=== 6. Machine Learning and FSMs ===")
print("""
Learning FSMs:
  - Learn from input-output data
  - Automata learning (Angluin's L*)
  - Neural FSM

Applications:
  - Program synthesis
  - Protocol reverse engineering
  - Behavior modeling

Neural FSM:
  - Differentiable state machines
  - Trainable transitions
  - End-to-end learning

Future:
  - Hybrid neural-symbolic systems
  - Interpretable AI
  - Verified learning
""")

print("\n=== 7. New Frontiers ===")
print("""
Continuous-State FSM:
  - States in continuous space
  - Hybrid automata
  - Cyber-physical systems

Probabilistic FSM:
  - Markov chains
  - Hidden Markov Models
  - Reinforcement learning

Timed FSM:
  - Time constraints
  - Real-time systems
  - Timed automata

Open Problems:
  - Scalable verification
  - Learning complex FSMs
  - Quantum FSM applications
""")

print("\n=== Timeline ===")
print("""
Past:
  1950s: Mealy and Moore machines defined
  1960s: FSM in digital design
  1980s: Statecharts (Harel)
  1990s: Model checking
  2000s: Behavior trees

Present:
  2010s: HLS, IoT
  2020s: AI integration
  2025: Quantum FSM research

Future:
  2030s: Neural-symbolic FSM?
  2040s: Quantum FSM applications?
  2050s: New paradigms?
  Beyond: Unknown
""")

print("\n=== Final Thoughts ===")
print("""
Mealy and Moore machines are:

  - Simple to understand
  - Powerful in practice
  - Fundamental to computing
  - Still relevant after 60+ years

They show us:
  - State + input → output
  - Simple rules → complex behavior
  - Hardware and software are connected

Whether we design chips, build AI,
or model protocols, Mealy and Moore
will be there.

"All computation is state machines,
 all the way down."

Keep exploring. Keep building.
""")