🧠 FST Fundamentals

🎯 What is a Finite State Transducer?

A Finite State Transducer (FST) is a finite automaton that reads an input string and produces an output string. Unlike acceptors (DFA/NFA) which only say "yes" or "no", transducers transform input into output. FSTs are fundamental to natural language processing, speech recognition, and morphological analysis.

Why FSTs Matter

Transformation: Input → Output. NLP: Morphological analysis. Speech: Pronunciation modeling. Compilers: Lexical analysis. Composition: Chain transformations. Bidirectional: Some FSTs are invertible.

📌 Transducer📌 Input→Output📌 NLP📌 Composition

# Finite State Transducers — the big picture
# FSTs are automata that read input and produce output.

# CONCEPTUAL OVERVIEW
print("""
=== Finite State Transducers ===

An FST is like a DFA but with output:

  DFA:  Input → Accept/Reject
  FST:  Input → Output

Formal: M = (Q, Σ, Γ, δ, λ, q₀, F)

  Q  = finite states
  Σ  = input alphabet
  Γ  = output alphabet
  δ  = transition function Q × Σ → Q
  λ  = output function Q × Σ → Γ*
  q₀ = initial state
  F  = final states

Key difference from Mealy/Moore:
  - Mealy/Moore: output single symbol
  - FST: output string (possibly empty)
""")

# SIMPLE FST IMPLEMENTATION
class FST:
    """
    Finite State Transducer.
    
    Transitions: (state, input_symbol) → (next_state, output_string)
    """
    def __init__(self, Q, Sigma, Gamma, delta, q0, F):
        self.Q = Q
        self.Sigma = Sigma
        self.Gamma = Gamma
        self.delta = delta  # (state, input) -> (next_state, output)
        self.q0 = q0
        self.F = F
        self.state = q0
    
    def reset(self):
        self.state = self.q0
    
    def step(self, input_symbol):
        """Process one input symbol, return output string."""
        if (self.state, input_symbol) not in self.delta:
            return ''  # no transition
        next_state, output = self.delta[(self.state, input_symbol)]
        self.state = next_state
        return output
    
    def run(self, input_string):
        """Transduce entire string. Returns (output, final_state, accepted)."""
        self.reset()
        outputs = []
        for symbol in input_string:
            outputs.append(self.step(symbol))
        final_state = self.state
        accepted = final_state in self.F
        return ''.join(outputs), final_state, accepted
    
    def trace(self, input_string):
        """Detailed trace."""
        self.reset()
        print(f"Initial: {self.state}")
        for symbol in input_string:
            if (self.state, symbol) in self.delta:
                next_state, output = self.delta[(self.state, symbol)]
                print(f"  {self.state} --{symbol}/{output}--> {next_state}")
                self.state = next_state
            else:
                print(f"  {self.state} --{symbol}/?--> (no transition)")
                break
        print(f"Final: {self.state} {'✓' if self.state in self.F else '✗'}")


# EXAMPLE 1: Pluralizer (English)
print("=== Example 1: English Pluralizer ===")
print("""
Simple FST that adds 's' to nouns:

  States: {q0, q1}
  Input: {a-z}
  Output: {a-z, s}
  
  q0 --letter/letter--> q0
  q0 --end/ε--> q1
  q1 --ε/s--> q1 (final)
  
Simplified: just append 's' at the end.
""")

# Simpler implementation: append 's'
class Pluralizer:
    """Append 's' to input."""
    def transduce(self, word):
        return word + 's'

pluralizer = Pluralizer()
words = ['cat', 'dog', 'house', 'computer']
print("\nPluralization:")
for w in words:
    print(f"  {w} → {pluralizer.transduce(w)}")

# EXAMPLE 2: Number to Words
print("\n=== Example 2: Number to Words ===")
print("""
FST that converts digits to words:

  0 → zero
  1 → one
  2 → two
  ...
  9 → nine

States: {q0, q1, q2, ...}
Input: {0-9}
Output: {zero, one, two, ...}
""")

digit_to_word = {
    '0': 'zero', '1': 'one', '2': 'two', '3': 'three', '4': 'four',
    '5': 'five', '6': 'six', '7': 'seven', '8': 'eight', '9': 'nine'
}

def number_to_words(num_str):
    return ' '.join(digit_to_word[d] for d in num_str)

print("\nNumber to words:")
for n in ['42', '123', '2024']:
    print(f"  {n} → {number_to_words(n)}")

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

1. TRANSDUCTION
   - Input string → Output string
   - Can be one-to-one, one-to-many, many-to-one

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

3. DETERMINISTIC vs NON-DETERMINISTIC
   - Deterministic FST (DFST)
   - Non-deterministic FST (NFST)

4. COMPOSITION
   - Chain FSTs: FST1 ∘ FST2
   - Output of one is input to next

5. INVERSION
   - Some FSTs are invertible
   - Swap input and output

6. WEIGHTED FSTs
   - Add weights/probabilities
   - Used in speech recognition

7. APPLICATIONS
   - NLP: morphology, phonology
   - Speech: pronunciation
   - Compilers: tokenization
""")

📐 Formal Definition

🎯 The 7-Tuple

A Finite State Transducer is formally defined as a 7-tuple M = (Q, Σ, Γ, δ, λ, q₀, F) where Q is states, Σ is input alphabet, Γ is output alphabet, δ is transition function, λ is output function, q₀ is initial state, and F is final states.

Formal Components

Q: Finite states. Σ: Input alphabet. Γ: Output alphabet. δ: Q × Σ → Q. λ: Q × Σ → Γ*. q₀: Initial state. F: Final states.

Q StatesΣ InputΓ Outputδ Transitionλ Output Funcq₀ InitialF Final

# Formal definition of Finite State Transducers
from dataclasses import dataclass
from typing import Dict, Set, Tuple

@dataclass
class FST:
    """
    Finite State Transducer: M = (Q, Σ, Γ, δ, λ, q₀, F)
    
    Q:  Finite set of states
    Σ:  Input alphabet
    Γ:  Output alphabet
    δ:  Q × Σ → Q           (transition function)
    λ:  Q × Σ → Γ*          (output function, string output)
    q₀: Initial state
    F:  Set of final states
    """
    Q: Set[str]
    Sigma: Set[str]
    Gamma: Set[str]
    delta: Dict[Tuple[str, str], str]
    lam: Dict[Tuple[str, str], str]
    q0: str
    F: Set[str]
    
    def __post_init__(self):
        assert self.q0 in self.Q, "Initial state must be in Q"
        assert self.F.issubset(self.Q), "F must be subset of 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})"
            for ch in output:
                assert ch in self.Gamma, f"Output symbol {ch} not in Γ"
    
    def transduce(self, input_string: str) -> Tuple[str, bool]:
        """Transduce input string. Returns (output, accepted)."""
        state = self.q0
        outputs = []
        for symbol in input_string:
            if (state, symbol) not in self.delta:
                return ''.join(outputs), False
            output = self.lam[(state, symbol)]
            state = self.delta[(state, symbol)]
            outputs.append(output)
        return ''.join(outputs), state in self.F
    
    def trace(self, input_string: str):
        """Print detailed trace."""
        state = self.q0
        print(f"Initial state: {state}")
        for symbol in input_string:
            if (state, symbol) in self.delta:
                output = self.lam[(state, symbol)]
                next_state = self.delta[(state, symbol)]
                print(f"  {state} --{symbol}/{output}--> {next_state}")
                state = next_state
            else:
                print(f"  {state} --{symbol}/?--> NO TRANSITION")
                return
        print(f"Final state: {state} {'✓' if state in self.F else '✗'}")


# EXAMPLE: Simple English Pluralizer FST
print("=== Formal Example: Pluralizer FST ===")
print("""
FST that adds 's' to the end of a word.

Q  = {q0, q1}
Σ  = {a-z}
Γ  = {a-z, s}
q₀ = q0
F  = {q1}

Transitions:
  (q0, letter) → (q0, letter)  for all letters
  (q0, '#')    → (q1, 's')     # '#' marks end of word
""")

# Build the FST (simplified with end marker)
alphabet = set('abcdefghijklmnopqrstuvwxyz')
gamma = alphabet | {'s'}

delta = {}
lam = {}

for ch in alphabet:
    delta[('q0', ch)] = 'q0'
    lam[('q0', ch)] = ch

delta[('q0', '#')] = 'q1'
lam[('q0', '#')] = 's'

plural_fst = FST(
    Q={'q0', 'q1'},
    Sigma=alphabet | {'#'},
    Gamma=gamma,
    delta=delta,
    lam=lam,
    q0='q0',
    F={'q1'}
)

# Test
print("\nTransducing 'cat#':")
output, accepted = plural_fst.transduce('cat#')
print(f"Output: {output}")
print(f"Accepted: {accepted}")

print("\nTrace:")
plural_fst.trace('cat#')

# MORE EXAMPLES
print("\n=== More Transduction Examples ===")
words = ['cat', 'dog', 'bus', 'house']
print("\nPluralization:")
for w in words:
    output, _ = plural_fst.transduce(w + '#')
    print(f"  {w} → {output}")

# FORMAL PROPERTIES
print("""
=== Formal Properties ===

1. TRANSDUCTION RELATION
   R(M) = {(x, y) | x ∈ Σ*, y ∈ Γ*, q₀ --x/y--> qf ∈ F}
   
   The set of all input-output pairs.

2. DETERMINISTIC FST
   - One transition per (state, input)
   - One output per (state, input)
   - Denoted DFST

3. NON-DETERMINISTIC FST
   - Multiple transitions possible
   - Multiple outputs possible
   - Denoted NFST

4. FUNCTIONAL FST
   - Each input maps to at most one output
   - Deterministic FSTs are functional

5. RELATIONAL FST
   - Input may map to multiple outputs
   - Non-deterministic

6. COMPOSITION
   (M1 ∘ M2)(x) = M2(M1(x))
   
   Chain transducers.

7. INVERSION
   M⁻¹(y) = x where M(x) = y
   
   Swap input and output.
""")

🔧 Components

🎯 The Building Blocks

An FST has seven components: states, input alphabet, output alphabet, transition function, output function, initial state, and final states. Understanding each is key to designing transducers.

Component Details

States: Memory of the machine. Input Σ: Symbols read. Output Γ: Symbols produced. δ: State transitions. λ: Output strings. q₀: Start state. F: Accept states.

🔲 States📥 Input Σ📤 Output Γ🔄 δ📝 λ▶️ q₀✅ F

# Components of Finite State Transducers
print("=== 1. STATES (Q) ===")
print("""
Finite set of configurations:
  - Encode memory of the transducer
  - Track progress through input

Example: Pluralizer
  q0: reading the word
  q1: done, output 's'

Example: Number to words
  q0: ready for next digit
  q1: processing digit
""")

print("\n=== 2. INPUT ALPHABET (Σ) ===")
print("""
Symbols the transducer reads:

Examples:
  English letters: {a-z, A-Z}
  Digits: {0-9}
  Phonemes: {AE, AH, B, D, ...}
  Morphological tags: {N, V, ADJ, PL, PAST, ...}
  Characters: all Unicode
""")

print("\n=== 3. OUTPUT ALPHABET (Γ) ===")
print("""
Symbols the transducer produces:

Examples:
  English letters: {a-z}
  Phonemes: {AE, AH, B, D, ...}
  Words: {cat, dog, ...}
  Numbers: {one, two, ...}

Note: Output can be empty string (ε).
""")

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

For each (state, input):
  - Exactly one next state (deterministic)
  - Or multiple (non-deterministic)

Example:
  δ(q0, 'c') = q0
  δ(q0, 'a') = q0
  δ(q0, 't') = q0
  δ(q0, '#') = q1
""")

