gen-define-a-finite-automaton-and-give-one-short-worked-example-dba6

Define a finite automaton and give one short worked example.

# Finite Automaton ## Definition A **finite automaton** (FA) is a mathematical model of computation consisting of: 1. **Q**: A finite set of states 2. **Σ**: A finite input alphabet 3. **δ**: A transition function: Q × Σ → Q 4. **q₀**: An initial/start state (q₀ ∈ Q) 5. **F**: A set of accepting/final states (F ⊆ Q) The automaton processes an input string symbol by symbol, transitioning between states according to δ, and **accepts** the string if it ends in a state in F. ## Worked Example **Design an FA that accepts all binary strings ending in "01"** **Solution:** - Q = {q₀, q₁, q₂} - Σ = {0, 1} - F = {q₂} - Transition function δ: | State | Input 0 | Input 1 | |-------|---------|---------| | q₀ | q₁ | q₀ | | q₁ | q₁ | q₂ | | q₂ | q₁ | q₀ | **Trace on input "1001":** - Start: **q₀** - Read '1': q₀ → **q₀** - Read '0': q₀ → **q₁** - Read '0': q₁ → **q₁** - Read '1': q₁ → **q₂** ✓ Ends in q₂ ∈ F, so the string is **accepted**.