Finite Automata

A finite automaton (FA) is an abstract machine that:

1. Has a finite number of states.
2. Reads an input string one symbol at a time, left to right.
3. At each step, moves from its current state to a new state based on the current symbol.
4. After reading the entire input, it either accepts the string (if it ended in an accepting state) or rejects it.

Finite automata are the mathematical model behind lexical analysers. Every token pattern described by a regular expression can be recognised by a finite automaton.

Informal Example — A Turnstile

Imagine a subway turnstile. It has two states: Locked and Unlocked.

This turnstile is a finite automaton with:

• States: {Locked, Unlocked}
• Input symbols (alphabet): {P, C}
• Transitions: as shown above
• Start state: Locked
• (There's no accepting state here — this is a Moore machine, but the concept is identical)

A finite automaton is formally defined as a 5-tuple:

Two Types of Finite Automata

Both accept exactly the same class of languages — the regular languages. NFAs are easier to design; DFAs are easier to implement. The next two topics cover each in detail.

Finite automata are typically drawn as state transition diagrams:

• Circles represent states.
• Double circles represent accepting (final) states.
• Arrows represent transitions, labelled with the input symbol.
• A filled arrow (→) points to the start state.

Diagram Conventions

Example — Automaton Accepting Strings Ending in 'a'

Language: all strings over {a, b} that end with the character 'a'. Examples of accepted strings: a, ba, aa, bba, aba, bbba, …

Reading the diagram:

• q0 = start state, "have not just seen 'a'"
• q1 = accepting state, "most recent symbol was 'a'"
• On reading 'a' from q0 → move to q1 (we just saw 'a')
• On reading 'b' from q0 → stay in q0 (still haven't ended with 'a')
• On reading 'a' from q1 → stay in q1 (still ending with 'a')
• On reading 'b' from q1 → go back to q0 (the 'a' is no longer the last symbol)

Trace on "bba":

Trace on "ab":

Given a finite automaton M = (Q, Σ, δ, q₀, F) and an input string w = a₁a₂…aₙ:

Acceptance Definition

If all three conditions hold, the machine accepts the string. If any condition fails — especially if rₙ ∉ F — the machine rejects the string.

Extended Transition Function δ*

For convenience, we define δ* (delta-star) as the extended transition function that takes a state and an entire string (not just one symbol):

With this, we can write the acceptance condition compactly:

Language of a Finite Automaton

The set of all strings that automaton M accepts is called the language of M, written L(M):

Key theorem (Kleene): A language L is regular (described by a regular expression) if and only if some finite automaton M recognises it, i.e., L = L(M).

A transition table is a tabular alternative to the state diagram — especially useful for larger automata.

Example — Automaton for Strings Ending in 'a'

Notation:

• → marks the start state
• ***** marks accepting states
• Rows = states, Columns = input symbols
• Cell = the target state after the transition

Reading the table:

• Row q0, column a → q1 (matches the diagram arrow q0 --a--> q1)
• Row q0, column b → q0 (loop on q0 with b)
• Row q1, column a → q1 (loop on q1 with a)
• Row q1, column b → q0 (go back to q0)

Trace using the Transition Table — "bab"

Trace — "aba"