print("\n=== 5. OUTPUT FUNCTION (λ) ===")
print("""
λ: Q × Σ → Γ*

For each (state, input):
  - Output string (possibly empty)

Example:
  λ(q0, 'c') = 'c'
  λ(q0, 'a') = 'a'
  λ(q0, 't') = 't'
  λ(q0, '#') = 's'    # add plural

Key difference from Mealy:
  Mealy: λ: Q × Σ → Γ (single symbol)
  FST:   λ: Q × Σ → Γ* (string)
""")

print("\n=== 6. INITIAL STATE (q₀) ===")
print("""
Where transduction begins:
  - Must be in Q
  - Usually no output at start
""")

print("\n=== 7. FINAL STATES (F) ===")
print("""
States where transduction is successful:
  - F ⊆ Q
  - Can be empty, all states, or subset
  - Input must end in F for valid output

Sometimes called "accepting states".
""")

# COMPONENT IMPLEMENTATION
print("\n=== Implementation: All Components ===")

class FSTComponents:
    """Demonstrate FST components."""
    def __init__(self, Q, Sigma, Gamma, delta, lam, q0, F):
        self.Q = Q
        self.Sigma = Sigma
        self.Gamma = Gamma
        self.delta = delta
        self.lam = lam
        self.q0 = q0
        self.F = F
    
    def describe(self):
        return f"""
FST Components:
  Q (States):       {self.Q}
  Σ (Input):        {self.Sigma}
  Γ (Output):       {self.Gamma}
  q₀ (Initial):     {self.q0}
  F (Final):        {self.F}
  δ (Transitions):  {len(self.delta)} entries
  λ (Outputs):      {len(self.lam)} entries
"""

# Example: Morphological analyzer
print("\n=== Example: English Morphological Analyzer ===")
print("""
Input:  surface form (e.g., "cats")
Output: lemma + tags (e.g., "cat+N+PL")
""")

# Simple morphological analyzer
morph_fst = FSTComponents(
    Q={'q0', 'q_plural', 'q_singular'},
    Sigma=set('abcdefghijklmnopqrstuvwxyz'),
    Gamma=set('abcdefghijklmnopqrstuvwxyz+'),
    delta={
        ('q0', 's'): 'q0',  # simplified
    },
    lam={
        ('q0', 's'): 's',
    },
    q0='q0',
    F={'q_singular', 'q_plural'}
)

print(morph_fst.describe())

# VISUALIZATION
print("\n=== Visual Representation ===")
print("""
FST for pluralization:

         letter/letter
    ┌───────────────────┐
    │                   ↓
  →(q0) ──────────────→ (q0)
    │
    │ #/s
    ↓
  ((q1))

Legend:
  →     : initial state
  (q)   : state
  ((q)) : final state
  a/b   : input a, output b
  #     : end of word marker
""")

# DESIGN PATTERNS
print("\n=== Common Design Patterns ===")
print("""
1. APPEND PATTERN
   - Read input, output same
   - At end, output additional string
   - Example: pluralizer

2. TRANSLATE PATTERN
   - Each input symbol maps to output
   - Example: digit to word

3. CONTEXT-SENSITIVE PATTERN
   - Output depends on context
   - Use states to remember context
   - Example: English spelling rules

4. DELETION PATTERN
   - Output empty for some inputs
   - Example: remove vowels

5. INSERTION PATTERN
   - Output extra symbols
   - Example: add accents

6. CHUNK PATTERN
   - Group input symbols
   - Output multi-symbol units
   - Example: phoneme to grapheme
""")

🔄 Transduction

🎯 Input → Output

Transduction is the process of transforming an input string into an output string using an FST. The transducer reads input symbols one at a time, transitioning between states and producing output along the way.

Transduction Process

1. Start: Begin at q₀. 2. Read: Process input symbols. 3. Output: Produce strings. 4. Transition: Move to next state. 5. End: Check final state. 6. Result: Concatenated outputs.

▶️ Start📖 Read📤 Output✅ End

# Transduction in detail
class Transducer:
    """
    FST with detailed transduction.
    """
    def __init__(self, Q, Sigma, Gamma, delta, lam, q0, F):
        self.Q = Q
        self.Sigma = Sigma
        self.Gamma = Gamma
        self.delta = delta
        self.lam = lam
        self.q0 = q0
        self.F = F
    
    def transduce(self, input_string):
        """Transduce input. Returns (output, accepted)."""
        state = self.q0
        output_parts = []
        
        for symbol in input_string:
            if (state, symbol) not in self.delta:
                return ''.join(output_parts), False
            output_parts.append(self.lam[(state, symbol)])
            state = self.delta[(state, symbol)]
        
        return ''.join(output_parts), state in self.F
    
    def transduce_with_steps(self, input_string):
        """Transduce with detailed step information."""
        state = self.q0
        output_parts = []
        steps = []
        
        for symbol in input_string:
            if (state, symbol) not in self.delta:
                steps.append({
                    'state': state,
                    'input': symbol,
                    'output': None,
                    'next_state': None,
                    'error': 'no transition'
                })
                break
            
            output = self.lam[(state, symbol)]
            next_state = self.delta[(state, symbol)]
            
            steps.append({
                'state': state,
                'input': symbol,
                'output': output,
                'next_state': next_state,
                'error': None
            })
            
            output_parts.append(output)
            state = next_state
        
        return ''.join(output_parts), state in self.F, steps


# EXAMPLE: Translation FST
print("=== Example: Pig Latin Translator ===")
print("""
Pig Latin rules (simplified):
  - If word starts with consonant, move consonant to end + 'ay'
  - If word starts with vowel, add 'way' at end
  
Examples:
  cat → atcay
  dog → ogday
  apple → appleway
  orange → orangeway
""")

# Simplified Pig Latin FST (for words starting with consonants)
# States: q0 (reading consonant), q1 (rest of word), q2 (done)
pig_latin = Transducer(
    Q={'q0', 'q1', 'q2'},
    Sigma=set('abcdefghijklmnopqrstuvwxyz') | {'#'},
    Gamma=set('abcdefghijklmnopqrstuvwxyz') | {'a', 'y', 'w'},
    delta={
        # q0: reading first consonant
        ('q0', 'c'): 'q1', ('q0', 'd'): 'q1', ('q0', 'g'): 'q1',
        ('q0', 'a'): 'q1', ('q0', 'e'): 'q1',  # vowels go directly
        # q1: reading rest of word
        ('q1', 'a'): 'q1', ('q1', 't'): 'q1', ('q1', 'o'): 'q1',
        ('q1', 'g'): 'q1', ('q1', 'p'): 'q1', ('q1', 'l'): 'q1',
        ('q1', 'r'): 'q1', ('q1', 'n'): 'q1', ('q1', 'e'): 'q1',
        # end marker
        ('q1', '#'): 'q2',
    },
    lam={
        # q0: skip first consonant (save for later)
        ('q0', 'c'): '', ('q0', 'd'): '', ('q0', 'g'): '',
        ('q0', 'a'): 'a', ('q0', 'e'): 'e',
        # q1: output rest
        ('q1', 'a'): 'a', ('q1', 't'): 't', ('q1', 'o'): 'o',
        ('q1', 'g'): 'g', ('q1', 'p'): 'p', ('q1', 'l'): 'l',
        ('q1', 'r'): 'r', ('q1', 'n'): 'n', ('q1', 'e'): 'e',
        # end: add consonant + 'ay' (simplified)
        ('q1', '#'): 'cay',
    },
    q0='q0',
    F={'q2'}
)

# Test with 'cat#'
print("\nTransducing 'cat#':")
output, accepted, steps = pig_latin.transduce_with_steps('cat#')
print(f"Output: {output}")
print(f"Accepted: {accepted}")
print("\nSteps:")
for step in steps:
    if step['error']:
        print(f"  {step['state']} --{step['input']}--> ERROR")
    else:
        print(f"  {step['state']} --{step['input']}/{step['output']}--> {step['next_state']}")

# TRANSDUCTION TYPES
print("\n=== Types of Transduction ===")
print("""
1. ONE-TO-ONE
   Each input maps to exactly one output.
   Example: digit → word

2. ONE-TO-MANY
   One input maps to multiple outputs.
   Example: number → multiple words
   42 → "forty two"

3. MANY-TO-ONE
   Multiple inputs map to same output.
   Example: different forms → same lemma
   cats, cat → cat

4. MANY-TO-MANY
   Complex transformations.
   Example: translation

5. IDENTITY
   Output = Input.
   Example: copy machine

6. DELETION
   Output shorter than input.
   Example: remove vowels

7. INSERTION
   Output longer than input.
   Example: add suffix

8. SUBSTITUTION
   Replace symbols.
   Example: a→b, b→c
""")

# TRANSDUCTION RELATION
print("\n=== Transduction Relation ===")
print("""
The relation R(M) for an FST M is:
  R(M) = {(x, y) | x ∈ Σ*, y ∈ Γ*, x --M--> y and ends in F}

Properties:
  - R(M) is a rational relation
  - Can be infinite
  - Composition of FSTs = composition of relations

Example: Pluralizer
  R = {(cat, cats), (dog, dogs), (bus, buses), ...}

This is a functional relation:
  Each input maps to at most one output.
""")

# FUNCTIONAL VS RELATIONAL
print("\n=== Functional vs Relational FSTs ===")
print("""
FUNCTIONAL FST:
  - Each input has at most one output
  - Deterministic
  - Can be inverted (if bijective)
  
  Example: digit → word

RELATIONAL FST:
  - Input may have multiple outputs
  - Non-deterministic
  - Cannot always invert
  
  Example: word → multiple pronunciations
  
  "read" → "reed" (present)
  "read" → "red" (past)

Both are useful in NLP.
""")

📊 Types of FSTs

🎯 Varieties of Transducers

FSTs come in many varieties: deterministic vs non-deterministic, functional vs relational, weighted vs unweighted, and more. Each type has different properties and applications.

FST Types

DFST: Deterministic FST. NFST: Non-deterministic FST. Functional: One output per input. Relational: Multiple outputs. Weighted: With probabilities. Subsequential: With final outputs.

🎯 DFST🔀 NFST📊 Weighted🔗 Subsequential

# Types of Finite State Transducers
print("=== 1. Deterministic FST (DFST) ===")
print("""
Definition:
  - One transition per (state, input)
  - One output per (state, input)
  - No ε-transitions

Properties:
  - Functional (one output per input)
  - Efficient to simulate: O(n)
  - Easy to implement

Example:
  (q0, a) → (q1, 'x')
  (q0, b) → (q2, 'y')
  
  No ambiguity.
""")

print("\n=== 2. Non-Deterministic FST (NFST) ===")
print("""
Definition:
  - Multiple transitions per (state, input)
  - Multiple outputs possible
  - May have ε-transitions

Properties:
  - Relational (multiple outputs)
  - More expressive
  - Simulation requires backtracking or subset construction

Example:
  (q0, a) → (q1, 'x')
  (q0, a) → (q2, 'y')   # multiple choices!
""")

print("\n=== 3. Functional FST ===")
print("""
Definition:
  - Each input string maps to at most one output
  - May be non-deterministic internally

Properties:
  - Output is unique
  - Can be determinized
  - Useful for translation

Example:
  Pluralizer (cat → cats)
  Each input has one output.
""")

print("\n=== 4. Relational FST ===")
print("""
Definition:
  - Input may map to multiple outputs
  - General case

Properties:
  - Captures ambiguity
  - Useful for analysis

Example: Morphological analyzer
  "reads" → read+V+3SG
  "reads" → read+N+PL
  (two possible analyses)
""")

