Think of the light switch on your wall. It is always in one of two situations, ON or OFF. Pressing it moves it from one situation to the other. It does not remember how many times it has been pressed, or when; the only thing it "knows" is its current situation. Yet that is enough for it to do its job perfectly.
A finite automaton is exactly this idea turned into mathematics: a machine with a fixed, finite number of situations (called states) that reads its input one symbol at a time and moves between states according to fixed rules. It is the simplest model of computation in TOC, and also the most widely used in practice: lexical analysers, regex engines, network protocols and digital circuits are all finite automata at heart.
In this chapter we will see how a finite automaton works, how to draw and tabulate one, trace two complete examples, meet the different kinds of finite automata, and understand what such a machine fundamentally cannot do. We use the vocabulary of Alphabets, Strings & Languages. The fully formal definition comes in the next chapter, Deterministic Finite Automata (DFA).
The Machine Model
Picture a finite automaton as three parts:
input tape (read only)
+---+---+---+---+---+---+
| 1 | 0 | 1 | 1 | | |
+---+---+---+---+---+---+
^
| read head: moves one cell to the RIGHT after every symbol,
| never goes back, never writes
+-------------------+
| finite control |
| current state: q |
+-------------------+The input tape holds the input string, one symbol per cell. It is read-only.
The read head starts at the leftmost symbol and moves exactly one cell to the right at every step.
The finite control is always in one of finitely many states. At each step it looks at its current state and the symbol under the head, and a rule tells it the next state.
When the head moves past the last symbol, the machine stops. If it is in one of the specially marked final (accepting) states, the string is accepted; otherwise it is rejected.
A finite automaton (FA) is a machine with a finite set of states, a start state, a set of final states and transition rules, which reads an input string left to right, one symbol per step, and accepts the string if it ends in a final state.
Notice what is missing: there is no extra memory. No variables, no stack, no writing on the tape. Everything the machine remembers about the input so far must be encoded in which state it is in. This is both the beauty and the limitation of finite automata.
Components of a Finite Automaton
Component | Symbol | Meaning |
|---|---|---|
States | Q | A finite set of situations the machine can be in |
Input alphabet | Σ | The symbols that may appear on the tape |
Transition function | δ | The rules: (current state, symbol read) → next state |
Start state | q0 | The state before any symbol is read |
Final states | F | The states that mean "accept if the input ends here" (F ⊆ Q, may be empty) |
These five pieces make up the famous 5-tuple (Q, Σ, δ, q0, F). The kinds of finite automata differ mainly in what δ is allowed to return: exactly one state (deterministic) or a set of states (nondeterministic).
Two Ways to Draw an Automaton
1. Transition Diagram
A transition diagram (state diagram) is a directed graph:
Each state is a circle (we write it as
( q )in text).The start state has an arrow coming in from nowhere (
-->).Each final state is a double circle (we write
(( q ))).An arrow from p to q labelled a means "in state p, reading a, go to q". A self-loop means the state does not change.
2. Transition Table
A transition table has one row per state and one column per symbol. Each cell gives the next state. By convention the start state is marked with → and final states with *. Tables are what you would actually store in a program, and they are the easiest format for checking an answer.
Example 1: Odd Number of 1s
Problem: Over Σ = {0, 1}, accept exactly the strings that contain an odd number of 1s.
Thinking: Do we need to remember the whole string? No. We only need to know whether the number of 1s so far is even or odd. That is one bit of information, so two states are enough:
EVEN: an even number of 1s seen so far (this is the start, since zero 1s is even).
ODD: an odd number of 1s seen so far (this is the final state).
A 0 does not change the count; a 1 flips it.
0 0
+---+ +---+
| v | v
--> ( EVEN ) ----1---> (( ODD ))
<---1----State | on 0 | on 1 |
|---|---|---|
→ EVEN | EVEN | ODD |
* ODD | ODD | EVEN |
Tracing the Machine
Input 1011:
step state before read state after
1 EVEN 1 ODD
2 ODD 0 ODD
3 ODD 1 EVEN
4 EVEN 1 ODD
end: ODD is final => ACCEPT (1011 has three 1s)Input 1001: EVEN →1→ ODD →0→ ODD →0→ ODD →1→ EVEN. Ends in EVEN, so REJECT (two 1s). Input 100: EVEN → ODD → ODD → ODD, ACCEPT. And the empty string ε: no moves at all, the machine stays in EVEN, so ε is rejected (zero 1s is even). Always check ε separately: it is accepted exactly when the start state is final.
We tested this machine against the definition "number of 1s is odd" on all 2047 binary strings of length 0 to 10; it agreed on every one.
Example 2: A Vending Machine
A machine sells a ₹15 snack and accepts ₹5 and ₹10 coins. It releases the snack once the total inserted is at least ₹15. Let the alphabet be Σ = {f, t}, where f means "a ₹5 coin" and t means "a ₹10 coin".
Thinking: The machine only needs to know the total so far, and once the total reaches 15 the exact amount no longer matters for our question. So the states are the totals 0, 5, 10 and "15 or more".
t
+-------------------------------+
| v
--> ( S0 ) ---f---> ( S5 ) ---f---> ( S10 ) ---f,t---> (( S15 )) ---+
| ^ ^ | f, t
| t | | | (self-loop)
+-----------------------------------+ +------+State | on f (₹5) | on t (₹10) |
|---|---|---|
→ S0 | S5 | S10 |
S5 | S10 | S15 |
S10 | S15 | S15 |
* S15 | S15 | S15 |
Traces: ff goes S0 → S5 → S10, rejected (only ₹10). tf goes S0 → S10 → S15, accepted. fft goes S0 → S5 → S10 → S15, accepted (₹20).
The state S15 never leaves itself on any input. A non-final state with this property is called a dead (trap) state; a final one like S15 is sometimes called an accepting sink. You will see both kinds constantly when designing automata.
The Central Idea: A State Is a Summary of the Past
In both examples, we designed the machine by asking one question:
"What is the least I must remember about the input read so far to decide correctly, whatever comes next?"
Each possible answer becomes a state. For "odd number of 1s" the answer is the parity (2 possibilities). For the vending machine it is the total, capped at 15 (4 possibilities). If the answer can take infinitely many different values that all matter, no finite automaton can do the job. This one question is the key to designing automata, and it is also the key to proving that some languages are beyond them.
The Language of an Automaton
The language accepted (recognised) by a finite automaton M, written L(M), is the set of all strings M accepts. For Example 1, L(M) = {w ∈ {0,1}* : |w|1 is odd}.
Two automata are equivalent if they accept the same language, even if they look completely different.
A language is called regular if some finite automaton accepts it.
Regular languages are the bottom level (Type 3) of the Chomsky hierarchy from Introduction to Theory of Computation. Later chapters will show that regular expressions and regular grammars describe exactly the same class.
Types of Finite Automata
Finite automata come in two families: acceptors that only answer yes/no, and transducers that produce output.
Type | Family | What is special | Chapter |
|---|---|---|---|
DFA (Deterministic FA) | Acceptor | Exactly one next state for every (state, symbol) | Deterministic Finite Automata (DFA) |
NFA (Nondeterministic FA) | Acceptor | Zero, one or several next states; accepts if some choice leads to a final state | Nondeterministic Finite Automata (NFA) |
ε-NFA | Acceptor | NFA that may also change state without reading a symbol | Epsilon-NFA & Epsilon-Closure |
Moore machine | Transducer | Output depends on the current state only | Moore & Mealy Machines |
Mealy machine | Transducer | Output depends on the current state and the input symbol | Moore & Mealy Machines |
A remarkable fact, proved in NFA to DFA Conversion (Subset Construction): DFA, NFA and ε-NFA all accept exactly the same class of languages, the regular languages. Nondeterminism makes machines easier to design and sometimes much smaller, but not more powerful. Even two-way finite automata, whose head may move left as well as right, accept only regular languages.
What Finite Automata Cannot Do
Consider L = {anbn : n ≥ 0} = {ε, ab, aabb, aaabbb, ...}. Suppose someone claims a finite automaton with k states accepts L. Feed it a, aa, aaa, ..., ak+1. That is k + 1 different inputs but only k states, so by the pigeonhole principle two of them, say ai and aj with i ≠ j, end in the same state. From then on the machine behaves identically for both. Now append bi: aibi must be accepted and ajbi must be rejected, but the machine is in the same state at the end of both. Contradiction. So no finite automaton accepts anbn.
The same reasoning shows finite automata cannot:
Check that brackets are balanced to arbitrary depth.
Recognise palindromes or strings of the form ww.
Compare two unbounded counts (equal numbers of a's and b's).
Write output to the tape or re-read earlier input to do calculations.
All of these need unbounded memory. The rigorous tool for such proofs is Pumping Lemma for Regular Languages, and the machines that fix the problem are the pushdown automaton and the Turing machine.
Do not over-learn this lesson, though: finite automata can count modulo a fixed number (odd/even, divisible by 3) and up to a fixed bound (at least 2, at most 5), because only finitely many cases matter.
Where Finite Automata Are Used
Application | How an FA is used |
|---|---|
Lexical analysis in compilers | Tools like Lex/Flex turn token patterns (identifiers, numbers, keywords) into one DFA that scans the source code. |
Text search, grep, regex | Patterns are compiled into automata (or simulated as NFAs) to find matches in one pass. |
Digital circuits | Sequential circuits such as counters, traffic-light and vending-machine controllers are designed as finite-state machines. |
Network protocols | TCP connection states, USB and Bluetooth handshakes are specified as state machines. |
Input validation | Checking formats like a PIN code or a date with a pattern. |
Games and UI | Character behaviour (idle, walking, jumping) and screen flows are often coded as state machines. |
Why are they so popular? Because they are fast and predictable: a DFA spends constant time per input symbol and uses a fixed amount of memory, whatever the input length.
Common Mistakes
Thinking the machine can look ahead or go back. A (one-way) FA sees each symbol once, left to right, and must decide its next state immediately.
Accepting as soon as a final state is visited. Acceptance is decided only after the whole input is read. Passing through a final state in the middle means nothing.
Forgetting ε. The empty string is accepted if and only if the start state is final.
Believing FAs cannot count at all. They can count modulo n and up to a fixed bound; they cannot keep an unbounded count.
Thinking the final-state set must be non-empty. F may be empty; then the machine accepts the empty language ∅.
Confusing "nondeterministic" with "more powerful". NFAs and DFAs accept the same class of languages.
Interview and Exam Questions
What is a finite automaton?
A mathematical machine with finitely many states, a start state, a set of final states and transition rules. It reads the input left to right one symbol at a time and accepts if it ends in a final state. Formally it is a 5-tuple (Q, Σ, δ, q0, F).
What does a state of a finite automaton represent?
A summary of everything about the input read so far that matters for the final decision. Since there are finitely many states, only a bounded amount of information can be remembered.
When does a finite automaton accept ε?
Exactly when its start state is also a final state, because reading ε makes no moves.
Can a finite automaton accept {anbn : n ≥ 0}? Why or why not?
No. With k states, two of the prefixes a0, ..., ak must reach the same state (pigeonhole). Appending the right number of b's then forces the machine to treat an accepted string and a rejected string the same way.
What is the difference between an acceptor and a transducer?
An acceptor (DFA, NFA, ε-NFA) only says accept or reject. A transducer (Moore or Mealy machine) produces an output string while reading the input.
What is a dead (trap) state?
A non-final state from which every transition leads back to itself. Once entered, the input can never be accepted.
Why is a DFA well suited for lexical analysis?
It processes each character in constant time with fixed memory, so scanning a source file takes time proportional to its length, and token patterns are regular languages.
Summary
A finite automaton reads its input once, left to right, with only a finite set of states as memory, and accepts if it ends in a final state.
It is described by a 5-tuple (Q, Σ, δ, q0, F) and drawn as a transition diagram or a transition table (→ start, * final).
Each state is a summary of the past: design by asking what must be remembered.
The set of strings accepted is the machine's language; languages accepted by FAs are called regular.
Acceptors: DFA, NFA, ε-NFA (all equally powerful). Transducers: Moore and Mealy machines.
Finite automata cannot handle languages that need unbounded memory, such as anbn, but they can count modulo n or up to a fixed bound.
Next, Deterministic Finite Automata (DFA) gives the precise definition and the extended transition function.