A FINITE AUTOMATON IS A MACHINE WITH A FINITE NUMBER OF STATES THAT READS AN INPUT STRING ONE SYMBOL AT A TIME AND CHANGES STATE ACCORDING TO WHAT IT READS. THE DEFINING LIMITATION, from which everything follows: ITS ONLY MEMORY IS ITS CURRENT STATE. It cannot count beyond the number of states it has, cannot store the input, and cannot look back at what it has already read. ── THE FORMAL DEFINITION ─────────────────────────────────── A DETERMINISTIC FINITE AUTOMATON (DFA) is a 5-tuple M = (Q, Σ, δ, q₀, F) Q a FINITE set of STATES Σ a finite INPUT ALPHABET δ the TRANSITION FUNCTION, δ : Q × Σ → Q q₀ the START STATE, q₀ ∈ Q F the set of ACCEPTING (final) STATES, F ⊆ Q "DETERMINISTIC" IS ENTIRELY CONTAINED IN THE TYPE OF δ: for EVERY state and EVERY symbol there is EXACTLY ONE next state. No choice, no ambiguity, and no missing transition. ACCEPTANCE: the automaton starts in q₀, consumes the whole input, and ACCEPTS if and when it finishes it is in a state belonging to F. The set of all strings it accepts is the LANGUAGE OF M, written L(M). ── NON-DETERMINISTIC FINITE AUTOMATON (NFA) ──────────────── Same 5-tuple, with one change: δ : Q × Σ → P(Q) (the POWER SET of Q) So a transition leads to a SET of possible states — possibly empty, possibly several. An NFA may also have ε-TRANSITIONS, changing state without consuming any input. ACCEPTANCE FOR AN NFA: the string is accepted IF THERE EXISTS AT LEAST ONE PATH through the machine that consumes the whole input and ends in an accepting state. THE USEFUL MENTAL MODEL: the NFA explores ALL possible paths SIMULTANEOUSLY and accepts if ANY of them succeeds. It is a machine that guesses correctly whenever a correct guess exists. THE CENTRAL RESULT, developed fully in the next topic: DFAs AND NFAs RECOGNISE EXACTLY THE SAME CLASS OF LANGUAGES. Non-determinism adds CONVENIENCE, not POWER. ── REPRESENTATIONS ───────────────────────────────────────── TRANSITION DIAGRAM — states as circles, transitions as labelled arrows, the start state marked by an incoming arrow, accepting states drawn as DOUBLE CIRCLES. TRANSITION TABLE — rows are states, columns are symbols, entries are the next state. THE 5-TUPLE — the formal definition itself. A WORKED EXAMPLE: a DFA accepting binary strings with an EVEN number of 1s. Q = {q₀, q₁}, Σ = {0,1}, F = {q₀} δ(q₀,0)=q₀ δ(q₀,1)=q₁ δ(q₁,0)=q₁ δ(q₁,1)=q₀ THE STATE ENCODES THE ONLY THING THAT MATTERS: the parity of the 1s seen so far. It does not remember how many, or where — ONLY WHETHER THE COUNT IS ODD OR EVEN, which is exactly one bit of memory. THAT IS THE DESIGN PRINCIPLE FOR EVERY DFA: identify the minimal information about the prefix that determines the future behaviour, and make that the state.

── ACCEPTORS VERSUS TRANSDUCERS ──────────────────────────── The automata above are ACCEPTORS: they answer yes or no. A FINITE STATE MACHINE WITH OUTPUT — a TRANSDUCER — produces an output string as it runs. Two standard forms: MOORE MACHINE — OUTPUT DEPENDS ON THE STATE ALONE. M = (Q, Σ, Δ, δ, λ, q₀) with λ : Q → Δ Each state has an output associated with it, emitted on entry. FOR AN INPUT OF LENGTH n, A MOORE MACHINE PRODUCES n+1 OUTPUT SYMBOLS, because the start state emits one before any input is read. MEALY MACHINE — OUTPUT DEPENDS ON THE STATE AND THE INPUT. λ : Q × Σ → Δ Output is emitted on the TRANSITION. FOR AN INPUT OF LENGTH n IT PRODUCES n OUTPUT SYMBOLS. THE COMPARISON: MOORE MEALY ─────────────────────────────────────────────────────── output depends on STATE only state AND input output written on the state on the transition outputs for input length n n + 1 n states needed generally MORE generally FEWER reacts to input one clock later IMMEDIATELY timing/glitches output is stable output can glitch (synchronous with when input changes the state) ─────────────────────────────────────────────────────── THEY ARE EQUIVALENT IN POWER: any Moore machine can be converted to a Mealy machine and vice versa. The choice is an ENGINEERING one — Mealy for fewer states and faster response, Moore for stable, glitch-free outputs, which is why Moore is often preferred in synchronous digital design. ── WHAT FINITE AUTOMATA CAN AND CANNOT DO ────────────────── THEY RECOGNISE EXACTLY THE REGULAR LANGUAGES — the class also described by regular expressions and by regular grammars. THEY CAN RECOGNISE: · strings containing a given substring · strings ending in a given pattern · strings whose length is divisible by k · strings with an even number of some symbol · any language describable by a regular expression IN GENERAL: ANYTHING REQUIRING ONLY A BOUNDED AMOUNT OF MEMORY. THEY CANNOT RECOGNISE: · { aⁿbⁿ : n ≥ 0 } — equal numbers of a's then b's · balanced parentheses · palindromes · { aⁿbⁿcⁿ } IN GENERAL: ANYTHING REQUIRING UNBOUNDED COUNTING OR MEMORY OF ARBITRARY LENGTH. THE INTUITION FOR WHY aⁿbⁿ IS IMPOSSIBLE, which is the argument formalised by the pumping lemma later in this section: A DFA has some finite number of states, say k. To accept aⁿbⁿ it must "remember" how many a's it has read so as to require the same number of b's. But there are infinitely many possible counts and only k states, so BY THE PIGEONHOLE PRINCIPLE two different counts must lead to the same state — and once in that state the machine cannot distinguish them, so it will accept a string with mismatched counts. THE MEMORY IS FINITE AND THE REQUIREMENT IS NOT. ── WHERE THEY ARE USED ───────────────────────────────────── · LEXICAL ANALYSIS in compilers — recognising identifiers, numbers and keywords · pattern matching and regular expression engines · PROTOCOL SPECIFICATION — TCP's connection state machine is a finite automaton · digital circuit design — sequential circuits ARE finite state machines · control systems: traffic lights, lifts, vending machines · text processing, spell checking, and tokenising · game AI and user interface state THE COMMON THREAD: WHEREVER BEHAVIOUR DEPENDS ON A BOUNDED AMOUNT OF HISTORY, A FINITE AUTOMATON IS THE RIGHT MODEL — and being able to recognise that situation is the practical value of the theory.