print("\n=== 5. Weighted FST (WFST) ===")
print("""
Definition:
  - Transitions have weights (costs/probabilities)
  - Output includes total weight

Properties:
  - Probabilistic transduction
  - Used in speech recognition
  - Can find best path (shortest path)

Example:
  "read" → "reed" (weight 0.7)
  "read" → "red"  (weight 0.3)
  
  Most likely: "reed"
""")

print("\n=== 6. Subsequential FST ===")
print("""
Definition:
  - Deterministic FST
  - Allows final output on final states
  - More expressive than pure DFST

Properties:
  - Functional
  - Can output suffix at end
  - Useful for morphology

Example: Pluralizer
  Read "cat", output "cat"
  At final state, output "s"
  Total: "cats"
""")

print("\n=== 7. Sequential FST ===")
print("""
Definition:
  - Deterministic
  - Output only during transitions
  - No final output

Properties:
  - Strictly functional
  - Subset of subsequential
  - Simpler to implement
""")

# COMPARISON TABLE
print("\n=== Comparison Table ===")
print(f"{'Type':<25} {'Deterministic':<15} {'Functional':<15} {'Weights':<10}")
print("-" * 70)
print(f"{'DFST':<25} {'Yes':<15} {'Yes':<15} {'No':<10}")
print(f"{'NFST':<25} {'No':<15} {'No':<15} {'No':<10}")
print(f"{'Functional FST':<25} {'Maybe':<15} {'Yes':<15} {'No':<10}")
print(f"{'Relational FST':<25} {'No':<15} {'No':<15} {'No':<10}")
print(f"{'WFST':<25} {'Maybe':<15} {'Maybe':<15} {'Yes':<10}")
print(f"{'Subsequential':<25} {'Yes':<15} {'Yes':<15} {'No':<10}")
print(f"{'Sequential':<25} {'Yes':<15} {'Yes':<15} {'No':<10}")

# IMPLEMENTATION
print("\n=== Implementation: Weighted FST ===")

class WeightedFST:
    """
    Weighted FST: transitions have weights.
    """
    def __init__(self, Q, Sigma, Gamma, delta, q0, F):
        self.Q = Q
        self.Sigma = Sigma
        self.Gamma = Gamma
        self.delta = delta  # (state, input) -> list of (next_state, output, weight)
        self.q0 = q0
        self.F = F
    
    def transduce(self, input_string):
        """Find best (lowest weight) transduction."""
        # BFS with weights
        from heapq import heappush, heappop
        
        # Priority queue: (weight, state, position, output)
        heap = [(0, self.q0, 0, '')]
        visited = {}
        
        while heap:
            weight, state, pos, output = heappop(heap)
            
            key = (state, pos)
            if key in visited and visited[key] <= weight:
                continue
            visited[key] = weight
            
            if pos == len(input_string):
                if state in self.F:
                    return output, weight
                continue
            
            symbol = input_string[pos]
            if (state, symbol) not in self.delta:
                continue
            
            for next_state, out, w in self.delta[(state, symbol)]:
                new_weight = weight + w
                new_output = output + out
                heappush(heap, (new_weight, next_state, pos + 1, new_output))
        
        return None, float('inf')


# Example: Pronunciation FST
print("\n=== Example: Pronunciation FST ===")
print("""
Word "read" can be pronounced two ways:
  "reed" (present tense)
  "red" (past tense)

Weighted FST:
  (q0, 'r') → (q1, 'r', 0)
  (q1, 'e') → (q2, 'ee', 0.3)  # present
  (q1, 'e') → (q3, 'e', 0.7)   # past
  (q2, 'a') → (q4, '', 0)
  (q3, 'a') → (q4, '', 0)
  (q4, 'd') → (q5, 'd', 0)
  
  q5 ∈ F
""")

wfst = WeightedFST(
    Q={'q0', 'q1', 'q2', 'q3', 'q4', 'q5'},
    Sigma=set('read'),
    Gamma=set('red'),
    delta={
        ('q0', 'r'): [('q1', 'r', 0)],
        ('q1', 'e'): [('q2', 'ee', 0.3), ('q3', 'e', 0.7)],
        ('q2', 'a'): [('q4', '', 0)],
        ('q3', 'a'): [('q4', '', 0)],
        ('q4', 'd'): [('q5', 'd', 0)],
    },
    q0='q0',
    F={'q5'}
)

output, weight = wfst.transduce('read')
print(f"\nBest pronunciation: {output} (weight: {weight})")

# APPLICATIONS
print("\n=== Applications by Type ===")
print("""
DFST:
  - Simple transliteration
  - Character encoding conversion

NFST:
  - Morphological analysis
  - Parsing

Functional FST:
  - Text normalization
  - Number formatting

Relational FST:
  - Machine translation
  - Speech recognition

Weighted FST:
  - Speech recognition (ASR)
  - Statistical machine translation
  - OCR post-processing

Subsequential FST:
  - Morphological generation
  - Inflection

Sequential FST:
  - Simple rewriting
  - Tokenization
""")

➕ Operations

🎯 Combining FSTs

FSTs can be combined through composition, union, intersection, and other operations. Composition is the most important — it chains transducers so output of one becomes input to another.

FST Operations

Composition: Chain FSTs. Union: Either FST. Intersection: Both FSTs. Inversion: Swap input/output. Projection: Input or output only. Closure: Star, plus.

🔗 Composition➕ Union∩ Intersection🔄 Inversion

# Operations on Finite State Transducers
print("=== 1. COMPOSITION ===")
print("""
Composition: M1 ∘ M2

Definition:
  (M1 ∘ M2)(x) = M2(M1(x))
  
  Output of M1 becomes input to M2.

Requirements:
  - Output alphabet of M1 = Input alphabet of M2
  - Both must be functional for deterministic composition

Example:
  M1: lowercase → uppercase
  M2: uppercase → leetspeak
  
  (M1 ∘ M2)("hello") = M2(M1("hello")) = M2("HELLO") = "H3LL0"
""")

class ComposedFST:
    """Compose two FSTs: M1 then M2."""
    def __init__(self, m1, m2):
        self.m1 = m1
        self.m2 = m2
    
    def transduce(self, input_string):
        """Apply M1 then M2."""
        intermediate, accepted1 = self.m1.transduce(input_string)
        if not accepted1:
            return None, False
        output, accepted2 = self.m2.transduce(intermediate)
        return output, accepted2


# Example: Compose lowercase→uppercase and uppercase→leetspeak
print("\n=== Example: Composition ===")

# M1: lowercase to uppercase
lower_to_upper = FST(
    Q={'q0', 'q1'},
    Sigma=set('abcdefghijklmnopqrstuvwxyz'),
    Gamma=set('ABCDEFGHIJKLMNOPQRSTUVWXYZ'),
    delta={('q0', c): 'q1' for c in 'abcdefghijklmnopqrstuvwxyz'},
    lam={('q0', c): c.upper() for c in 'abcdefghijklmnopqrstuvwxyz'},
    q0='q0',
    F={'q1'}
)

# M2: uppercase to leetspeak
upper_to_leet = FST(
    Q={'q0', 'q1'},
    Sigma=set('ABCDEFGHIJKLMNOPQRSTUVWXYZ'),
    Gamma=set('ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'),
    delta={('q0', c): 'q1' for c in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'},
    lam={('q0', c): {'E': '3', 'L': '1', 'O': '0', 'T': '7'}.get(c, c) 
         for c in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'},
    q0='q0',
    F={'q1'}
)

composed = ComposedFST(lower_to_upper, upper_to_leet)
word = 'hello'
output, accepted = composed.transduce(word)
print(f"Input: {word}")
print(f"Step 1 (lower→upper): {lower_to_upper.transduce(word)[0]}")
print(f"Step 2 (upper→leet):  {output}")
print(f"Final: {output}")

print("\n=== 2. UNION ===")
print("""
Union: M1 ∪ M2

Definition:
  (M1 ∪ M2)(x) = M1(x) OR M2(x)
  
  Output from either FST.

Construction:
  - New start state with ε-transitions to M1 and M2
  - Accept if either accepts

Example:
  M1: English pluralizer
  M2: French pluralizer
  M1 ∪ M2: pluralize in either language
""")

print("\n=== 3. INTERSECTION ===")
print("""
Intersection: M1 ∩ M2

Definition:
  (M1 ∩ M2)(x) = M1(x) AND M2(x)
  
  Output must come from both.

Construction:
  - Product construction
  - Pair states (q1, q2)
  - Accept if both accept

Note: Intersection is more complex for transducers.
      Requires synchronization of outputs.
""")

print("\n=== 4. INVERSION ===")
print("""
Inversion: M⁻¹

Definition:
  M⁻¹(y) = x where M(x) = y
  
  Swap input and output.

Construction:
  - Swap Σ and Γ
  - Swap δ and λ roles
  - Reverse transitions

Example:
  M: word → pronunciation
  M⁻¹: pronunciation → word

Note: Not all FSTs are invertible.
      Only functional, bijective FSTs.
""")

print("\n=== 5. PROJECTION ===")
print("""
Input projection: π₁(M)
  - The set of all possible inputs
  - Ignores output

Output projection: π₂(M)
  - The set of all possible outputs
  - Ignores input

Example:
  M: pluralizer
  π₁(M) = all English words
  π₂(M) = all plural English words
""")

print("\n=== 6. CLOSURE ===")
print("""
Kleene Star: M*
  - Zero or more applications of M
  - M* = ε ∪ M ∪ M² ∪ M³ ∪ ...

Kleene Plus: M+
  - One or more applications
  - M+ = M ∪ M² ∪ M³ ∪ ...

Example:
  M: add 's'
  M*: add zero or more 's'
  M+: add one or more 's'
""")

# OPERATIONS IMPLEMENTATION
print("\n=== Implementation: Operations ===")

def invert_fst(fst):
    """Invert an FST (swap input/output)."""
    new_delta = {}
    new_lam = {}
    
    for (state, inp), next_state in fst.delta.items():
        output = fst.lam[(state, inp)]
        # For inversion, we need to reverse the transduction
        # This is complex; simplified here
        pass
    
    return "Inversion requires more complex construction"

def union_fst(m1, m2):
    """Union of two FSTs (simplified)."""
    pass

def compose_fst(m1, m2):
    """Compose two FSTs (conceptual)."""
    return ComposedFST(m1, m2)

# PRACTICAL EXAMPLE: MORPHOLOGICAL ANALYSIS + GENERATION
print("\n=== Practical Example: Analysis + Generation ===")
print("""
Analysis FST: surface form → lemma + tags
Generation FST: lemma + tags → surface form

Composition: Analysis ∘ Generation = Identity
  (for correctly analyzed forms)

This is used in:
  - Spell checkers
  - Machine translation
  - Grammar checking
""")

# SUMMARY
print("\n=== Operations Summary ===")
print(f"{'Operation':<20} {'Notation':<15} {'Purpose':<30}")
print("-" * 70)
print(f"{'Composition':<20} {'M1 ∘ M2':<15} {'Chain transducers':<30}")
print(f"{'Union':<20} {'M1 ∪ M2':<15} {'Either transducer':<30}")
print(f"{'Intersection':<20} {'M1 ∩ M2':<15} {'Both transducers':<30}")
print(f"{'Inversion':<20} {'M⁻¹':<15} {'Swap input/output':<30}")
print(f"{'Projection':<20} {'π₁(M)':<15} {'Input set':<30}")
print(f"{'Star':<20} {'M*':<15} {'Zero or more':<30}")
print(f"{'Plus':<20} {'M+':<15} {'One or more':<30}")

🎯 Determinization

🎯 From Non-Deterministic to Deterministic

Determinization converts a non-deterministic FST (NFST) into an equivalent deterministic FST (DFST). This is similar to subset construction for NFAs, but more complex due to outputs.

Determinization

Goal: One transition per input. Method: Subset construction. Challenge: Output delays. Result: DFST or subsequential. Not always possible: Some NFSTs can't be determinized. Complexity: Exponential.

🎯 Deterministic📊 Subset⏳ Output Delay⚠️ Not Always

# Determinization of Finite State Transducers
print("=== Why Determinize? ===")
print("""
Non-deterministic FST:
  - Multiple transitions per (state, input)
  - Multiple outputs possible
  - Simulation requires backtracking

Deterministic FST:
  - One transition per (state, input)
  - One output per (state, input)
  - Simulation is O(n)

Determinization makes simulation efficient.
""")

print("\n=== The Challenge ===")
print("""
For NFAs: subset construction works directly.

For NFSTs: outputs complicate things.

Problem:
  Different paths may produce outputs at different times.
  
Example:
  Path 1: outputs "a" immediately
  Path 2: outputs "b" after 2 more steps
  
  When to output? Need to delay.

Solution:
  - Subsequential FST: allow final output
  - P-subsequential: allow multiple final outputs
  - General: may require infinite states
""")

print("\n=== Subset Construction for FSTs ===")
print("""
Algorithm (simplified):

1. States of DFST are sets of NFST states
2. Track pending output (output to be emitted)
3. For each input:
   - Compute all possible next states
   - Compute common prefix of outputs
   - Emit common prefix, delay rest
4. Final states: those containing an NFST final state
5. Final output: remaining pending output

Key: Output may be delayed until enough information.
""")

# IMPLEMENTATION
class NFST:
    """Non-deterministic FST."""
    def __init__(self, Q, Sigma, Gamma, delta, q0, F):
        self.Q = Q
        self.Sigma = Sigma
        self.Gamma = Gamma
        # delta: (state, input) -> list of (next_state, output)
        self.delta = delta
        self.q0 = q0
        self.F = F
    
    def transduce(self, input_string):
        """Non-deterministic transduction: return all possible outputs."""
        results = []
        
        def explore(state, pos, output):
            if pos == len(input_string):
                if state in self.F:
                    results.append(output)
                return
            
            symbol = input_string[pos]
            if (state, symbol) not in self.delta:
                return
            
            for next_state, out in self.delta[(state, symbol)]:
                explore(next_state, pos + 1, output + out)
        
        explore(self.q0, 0, '')
        return results


class DFST:
    """Deterministic FST (with output on transitions)."""
    def __init__(self, Q, Sigma, Gamma, delta, lam, q0, F, final_output=None):
        self.Q = Q
        self.Sigma = Sigma
        self.Gamma = Gamma
        self.delta = delta
        self.lam = lam
        self.q0 = q0
        self.F = F
        self.final_output = final_output or {}  # state -> final output
    
    def transduce(self, input_string):
        state = self.q0
        outputs = []
        
        for symbol in input_string:
            if (state, symbol) not in self.delta:
                return None, False
            outputs.append(self.lam[(state, symbol)])
            state = self.delta[(state, symbol)]
        
        # Add final output if in final state
        if state in self.F:
            outputs.append(self.final_output.get(state, ''))
            return ''.join(outputs), True
        return ''.join(outputs), False


# EXAMPLE: Non-deterministic FST that needs determinization
print("\n=== Example: NFST to DFST ===")
print("""
NFST: reads a's and b's, outputs 'x' for each a, 'y' for each b.
      Non-deterministic: at end, may output 'z' or not.

Actually, let's make a simpler example:

NFST:
  q0 --a/x--> q1
  q0 --a/x--> q2   (non-deterministic choice)
  q1 --b/y--> q3
  q2 --b/y--> q3
  q3 is final

Both paths produce same output: "xy"
So determinization is possible.
""")

nfst = NFST(
    Q={'q0', 'q1', 'q2', 'q3'},
    Sigma={'a', 'b'},
    Gamma={'x', 'y'},
    delta={
        ('q0', 'a'): [('q1', 'x'), ('q2', 'x')],
        ('q1', 'b'): [('q3', 'y')],
        ('q2', 'b'): [('q3', 'y')],
    },
    q0='q0',
    F={'q3'}
)

print("\nNFST outputs for 'ab':")
outputs = nfst.transduce('ab')
print(f"  All outputs: {outputs}")

# Determinize (simplified)
print("\n=== Determinized Version ===")
print("""
Since both paths give same output, we can merge q1 and q2:

DFST:
  q0 --a/x--> q12
  q12 --b/y--> q3
  q3 final

States: {q0, q12, q3}
""")

dfst = DFST(
    Q={'q0', 'q12', 'q3'},
    Sigma={'a', 'b'},
    Gamma={'x', 'y'},
    delta={
        ('q0', 'a'): 'q12',
        ('q12', 'b'): 'q3',
    },
    lam={
        ('q0', 'a'): 'x',
        ('q12', 'b'): 'y',
    },
    q0='q0',
    F={'q3'}
)

output, accepted = dfst.transduce('ab')
print(f"DFST output: {output} (accepted: {accepted})")

# SUBSEQUENTIAL FST
print("\n=== Subsequential FST ===")
print("""
A subsequential FST is a DFST that allows:
  - Final output on final states
  - This makes it more expressive

Example: Pluralizer
  Read "cat", output "cat"
  At final state, output "s"
  Total: "cats"

The 's' is the final output.
""")

pluralizer_subseq = DFST(
    Q={'q0', 'q1'},
    Sigma=set('abcdefghijklmnopqrstuvwxyz'),
    Gamma=set('abcdefghijklmnopqrstuvwxyz') | {'s'},
    delta={('q0', c): 'q1' for c in 'abcdefghijklmnopqrstuvwxyz'},
    lam={('q0', c): c for c in 'abcdefghijklmnopqrstuvwxyz'},
    q0='q0',
    F={'q1'},
    final_output={'q1': 's'}
)

output, accepted = pluralizer_subseq.transduce('cat')
print(f"Input: cat")
print(f"Output: {output}")
print(f"Accepted: {accepted}")

# P-SUBSEQUENTIAL
print("\n=== P-Subsequential FST ===")
print("""
P-subsequential: allows multiple final outputs.

Example: Morphological analyzer
  "cats" → cat+N+PL
  "cats" → cat+V+3SG  (if "cat" is also a verb)
  
  Two possible analyses at final state.
""")

# LIMITATIONS
print("\n=== Limitations of Determinization ===")
print("""
Not all NFSTs can be determinized!

Reasons:
  1. Output may depend on future input
  2. Ambiguous outputs that can't be delayed
  3. Infinite delay required

Example where determinization fails:
  NFST: reads a's and b's
        outputs 'x' if string has even length
        outputs 'y' if string has odd length
        (output at end, depends on total length)
        
  This requires knowing the full string length.
  Can't be done with finite states deterministically.

In practice:
  - Many useful NFSTs are determinizable
  - Subsequential covers most cases
  - Tools handle determinization automatically
""")

# COMPLEXITY
print("\n=== Complexity ===")
print(f"{'Operation':<25} {'Complexity':<20} {'Notes':<30}")
print("-" * 75)
print(f"{'NFST simulation':<25} {'O(2^n)':<20} {'Exponential paths':<30}")
print(f"{'DFST simulation':<25} {'O(n)':<20} {'Linear':<30}")
print(f"{'Determinization':<25} {'O(2^n)':<20} {'Exponential blowup':<30}")
print(f"{'Minimization':<25} {'O(n log n)':<20} {'After determinization':<30}")

📉 Minimization

🎯 Finding the Smallest FST

FST minimization reduces the number of states in a deterministic FST without changing its transduction behavior. This is analogous to DFA minimization.

Minimization

Goal: Fewest states. Method: Partition refinement. Equivalence: Same transduction. Requirement: Deterministic. Result: Minimal DFST. Uniqueness: Unique up to isomorphism.

🔍 Equivalence📊 Partition🔗 Merge📉 Minimal

# Minimization of Finite State Transducers
from collections import defaultdict

print("=== State Equivalence for FSTs ===")
print("""
Two states q1, q2 in a DFST are equivalent if:
  - For all inputs, they produce the same output
  - They transition to equivalent states

Formally: q1 ~ q2 iff for all x ∈ Σ*:
  λ*(q1, x) = λ*(q2, x)  (same output)
  and δ*(q1, x) ~ δ*(q2, x)  (transitions to equivalent states)
""")

# MINIMIZATION ALGORITHM
def minimize_fst(fst):
    """
    Minimize a deterministic FST using partition refinement.
    """
    # Initial partition: group by final/non-final
    final = set(fst.F)
    non_final = fst.Q - final
    
    partitions = []
    if final:
        partitions.append(final)
    if non_final:
        partitions.append(non_final)
    
    changed = True
    while changed:
        changed = False
        new_partitions = []
        
        for group in partitions:
            split = split_fst_group(group, partitions, fst)
            new_partitions.extend(split)
            if len(split) > 1:
                changed = True
        
        partitions = new_partitions
    
    return build_minimized_fst(fst, partitions)


def split_fst_group(group, partitions, fst):
    """Split a group based on FST 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(fst.Sigma):
            if (state, s) in fst.delta:
                out = fst.lam[(state, s)]
                target = fst.delta[(state, s)]
                sig.append((out, part_index[target]))
            else:
                sig.append((None, None))
        signatures[tuple(sig)].append(state)
    
    return [set(states) for states in signatures.values()]


def build_minimized_fst(fst, partitions):
    """Build minimized FST 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[fst.q0]
    new_F = {state_to_part[s] for s in fst.F}
    
    new_delta = {}
    new_lam = {}
    
    for state in fst.Q:
        for s in fst.Sigma:
            if (state, s) in fst.delta:
                next_state = fst.delta[(state, s)]
                output = fst.lam[(state, s)]
                new_delta[(state_to_part[state], s)] = state_to_part[next_state]
                new_lam[(state_to_part[state], s)] = output
    
    return FST(
        Q=new_Q,
        Sigma=fst.Sigma,
        Gamma=fst.Gamma,
        delta=new_delta,
        lam=new_lam,
        q0=new_q0,
        F=new_F
    )


# EXAMPLE: Non-minimal FST
print("\n=== Example: Minimize FST ===")
print("""
Original FST with redundant states:

States: {q0, q1, q2, q3}
  q0: start
  q1: reads 'a', outputs 'x'
  q2: reads 'a', outputs 'x'  (same as q1)
  q3: final

Transitions:
  q0 --a/x--> q1
  q0 --a/x--> q2  (redundant)
  q1 --b/y--> q3
  q2 --b/y--> q3
""")

# Create non-minimal FST (deterministic version)
# For simplicity, let's create a FST with redundant states
non_min_fst = FST(
    Q={'q0', 'q1', 'q2', 'q3'},
    Sigma={'a', 'b'},
    Gamma={'x', 'y'},
    delta={
        ('q0', 'a'): 'q1',
        ('q1', 'b'): 'q3',
        ('q2', 'b'): 'q3',  # q2 has same behavior as q1
        ('q3', 'a'): 'q3',
        ('q3', 'b'): 'q3',
    },
    lam={
        ('q0', 'a'): 'x',
        ('q1', 'b'): 'y',
        ('q2', 'b'): 'y',
        ('q3', 'a'): '',
        ('q3', 'b'): '',
    },
    q0='q0',
    F={'q3'}
)

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

# Add q2 transition from q0
non_min_fst.delta[('q0', 'a')] = 'q1'  # keep deterministic

minimized = minimize_fst(non_min_fst)
print(f"Minimized states: {minimized.Q}")

# Test equivalence
def test_fst_equivalence(fst1, fst2, max_length=5):
    """Test if two FSTs are equivalent."""
    from itertools import product
    
    for length in range(max_length + 1):
        for symbols in product(fst1.Sigma, repeat=length):
            word = ''.join(symbols)
            out1, acc1 = fst1.transduce(word)
            out2, acc2 = fst2.transduce(word)
            if out1 != out2 or acc1 != acc2:
                return False, word, (out1, acc1), (out2, acc2)
    return True, None, None, None

equiv, counter, r1, r2 = test_fst_equivalence(non_min_fst, minimized)
if equiv:
    print("✓ FSTs are equivalent")
else:
    print(f"✗ Differ on '{counter}': {r1} vs {r2}")

# WHY MINIMIZE
print("\n=== Why Minimize FSTs? ===")
print("""
1. EFFICIENCY
   - Fewer states → less memory
   - Faster simulation

2. COMPOSITION
   - Smaller FSTs compose better
   - Less state explosion

3. UNDERSTANDING
   - Reveals essential structure
   - Canonical form

4. OPTIMIZATION
   - Foundation for further optimization
   - State encoding

5. VERIFICATION
   - Easy comparison
   - Standard representation

Applications:
  - Speech recognition (large FSTs)
  - Machine translation
  - Morphological analysis
""")

# MINIMIZATION + DETERMINIZATION
print("\n=== Determinization + Minimization Pipeline ===")
print("""
Typical FST processing pipeline:

1. Start with NFST (easier to design)
2. Determinize → DFST
3. Minimize → minimal DFST
4. Compose with other FSTs
5. Optimize further

Tools like OpenFST automate this pipeline.

Complexity:
  - Determinization: O(2^n) worst case
  - Minimization: O(n log n)
  - Composition: O(n*m)
""")

# PRACTICAL EXAMPLE
print("\n=== Practical Example: Morphological Analyzer ===")
print("""
A morphological analyzer for English:

Input:  "cats"
Output: "cat+N+PL"

This can be built as an FST and minimized.

States might represent:
  - Reading the word
  - Detecting suffixes
  - Outputting tags

Minimization reduces redundant states.
""")

🔗 Composition

🎯 Chaining Transducers

Composition chains two FSTs so the output of the first becomes the input of the second. This is the most important operation for building complex NLP pipelines.

Composition

Notation: M1 ∘ M2. Definition: (M1 ∘ M2)(x) = M2(M1(x)). Requirement: Γ1 = Σ2. Construction: Product with ε-filter. Complexity: O(|Q1| × |Q2|). Uses: NLP pipelines.

🔗 Chain🔄 Output→Input📊 Product🚰 Pipeline

# Composition of Finite State Transducers
print("=== What is Composition? ===")
print("""
Composition: M1 ∘ M2

Given:
  M1: Σ* → Γ1*
  M2: Γ1* → Γ2*  (Γ1 = Σ2)

Then:
  M1 ∘ M2: Σ* → Γ2*
  (M1 ∘ M2)(x) = M2(M1(x))

The output of M1 feeds into M2.

Visual:
  Input x → [M1] → Intermediate y → [M2] → Output z
""")

# COMPOSITION IMPLEMENTATION
class ComposedFST:
    """
    Composition of two FSTs: M1 then M2.
    """
    def __init__(self, m1, m2):
        self.m1 = m1
        self.m2 = m2
        self.name = f"({m1.name if hasattr(m1, 'name') else 'M1'} ∘ {m2.name if hasattr(m2, 'name') else 'M2'})"
    
    def transduce(self, input_string):
        """Apply M1 then M2."""
        intermediate, accepted1 = self.m1.transduce(input_string)
        if not accepted1:
            return None, False
        output, accepted2 = self.m2.transduce(intermediate)
        return output, accepted2
    
    def trace(self, input_string):
        """Detailed trace through both FSTs."""
        print(f"Input: {input_string}")
        
        print("\nStep 1: M1")
        intermediate, acc1 = self.m1.transduce(input_string)
        print(f"  Output: {intermediate}")
        print(f"  Accepted: {acc1}")
        
        if not acc1:
            print("  M1 rejected input.")
            return
        
        print("\nStep 2: M2")
        output, acc2 = self.m2.transduce(intermediate)
        print(f"  Output: {output}")
        print(f"  Accepted: {acc2}")
        
        print(f"\nFinal output: {output if acc2 else 'REJECTED'}")


# EXAMPLE 1: Lowercase → Uppercase → Leetspeak
print("\n=== Example 1: Text Transformation Pipeline ===")
print("""
M1: lowercase → uppercase
M2: uppercase → leetspeak
Composition: lowercase → leetspeak
""")

# M1: lowercase to uppercase
lower_to_upper = FST(
    Q={'q0', 'q1'},
    Sigma=set('abcdefghijklmnopqrstuvwxyz'),
    Gamma=set('ABCDEFGHIJKLMNOPQRSTUVWXYZ'),
    delta={('q0', c): 'q1' for c in 'abcdefghijklmnopqrstuvwxyz'},
    lam={('q0', c): c.upper() for c in 'abcdefghijklmnopqrstuvwxyz'},
    q0='q0',
    F={'q1'}
)
lower_to_upper.name = 'lower→upper'

# M2: uppercase to leetspeak
leet_map = {'E': '3', 'L': '1', 'O': '0', 'T': '7', 'A': '4', 'S': '5'}
upper_to_leet = FST(
    Q={'q0', 'q1'},
    Sigma=set('ABCDEFGHIJKLMNOPQRSTUVWXYZ'),
    Gamma=set('ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'),
    delta={('q0', c): 'q1' for c in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'},
    lam={('q0', c): leet_map.get(c, c) for c in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'},
    q0='q0',
    F={'q1'}
)
upper_to_leet.name = 'upper→leet'

# Compose
pipeline = ComposedFST(lower_to_upper, upper_to_leet)

print("\nProcessing 'hello':")
pipeline.trace('hello')

print("\n---")
print("\nProcessing 'test':")
pipeline.trace('test')

# EXAMPLE 2: NLP Pipeline
print("\n=== Example 2: NLP Pipeline ===")
print("""
Typical NLP pipeline using FST composition:

1. Tokenizer: text → tokens
2. Tagger: tokens → tagged tokens
3. Lemmatizer: tagged tokens → lemmas
4. Generator: lemmas → inflected forms

Composition: 1 ∘ 2 ∘ 3 ∘ 4
""")

# Simplified example: word → uppercase → add suffix
print("\n=== Example 3: Word Processing ===")

# M1: identity (copy input)
identity = FST(
    Q={'q0', 'q1'},
    Sigma=set('abcdefghijklmnopqrstuvwxyz'),
    Gamma=set('abcdefghijklmnopqrstuvwxyz'),
    delta={('q0', c): 'q1' for c in 'abcdefghijklmnopqrstuvwxyz'},
    lam={('q0', c): c for c in 'abcdefghijklmnopqrstuvwxyz'},
    q0='q0',
    F={'q1'}
)
identity.name = 'identity'

# M2: append 's'
append_s = FST(
    Q={'q0', 'q1'},
    Sigma=set('abcdefghijklmnopqrstuvwxyz'),
    Gamma=set('abcdefghijklmnopqrstuvwxyz') | {'s'},
    delta={('q0', c): 'q1' for c in 'abcdefghijklmnopqrstuvwxyz'},
    lam={('q0', c): c for c in 'abcdefghijklmnopqrstuvwxyz'},
    q0='q0',
    F={'q1'}
)
# Add final output
append_s.final_output = {'q1': 's'}
# We need to modify the FST class or use a different approach

# For simplicity, let's use a custom function
def append_s_transduce(input_str):
    return input_str + 's'

# Composition
pipeline2 = ComposedFST(identity, append_s)

# Note: Our FST class doesn't have final_output, so this won't work perfectly
# Let's demonstrate with a simple function
print("\nProcessing 'cat' through identity ∘ append_s:")
intermediate, _ = identity.transduce('cat')
print(f"  After identity: {intermediate}")
final = append_s_transduce(intermediate)
print(f"  After append_s: {final}")

# COMPOSITION PROPERTIES
print("\n=== Properties of Composition ===")
print("""
1. ASSOCIATIVITY
   (M1 ∘ M2) ∘ M3 = M1 ∘ (M2 ∘ M3)
   
2. IDENTITY
   M ∘ I = I ∘ M = M
   where I is the identity FST.

3. COMPLEXITY
   |Q1 ∘ Q2| = O(|Q1| × |Q2|)
   
   Product construction.

4. EPSILON FILTERING
   Need to handle ε-transitions carefully.
   Otherwise, composition may be incorrect.

5. FUNCTIONALITY
   If M1 and M2 are functional, M1 ∘ M2 is functional.
   
6. DETERMINISM
   Composition of DFSTs may be NFST.
   Need determinization after composition.
""")

# EPSILON FILTERING
print("\n=== Epsilon Filtering ===")
print("""
Problem:
  M1 may output ε (empty string)
  M2 may read ε-transitions
  
  Without filtering, composition may:
    - Create spurious paths
    - Produce incorrect outputs

Solution:
  1. Represent ε as a special symbol
  2. Filter out invalid ε paths
  3. Standard construction (Mohri, 1996)

In practice:
  - OpenFST handles this automatically
  - Tools implement ε-filter
""")

# OPTIMIZATION
print("\n=== Optimizing Composition ===")
print("""
1. DETERMINIZE FIRST
   - Determinize M1 and M2 before composition
   - Reduces state space

2. MINIMIZE FIRST
   - Minimize M1 and M2
   - Smaller product

3. LAZY COMPOSITION
   - Compute states on demand
   - Don't build full product
   - Used in OpenFST

4. WEIGHTED COMPOSITION
   - Weights multiply during composition
   - Used in speech recognition

5. FILTERED COMPOSITION
   - Apply filters during composition
   - Reduces intermediate size
""")

# PRACTICAL EXAMPLE
print("\n=== Practical Example: Morphological Analysis + Generation ===")
print("""
Analysis FST: surface form → lemma + tags
  "cats" → "cat+N+PL"

Generation FST: lemma + tags → surface form
  "cat+N+PL" → "cats"

Composition: Analysis ∘ Generation
  "cats" → "cat+N+PL" → "cats"
  
  This should be identity for valid forms.

This is used in:
  - Spell checkers
  - Grammar checkers
  - Machine translation
""")

# SUMMARY
print("\n=== Composition Summary ===")
print(f"{'Aspect':<25} {'Description':<40}")
print("-" * 70)
print(f"{'Notation':<25} {'M1 ∘ M2':<40}")
print(f"{'Definition':<25} {'(M1 ∘ M2)(x) = M2(M1(x))':<40}")
print(f"{'State count':<25} {'O(|Q1| × |Q2|)':<40}")
print(f"{'Requirement':<25} {'Γ1 = Σ2':<40}")
print(f"{'Associativity':<25} {'Yes':<40}")
print(f"{'Identity':<25} {'I ∘ M = M ∘ I = M':<40}")
print(f"{'Determinism':<25} {'May need determinization':<40}")
print(f"{'Tools':<25} {'OpenFST, Foma, HFST':<40}")

📝 Morphological Analysis

🎯 FSTs for Word Structure

Morphological analysis is the task of breaking words into their constituent morphemes (roots, prefixes, suffixes) and identifying grammatical features. FSTs are the standard tool for this in computational linguistics.

Morphology with FSTs

Analysis: Surface → Lemma + Tags. Generation: Lemma + Tags → Surface. Two-level: Lexical ↔ Surface. Rules: Morphotactics + Orthography. Languages: Finnish, Turkish, English. Tools: Two-level morphology.

📝 Analysis🔧 Generation📊 Two-level🌍 Multilingual

# Morphological Analysis with FSTs
print("=== What is Morphological Analysis? ===")
print("""
Morphology: study of word structure.

Tasks:
  1. ANALYSIS: surface form → lemma + grammatical tags
     "cats" → "cat+N+PL"
     "running" → "run+V+PROG"
     
  2. GENERATION: lemma + tags → surface form
     "cat+N+PL" → "cats"
     "run+V+PROG" → "running"

FSTs are ideal because:
  - Finite state (morphology is regular)
  - Bidirectional (analysis and generation)
  - Compositional (build complex from simple)
  - Efficient (linear time)
""")

# SIMPLE MORPHOLOGICAL ANALYZER
print("\n=== Simple English Morphological Analyzer ===")
print("""
Analyzes regular English plurals.

Input:  word ending in 's'
Output: lemma + N + PL

Example:
  cats → cat+N+PL
  dogs → dog+N+PL
  boxes → box+N+PL (with e-insertion)
""")

# Simplified analyzer for regular plurals
class MorphAnalyzer:
    """Simple morphological analyzer."""
    
    def __init__(self):
        self.irregular = {
            'children': 'child+N+PL',
            'men': 'man+N+PL',
            'women': 'woman+N+PL',
            'feet': 'foot+N+PL',
            'teeth': 'tooth+N+PL',
            'mice': 'mouse+N+PL',
            'geese': 'goose+N+PL',
        }
    
    def analyze(self, word):
        """Analyze a word. Returns list of analyses."""
        analyses = []
        
        # Check irregulars
        if word in self.irregular:
            analyses.append(self.irregular[word])
            return analyses
        
        # Regular plural: ends in 's'
        if word.endswith('s'):
            stem = word[:-1]
            
            # Handle 'es' (boxes → box)
            if word.endswith('es'):
                stem = word[:-2]
                # Check if stem ends in s, x, z, ch, sh (needs 'es')
                if stem.endswith(('s', 'x', 'z', 'ch', 'sh')):
                    analyses.append(f"{stem}+N+PL")
                    return analyses
            
            # Handle 'ies' (cities → city)
            if word.endswith('ies'):
                stem = word[:-3] + 'y'
                analyses.append(f"{stem}+N+PL")
                return analyses
            
            # Simple 's'
            analyses.append(f"{stem}+N+PL")
            return analyses
        
        # Singular (no plural marker)
        analyses.append(f"{word}+N+SG")
        return analyses
    
    def generate(self, lemma, tags):
        """Generate surface form from lemma + tags."""
        if 'PL' not in tags:
            return lemma
        
        # Irregular
        for surface, analysis in self.irregular.items():
            if analysis == f"{lemma}+N+PL":
                return surface
        
        # Regular
        if lemma.endswith(('s', 'x', 'z', 'ch', 'sh')):
            return lemma + 'es'
        elif lemma.endswith('y') and len(lemma) > 1 and lemma[-2] not in 'aeiou':
            return lemma[:-1] + 'ies'
        else:
            return lemma + 's'


# Test
analyzer = MorphAnalyzer()

print("\nAnalysis:")
words = ['cat', 'cats', 'dog', 'dogs', 'box', 'boxes', 
         'city', 'cities', 'child', 'children', 'foot', 'feet']

for w in words:
    analyses = analyzer.analyze(w)
    print(f"  {w:<12} → {analyses}")

print("\nGeneration:")
tags_list = [
    ('cat', 'N+PL'), ('dog', 'N+PL'), ('box', 'N+PL'),
    ('city', 'N+PL'), ('child', 'N+PL'), ('foot', 'N+PL')
]

for lemma, tags in tags_list:
    surface = analyzer.generate(lemma, tags)
    print(f"  {lemma}+{tags:<8} → {surface}")

# TWO-LEVEL MORPHOLOGY
print("\n=== Two-Level Morphology ===")
print("""
Two-level morphology (Koskenniemi, 1983):

Two levels:
  1. LEXICAL: abstract morphemes
  2. SURFACE: actual word forms

Rules map between levels:
  - Morphotactic rules: which morphemes combine
  - Orthographic rules: how they combine

Example: English plural
  Lexical:  cat + s
  Surface:  cats

  Lexical:  box + s
  Surface:  boxes (e-insertion)
  
  Rule: s → es after s, x, z, ch, sh

FST implementation:
  - Each rule is an FST
  - Compose rules
  - Result: full morphological analyzer
""")

# BUILDING A TWO-LEVEL FST
print("\n=== Building a Two-Level FST ===")
print("""
Steps:
  1. Lexicon FST: maps lemma+tags → morpheme sequence
  2. Morphotactic FST: constrains morpheme combinations
  3. Orthographic FST: handles spelling changes
  4. Compose all three → full analyzer

Example: English plural

Lexicon:
  cat+N+PL → cat^s
  dog+N+PL → dog^s
  box+N+PL → box^s
  city+N+PL → city^s

Orthographic rules:
  s → es after s, x, z, ch, sh
  y → ies after consonant

Surface:
  cat^s → cats
  box^s → boxes
  city^s → cities
""")

# FINNISH EXAMPLE
print("\n=== Finnish Morphology (Famous Example) ===")
print("""
Finnish has complex morphology:

  talo     = house
  talossa  = in the house
  talosta  = from the house
  taloon   = into the house
  talolla  = at the house
  talolta  = from the house (adjacent)
  talolle  = to the house
  
  taloissa = in the houses
  taloista = from the houses
  ...

A single Finnish word can have:
  - Multiple suffixes
  - Complex morphophonemic changes

FSTs handle this elegantly:
  - One FST for each rule
  - Compose them
  - Efficient analysis/generation

Tools: HFST, Foma, OpenFST
""")

# TURKISH EXAMPLE
print("\n=== Turkish Morphology ===")
print("""
Turkish has agglutinative morphology:

  ev        = house
  evler     = houses
  evlerim   = my houses
  evlerimde = in my houses
  evlerimdekiler = those which are in my houses
  ...

FSTs are ideal for agglutinative languages.

Example:
  ev + ler + im + de + ki + ler
  house + PL + 1SG + LOC + REL + PL
""")

# PRACTICAL FST FOR MORPHOLOGY
print("\n=== Practical FST Implementation ===")

class MorphologicalFST:
    """
    A simple morphological FST for English plurals.
    """
    def __init__(self):
        # States: q0 (start), q1 (reading stem), q2 (need e), q3 (accept)
        self.states = {'q0', 'q1', 'q2', 'q3'}
        self.q0 = 'q0'
        self.F = {'q3'}
        
        # Transitions: (state, input) -> (next_state, output)
        self.delta = {}
        self.lam = {}
    
    def add_stem_letter(self, letter):
        """Add a stem letter transition."""
        self.delta[('q0', letter)] = 'q1'
        self.lam[('q0', letter)] = letter
        self.delta[('q1', letter)] = 'q1'
        self.lam[('q1', letter)] = letter
    
    def add_plural_rule(self):
        """Add plural rule: 's' → 's', but need context."""
        # After s, x, z, ch, sh: add 'es'
        # Simplified: we'll just add 's'
        self.delta[('q1', '+PL')] = 'q3'
        self.lam[('q1', '+PL')] = 's'
    
    def transduce(self, input_string):
        """Analyze or generate."""
        state = self.q0
        outputs = []
        for symbol in input_string:
            if (state, symbol) in self.delta:
                output = self.lam[(state, symbol)]
                state = self.delta[(state, symbol)]
                outputs.append(output)
            else:
                return None, False
        return ''.join(outputs), state in self.F


# More realistic: use the MorphAnalyzer above
print("We'll use the MorphAnalyzer class for practical examples.")

# MORPHOLOGICAL TAGS
print("\n=== Common Morphological Tags ===")
print("""
Part of Speech:
  N    = Noun
  V    = Verb
  ADJ  = Adjective
  ADV  = Adverb
  PRON = Pronoun
  DET  = Determiner
  PREP = Preposition
  CONJ = Conjunction

Number:
  SG   = Singular
  PL   = Plural
  DU   = Dual

Case:
  NOM  = Nominative
  ACC  = Accusative
  GEN  = Genitive
  DAT  = Dative
  LOC  = Locative
  ABL  = Ablative

Verb features:
  PRES = Present
  PAST = Past
  FUT  = Future
  PROG = Progressive
  1SG  = First person singular
  2SG  = Second person singular
  3SG  = Third person singular
  INF  = Infinitive
  PART = Participle

Example analysis:
  "running" → run+V+PROG
  "cats" → cat+N+PL
  "quickly" → quick+ADJ+ADV
""")

# APPLICATIONS
print("\n=== Applications of Morphological FSTs ===")
print("""
1. SPELL CHECKERS
   - Check if word is valid
   - Suggest corrections
   - Handle inflected forms

2. MACHINE TRANSLATION
   - Analyze source language
   - Generate target language
   - Handle morphology differences

3. INFORMATION RETRIEVAL
   - Index lemmas, not surface forms
   - Better search results

4. GRAMMAR CHECKERS
   - Verify agreement
   - Check case usage

5. TEXT-TO-SPEECH
   - Pronounce inflected forms
   - Handle irregular forms

6. LANGUAGE LEARNING
   - Generate exercises
   - Analyze student input
""")

🔊 Phonology & FSTs

🎯 Sound Patterns with FSTs

Phonology is the study of sound patterns in language. FSTs are used to model phonological rules, convert between spelling and pronunciation, and handle sound changes in speech recognition.

Phonology with FSTs

Rules: Sound changes. G2P: Grapheme to phoneme. P2G: Phoneme to grapheme. ASR: Speech recognition. TTS: Text to speech. Two-level: Lexical ↔ Surface.

🔊 Phonemes📝 G2P🔤 P2G🎙️ ASR/TTS

# Phonology and Finite State Transducers
print("=== What is Phonology? ===")
print("""
Phonology: study of sound patterns in language.

Key concepts:
  - Phonemes: abstract sound units (/k/, /æ/, /t/)
  - Allophones: surface variants ([kʰ], [k])
  - Rules: how phonemes map to allophones

Example: English plural rule
  /s/ after voiceless sounds: cats [kæts]
  /z/ after voiced sounds: dogs [dɔgz]
  /əz/ after sibilants: boxes [bɑksəz]

FSTs model these rules elegantly.
""")

# SIMPLE PHONOLOGICAL FST
print("\n=== English Plural Phonology ===")
print("""
Rule:
  - If stem ends in voiceless sound (p, t, k, f, θ): add /s/
  - If stem ends in voiced sound (b, d, g, v, ð, m, n, l, r): add /z/
  - If stem ends in sibilant (s, z, ʃ, ʒ, tʃ, dʒ): add /əz/

Examples:
  cat + s → cats [kæts]
  dog + s → dogs [dɔgz]
  box + s → boxes [bɑksəz]
""")

class PluralPhonologyFST:
    """FST for English plural phonology."""
    
    def __init__(self):
        self.voiceless = set('ptkfθ')
        self.voiced = set('bdgvðmnlr')
        self.sibilant = set('szʃʒ')
    
    def transduce(self, stem_phonemes, plural_tag='+PL'):
        """Add plural suffix based on final phoneme."""
        if not stem_phonemes:
            return stem_phonemes + 'z'  # default
        
        last = stem_phonemes[-1]
        
        if last in self.sibilant:
            return stem_phonemes + 'əz'
        elif last in self.voiceless:
            return stem_phonemes + 's'
        else:
            return stem_phonemes + 'z'


# Test
fst = PluralPhonologyFST()

print("\nPhonological pluralization:")
examples = [
    ('kæt', 'cat'),
    ('dɔg', 'dog'),
    ('bɑks', 'box'),
    ('bʊk', 'book'),
    ('rəʊz', 'rose'),
]

for phonemes, spelling in examples:
    plural = fst.transduce(phonemes)
    print(f"  {spelling:<8} {phonemes:<10} → {plural}")

# G2P AND P2G
print("\n=== Grapheme-to-Phoneme (G2P) ===")
print("""
G2P: Convert spelling to pronunciation.

  "cat" → /kæt/
  "dog" → /dɔg/
  "phone" → /foʊn/

Challenges:
  - English spelling is irregular
  - Context-dependent pronunciation
  - Homographs (read/read)

FST approaches:
  - Rule-based G2P
  - Data-driven G2P
  - Hybrid approaches

Tools:
  - Sequitur (OpenFST)
  - Phonetisaurus
  - CMUdict (dictionary-based)
""")

# SIMPLE G2P RULES
print("\n=== Simple G2P Rules for English ===")

g2p_rules = {
    'a': 'æ',
    'e': 'ɛ',
    'i': 'ɪ',
    'o': 'ɑ',
    'u': 'ʌ',
    'c': 'k',
    'ph': 'f',
    'sh': 'ʃ',
    'ch': 'tʃ',
    'th': 'θ',
}

def simple_g2p(word):
    """Simple G2P for English (very simplified)."""
    result = []
    i = 0
    while i < len(word):
        # Check digraphs
        if i + 1 < len(word):
            digraph = word[i:i+2]
            if digraph in g2p_rules:
                result.append(g2p_rules[digraph])
                i += 2
                continue
        
        # Single letter
        letter = word[i]
        result.append(g2p_rules.get(letter, letter))
        i += 1
    
    return ''.join(result)

print("\nSimple G2P:")
words = ['cat', 'dog', 'phone', 'ship', 'chat', 'thin']
for w in words:
    phonemes = simple_g2p(w)
    print(f"  {w:<8} → /{phonemes}/")

print("\n=== Phoneme-to-Grapheme (P2G) ===")
print("""
P2G: Convert pronunciation to spelling.

  /kæt/ → "cat"
  /dɔg/ → "dog"
  /foʊn/ → "phone"

Challenges:
  - Multiple spellings for same sound
  - /f/ can be "f" or "ph"
  - /k/ can be "c", "k", "ck", "ch"

Applications:
  - Speech recognition
  - Text-to-speech
  - Spelling correction
""")

# PHONOLOGICAL RULES
print("\n=== Phonological Rules ===")
print("""
Common phonological rules modeled with FSTs:

1. ASSIMILATION
   Sounds become more like neighbors.
   /ɪn/ + /pɒsɪbəl/ → [ɪmpɒsɪbəl] (impossible)

2. DELETION
   Sounds are removed.
   /hænd/ + /bæg/ → [hæmbæg] (handbag)

3. INSERTION
   Sounds are added.
   /sɪŋ/ + /ɪŋ/ → [sɪŋɪŋ] (singing)

4. METATHESIS
   Sounds are reordered.
   /æsk/ → [æks] (ask → ax)

5. FLAPPING (American English)
   /t/ → [ɾ] between vowels.
   /bʌtər/ → [bʌɾɚ] (butter)

FSTs can model all of these as transducers.
""")

# TWO-LEVEL PHONOLOGY
print("\n=== Two-Level Phonology ===")
print("""
Two-level model (Koskenniemi):

  LEXICAL level:  abstract phonemes
  SURFACE level:  actual sounds
  
  Rules map between levels.
  
  Example: English plural
    Lexical:  cat + s
    Surface:  cats [kæts]
    
    Rule: s → s after voiceless
          s → z after voiced
          s → əz after sibilant

Each rule is an FST.
Compose rules → full phonology.

This is the standard approach in computational phonology.
""")

# SPEECH RECOGNITION
print("\n=== FSTs in Speech Recognition ===")
print("""
Speech recognition pipeline:

  Audio → Acoustic Model → Phonemes → Language Model → Words

FSTs are used for:
  1. Pronunciation dictionary (word → phonemes)
  2. Context-dependent phones
  3. Language model (n-grams)
  4. Decoding (search)

Weighted FSTs (WFSTs):
  - Add probabilities to transitions
  - Find most likely word sequence

Components:
  H = HMM transducer (acoustic)
  C = Context dependency
  L = Lexicon (pronunciation)
  G = Grammar (language model)

Composition: H ∘ C ∘ L ∘ G
""")

# TEXT-TO-SPEECH
print("\n=== FSTs in Text-to-Speech ===")
print("""
TTS pipeline:

  Text → Normalization → G2P → Prosody → Waveform

FSTs are used for:
  1. Text normalization (numbers, dates)
  2. Grapheme-to-phoneme
  3. Morphological analysis
  4. Letter-to-sound rules

Example: Number normalization
  "42" → "forty two"
  "2024" → "twenty twenty four" or "two thousand twenty four"

Example: Abbreviation expansion
  "Dr." → "doctor"
  "St." → "street" or "saint"
""")

# PRACTICAL FST FOR PHONOLOGY
print("\n=== Practical: Finnish Consonant Gradation ===")
print("""
Finnish has consonant gradation:

  kk → k    (strong → weak)
  pp → p
  tt → t
  k → ∅
  p → v
  t → d

Example:
  kukka (flower) → kukan (of the flower)
  pappi (priest) → papin
  matto (mat) → maton

This is modeled with FSTs in HFST.
""")

# COMPOSITION FOR PHONOLOGY
print("\n=== Composition for Phonology ===")
print("""
Phonological rules compose:

  M = M1 ∘ M2 ∘ M3 ∘ ... ∘ Mn

Each Mi is one rule.

Example: English plural
  M1: s → z after voiced
  M2: s → əz after sibilant
  M3: s → s elsewhere

Composition handles rule ordering.

This is the basis of:
  - Two-level morphology
  - Computational phonology
  - Speech technology
""")

💼 Applications

🎯 Real-World Impact

Finite State Transducers are widely used in natural language processing, speech recognition, machine translation, and compiler design. They provide an efficient, compositional framework for string transformation.

Application Areas

NLP: Morphology, phonology. Speech: ASR, TTS. Translation: Machine translation. Compilers: Lexing, parsing. Search: Query expansion. Bio: Sequence analysis.

📝 NLP🎙️ Speech🌐 Translation💻 Compilers

# Applications of Finite State Transducers
print("=== 1. Natural Language Processing ===")
print("""
Morphological Analysis:
  - Analyze word structure
  - Identify lemma + tags
  - Used in: parsers, taggers, lemmatizers

Example:
  "running" → run+V+PROG
  "cats" → cat+N+PL

Tools:
  - Foma
  - HFST
  - OpenFST
  - Xerox FST

Languages:
  - English (simple)
  - Finnish (complex)
  - Turkish (agglutinative)
  - Arabic (non-concatenative)
""")

print("\n=== 2. Speech Recognition (ASR) ===")
print("""
Weighted FSTs in ASR:

Pipeline:
  Audio → HMM → Phonemes → Lexicon → Words → Language Model

FST components:
  H = HMM transducer
  C = Context dependency
  L = Lexicon (pronunciation)
  G = Grammar (n-gram)

Composition: H ∘ C ∘ L ∘ G

Benefits:
  - Efficient search
  - Modular design
  - Probabilistic

Tools:
  - Kaldi
  - HTK
  - Julius
""")

print("\n=== 3. Machine Translation ===")
print("""
FSTs in MT:

  Source → Analysis → Transfer → Generation → Target

Steps:
  1. Analyze source morphology
  2. Transfer to target structures
  3. Generate target morphology

FSTs used for:
  - Morphological analysis
  - Morphological generation
  - Word-level translation
  - Reordering

Example:
  English "cats" → [cat+N+PL]
  Transfer → [gato+N+PL]
  Generate → "gatos" (Spanish)
""")

print("\n=== 4. Compilers and Language Processing ===")
print("""
Lexical Analysis:
  - Tokenizer as FST
  - Input: characters
  - Output: tokens

Example: Number lexer
  Input: "123.45"
  Output: 

Parsing:
  - Some parsers use FSTs
  - Chart parsing
  - Finite-state parsing

Tools:
  - Lex/Flex (uses DFA)
  - FST-based lexers
""")

print("\n=== 5. Text Processing ===")
print("""
Text Normalization:
  - Numbers to words
  - Dates to standard format
  - Abbreviations expansion

Example:
  "42" → "forty two"
  "2024-01-15" → "January 15, 2024"
  "Dr." → "doctor"

Spell Checking:
  - Generate valid forms
  - Check against FST
  - Suggest corrections

Tokenization:
  - Split text into tokens
  - Handle punctuation
  - Multi-word tokens
""")

print("\n=== 6. Information Retrieval ===")
print("""
Query Expansion:
  - Expand search terms
  - Include morphological variants

Example:
  Search: "running"
  Expand: run, runs, ran, running

Indexing:
  - Index lemmas, not surface forms
  - Better recall
  - Smaller index

FSTs used for:
  - Lemmatization
  - Stemming
  - Synonym expansion
""")

print("\n=== 7. Bioinformatics ===")
print("""
Sequence Analysis:
  - DNA/RNA/protein sequences
  - Pattern matching
  - Sequence alignment

FSTs used for:
  - Sequence transduction
  - Pattern recognition
  - Motif finding

Example:
  DNA → RNA transcription
  DNA: ATGC → RNA: AUGC

  FST: A→A, T→U, G→G, C→C
""")

print("\n=== 8. Handwriting Recognition ===")
print("""
OCR Post-processing:
  - Correct OCR errors
  - FST-based error models
  - Language model integration

Example:
  OCR: "hel1o" → Corrected: "hello"

FSTs model:
  - Character confusion
  - Context-dependent errors
  - Word-level correction
""")

# PRACTICAL EXAMPLE: SPELL CHECKER
print("\n=== Practical Example: Spell Checker with FST ===")

class SpellChecker:
    """Simple spell checker using morphological FST."""
    
    def __init__(self):
        # Vocabulary of lemmas
        self.lemmas = {'cat', 'dog', 'box', 'city', 'child', 'run', 'walk'}
        self.analyzer = MorphAnalyzer()
    
    def is_valid(self, word):
        """Check if word is valid."""
        # Try to analyze
        analyses = self.analyzer.analyze(word)
        for analysis in analyses:
            lemma = analysis.split('+')[0]
            if lemma in self.lemmas:
                return True
        return False
    
    def suggest(self, word):
        """Suggest corrections."""
        suggestions = []
        # Simple edit distance
        for lemma in self.lemmas:
            # Generate plural
            plural = self.analyzer.generate(lemma, 'N+PL')
            if self._edit_distance(word, plural) <= 2:
                suggestions.append(plural)
            if self._edit_distance(word, lemma) <= 2:
                suggestions.append(lemma)
        return suggestions
    
    def _edit_distance(self, s1, s2):
        """Levenshtein distance."""
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(m + 1):
            dp[i][0] = i
        for j in range(n + 1):
            dp[0][j] = j
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i-1] == s2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
        
        return dp[m][n]


# Test
checker = SpellChecker()

print("\nSpell checking:")
words = ['cat', 'cats', 'dog', 'dogs', 'box', 'boxes', 
         'ct', 'dogg', 'bx', 'citty']

for w in words:
    valid = checker.is_valid(w)
    status = "✓" if valid else "✗"
    suggestions = checker.suggest(w) if not valid else []
    print(f"  {status} {w:<10} {('suggestions: ' + str(suggestions)) if suggestions else ''}")

# SUMMARY
print("\n=== Application Summary ===")
print(f"{'Domain':<25} {'Use Case':<35} {'FST Role':<25}")
print("-" * 85)
print(f"{'NLP':<25} {'Morphological analysis':<35} {'Analysis/generation':<25}")
print(f"{'Speech':<25} {'ASR/TTS':<35} {'Pronunciation modeling':<25}")
print(f"{'Translation':<25} {'Machine translation':<35} {'Transfer rules':<25}")
print(f"{'Compilers':<25} {'Lexical analysis':<35} {'Tokenization':<25}")
print(f"{'Text':<25} {'Normalization':<35} {'Rewriting rules':<25}")
print(f"{'Search':<25} {'Query expansion':<35} {'Morphological variants':<25}")
print(f"{'Bio':<25} {'Sequence analysis':<35} {'Pattern matching':<25}")
print(f"{'OCR':<25} {'Post-processing':<35} {'Error correction':<25}")

🛠️ Tools & Libraries

🎯 FST Software

Many tools and libraries exist for working with Finite State Transducers. These range from general-purpose FST libraries to specialized morphological analyzers.

FST Tools

OpenFST: C++ library. Foma: Morphology. HFST: NLP toolkit. Xerox: Commercial. Python: Various bindings. Web: Online tools.

🔧 OpenFST📝 Foma🌍 HFST🐍 Python

# Tools and libraries for Finite State Transducers
print("=== 1. OpenFST ===")
print("""
OpenFST (Google):
  - C++ library for FSTs
  - Weighted FSTs
  - Composition, determinization, minimization
  - Used in speech recognition

Website: http://www.openfst.org

Features:
  - Efficient algorithms
  - Weighted transducers
  - Lazy composition
  - Python bindings (pywrapfst)

Example usage:
  import pywrapfst as fst
  
  # Create FST
  t = fst.Transducer()
  s1 = t.add_state()
  s2 = t.add_state()
  t.set_start(s1)
  t.set_final(s2)
  t.add_arc(s1, fst.Arc(ord('a'), ord('x'), 0, s2))
""")

print("\n=== 2. Foma ===")
print("""
Foma (Mans Hulden):
  - FST compiler and library
  - Focus on morphology
  - C library with scripting language
  - Successor to Xerox lexc/foma

Website: https://github.com/mhulden/foma

Features:
  - Regular expression syntax
  - Composition
  - Determinization
  - Minimization
  - Weighted FSTs

Example:
  define Plural [..] ;
  regex [a-z]+ -> ... ;
""")

print("\n=== 3. HFST ===")
print("""
HFST (Helsinki Finite-State Technology):
  - NLP toolkit for FSTs
  - Multiple backends (OpenFST, Foma)
  - Morphological analysis
  - Language technology

Website: https://hfst.github.io

Features:
  - Command-line tools
  - Python API
  - Support for many languages
  - Compatible with Foma, OpenFST

Tools:
  hfst-lexc    — lexicon compiler
  hfst-twolc   — two-level rule compiler
  hfst-compose — composition
  hfst-determinize — determinization
""")

print("\n=== 4. Xerox FST ===")
print("""
Xerox Finite State Tools:
  - Commercial FST tools
  - lexc, twolc, xfst
  - Used in industry

Features:
  - lexc: lexicon compiler
  - twolc: two-level rules
  - xfst: FST operations

Note: Largely superseded by Foma/HFST.
""")

print("\n=== 5. Python Libraries ===")
print("""
Python FST libraries:

1. pywrapfst (OpenFST bindings)
   - Full OpenFST API
   - Efficient
   - C++ backend

2. pynini
   - Python wrapper for OpenFST
   - String compilation
   - Used in Google

3. fstlib
   - Pure Python FST
   - Educational
   - Simple API

4. PyFST
   - Python FST
   - Basic operations

Example (pynini):
  import pynini
  rule = pynini.string_map([("cat", "cats"), ("dog", "dogs")])
  result = pynini.compose(rule, "cat")
""")

# PRACTICAL PYTHON EXAMPLE
print("\n=== Practical Python Example ===")
print("""
Using pynini (if installed):

  import pynini
  
  # Create a simple FST
  # Maps "a" to "x", "b" to "y"
  fst = pynini.string_map([("a", "x"), ("b", "y")])
  
  # Apply to input
  result = pynini.compose(fst, "ab")
  print(result)  # "xy"
  
  # Compose two FSTs
  fst1 = pynini.string_map([("a", "x")])
  fst2 = pynini.string_map([("x", "1")])
  composed = fst1 @ fst2  # composition
  result = pynini.compose(composed, "a")
  print(result)  # "1"
""")

# SIMPLE PYTHON FST
print("\n=== Simple Python FST (Educational) ===")

class SimpleFST:
    """Educational FST implementation."""
    
    def __init__(self):
        self.transitions = {}  # (state, input) -> (next_state, output)
        self.q0 = 'q0'
        self.F = set()
    
    def add_transition(self, state, input_sym, next_state, output):
        self.transitions[(state, input_sym)] = (next_state, output)
    
    def add_final(self, state):
        self.F.add(state)
    
    def transduce(self, input_string):
        state = self.q0
        output = []
        for sym in input_string:
            if (state, sym) not in self.transitions:
                return None, False
            next_state, out = self.transitions[(state, sym)]
            output.append(out)
            state = next_state
        return ''.join(output), state in self.F
    
    def compose(self, other):
        """Compose with another FST."""
        # Simplified composition
        result = SimpleFST()
        # ... (complex implementation)
        return result


# Example
fst = SimpleFST()
fst.add_transition('q0', 'a', 'q1', 'x')
fst.add_transition('q1', 'b', 'q2', 'y')
fst.add_final('q2')

output, accepted = fst.transduce('ab')
print(f"Input: 'ab'")
print(f"Output: '{output}'")
print(f"Accepted: {accepted}")

# WEB TOOLS
print("\n=== Web-Based FST Tools ===")
print("""
1. Foma Online
   - Web interface for Foma
   - Try FST operations

2. HFST Online
   - Web interface for HFST
   - Morphological analysis

3. OpenFST Web
   - Online demos

4. FST Sandbox
   - Interactive FST editor

5. Grammatical Framework
   - GF uses FSTs
   - Web-based IDE
""")

# COMMAND-LINE TOOLS
print("\n=== Command-Line Tools ===")
print("""
HFST commands:
  hfst-lexc input.lexc -o output.hfst
  hfst-twolc input.twolc -o rules.hfst
  hfst-compose -1 lexicon.hfst -2 rules.hfst -o analyzer.hfst
  hfst-determinize analyzer.hfst
  hfst-minimize analyzer.hfst
  hfst-lookup analyzer.hfst

Foma commands:
  foma> define Plural ...
  foma> regex ...
  foma> compose ...
  foma> determinize ...
  foma> minimize ...

OpenFST commands:
  fstcompile --isymbols=... --osymbols=... input.txt output.fst
  fstcompose input1.fst input2.fst output.fst
  fstshortestpath input.fst output.fst
  fstprint input.fst
""")

# SUMMARY TABLE
print("\n=== Tools Summary ===")
print(f"{'Tool':<20} {'Type':<15} {'Language':<15} {'Best For':<30}")
print("-" * 85)
print(f"{'OpenFST':<20} {'Library':<15} {'C++':<15} {'Speech, general':<30}")
print(f"{'Foma':<20} {'Compiler':<15} {'C':<15} {'Morphology':<30}")
print(f"{'HFST':<20} {'Toolkit':<15} {'Multiple':<15} {'NLP, many languages':<30}")
print(f"{'Xerox':<20} {'Commercial':<15} {'Multiple':<15} {'Industry':<30}")
print(f"{'pywrapfst':<20} {'Python':<15} {'Python':<15} {'OpenFST in Python':<30}")
print(f"{'pynini':<20} {'Python':<15} {'Python':<15} {'Google, string rules':<30}")

🚀 Future: FST in Modern Computing

🎯 Where FSTs Are Going

Finite State Transducers remain essential in NLP and speech, but their use is expanding into new areas: neural-symbolic AI, quantum computing, and large-scale text processing. The compositional framework of FSTs is more relevant than ever.

Future Directions

Neural: FSTs + deep learning. Quantum: Quantum FSTs. Scale: Web-scale NLP. Multilingual: 7000+ languages. Real-time: Streaming. Interpretable: Explainable AI.

🧠 Neural⚛️ Quantum🌐 Scale🔍 Interpretable

# Future of Finite State Transducers
print("=== 1. Neural-Symbolic Integration ===")
print("""
Combining FSTs with neural networks:

Approach 1: FST as output layer
  - Neural network encodes input
  - FST decodes to output
  - Differentiable FST

Approach 2: FST as constraint
  - Neural model generates candidates
  - FST filters valid outputs
  - Guarantees well-formedness

Approach 3: FST as features
  - FST features fed to neural network
  - Hybrid architecture

Applications:
  - Morphological generation
  - Speech recognition
  - Machine translation

Benefits:
  - Interpretable
  - Guaranteed correctness
  - Data-efficient
""")

print("\n=== 2. Quantum Finite State Transducers ===")
print("""
Quantum FSTs:
  - States in superposition
  - Transitions as unitary operators
  - Measurement at end

Potential advantages:
  - Exponential state compression
  - Quantum parallelism
  - New capabilities

Challenges:
  - Decoherence
  - Error correction
  - Limited qubits

Research directions:
  - Quantum morphology
  - Quantum speech recognition
  - Quantum NLP
""")

print("\n=== 3. Web-Scale NLP ===")
print("""
FSTs for massive text processing:

Scale:
  - Billions of documents
  - Trillions of tokens
  - 7000+ languages

Requirements:
  - Efficient composition
  - Lazy evaluation
  - Distributed processing

Tools:
  - OpenFST (optimized)
  - HFST (multi-language)
  - Custom distributed FSTs

Applications:
  - Web search
  - Machine translation
  - Content analysis
""")

print("\n=== 4. Low-Resource Languages ===")
print("""
FSTs for endangered languages:

Advantages:
  - Rule-based (less data needed)
  - Interpretable
  - Compositional

Projects:
  - Giellatekno (Sámi languages)
  - Apertium (open-source MT)
  - HFST (many languages)

Future:
  - Automated FST induction
  - Transfer learning
  - Community-driven development
""")

print("\n=== 5. Real-Time Processing ===")
print("""
Streaming FSTs:
  - Process data as it arrives
  - Constant memory
  - Low latency

Applications:
  - Real-time speech recognition
  - Live translation
  - Streaming text analysis

Techniques:
  - Lazy composition
  - Incremental determinization
  - Window-based processing
""")

print("\n=== 6. Interpretable AI ===")
print("""
FSTs for explainable AI:

Advantages:
  - Rules are explicit
  - Decisions are traceable
  - Verifiable

Applications:
  - Medical NLP
  - Legal text analysis
  - Financial compliance

Hybrid approaches:
  - Neural network + FST
  - Neural model generates
  - FST verifies/explains

Future:
  - FSTs as explanation layer
  - FSTs for bias detection
  - FSTs for fairness
""")

print("\n=== 7. New Frontiers ===")
print("""
Continuous FSTs:
  - Continuous states
  - Hybrid automata
  - Cyber-physical systems

Probabilistic FSTs:
  - Weighted transducers
  - Bayesian networks
  - Reinforcement learning

Timed FSTs:
  - Time constraints
  - Real-time systems
  - Scheduling

Open Problems:
  - Scalable determinization
  - Learning FSTs from data
  - Quantum FST applications
""")

print("\n=== Timeline ===")
print("""
Past:
  1950s: Finite state transducers defined
  1980s: Two-level morphology
  1990s: Weighted FSTs
  2000s: OpenFST, HFST
  2010s: Neural-symbolic integration

Present:
  2020s: FSTs + deep learning
  2025: Web-scale NLP

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

print("\n=== Final Thoughts ===")
print("""
Finite State Transducers are:

  - Simple to understand
  - Powerful in practice
  - Fundamental to NLP
  - Compositional and modular
  - Efficient (linear time)

They show us:
  - Transformation is computation
  - Simple rules → complex behavior
  - Composition is key

Whether we analyze morphology, recognize speech,
or build the next generation of AI,
FSTs will be there.

"All string transformation is finite-state,
 all the way down."

Keep exploring. Keep building.
""")