Difficulty: Intermediate | Prerequisites: Cryptography and RSA notes, basic set theory
Models of computation are abstract frameworks that formalise what it means for a machine to "compute" something. This topic moves from the simplest model (finite automata, which recognise patterns in strings) through regular expressions (a compact notation for the same patterns) to Turing machines (which can simulate any algorithm a real computer runs). Understanding these models is essential because they define the boundaries of what is computable, and those boundaries shape every area of computer science from compiler design to artificial intelligence.
Finite automata (DFAs and NFAs) are simple machines that read input one symbol at a time and either accept or reject a string. Regular expressions describe the exact same set of languages in a compact text notation. Turing machines are the most powerful model, capable of computing anything a real computer can, and they define the theoretical ceiling of computation.
Finite Automaton (FA)
An abstract machine with a finite number of states that reads input symbols one at a time and transitions between states according to fixed rules.
Think of it as a flowchart that reads a string character by character and ends up at either an "accept" or "reject" state.
Deterministic Finite Automaton (DFA)
A finite automaton where, for every state and input symbol, there is exactly one transition to a next state. No ambiguity, no choices.
In simple terms, at every step the machine knows exactly where to go next.
Nondeterministic Finite Automaton (NFA)
A finite automaton where a state may have zero, one, or multiple transitions for a given input symbol, and may also have lambda (epsilon) transitions that happen without consuming any input.
Think of it as a machine that can "guess" the right path, or equivalently explore all paths at once.
5-Tuple (DFA definition)
A DFA is formally defined as M = (Q, Sigma, delta, q_0, F), where Q is the set of states, Sigma is the input alphabet, delta is the transition function, q_0 is the start state, and F is the set of accept states.
Transition Function (delta)
The rule that determines, given a current state and an input symbol, which state the machine moves to next. For a DFA: delta maps Q x Sigma to Q.
Accept State (Final State)
A state in which, if the machine finishes reading all input, the string is accepted (recognised as part of the language).
Lambda Transition (Epsilon Transition)
A transition in an NFA that occurs without reading any input symbol. Allows the machine to change state "for free."
Regular Expression (Regex)
A compact textual notation for describing a set of strings (a language). Built from concatenation, union (the | operator), and the Kleene star (zero or more repetitions).
In simple terms, it is a pattern that matches strings, like the search patterns used in text editors and programming languages.
Kleene Star (*)
An operator meaning "zero or more repetitions" of the preceding element. For example, a* matches the empty string, a, aa, aaa, and so on.
Turing Machine (TM)
The most powerful standard model of computation. It has an infinite tape (memory), a read/write head, and a set of states with transition rules. It can simulate any algorithm.
Think of it as a theoretical computer with unlimited memory and a simple instruction set.
7-Tuple (Turing Machine definition)
A Turing Machine is formally defined as (Q, Sigma, Gamma, delta, q_0, q_a, q_r), where Q is the set of states, Sigma is the input alphabet, Gamma is the tape alphabet, delta is the transition function, q_0 is the start state, q_a is the accept state, and q_r is the reject state.
Language (formal)
A set of strings over some alphabet. A machine "recognises" a language if it accepts exactly the strings in that set and rejects all others.
A DFA is the simplest computational model. It reads an input string one symbol at a time, transitions between a finite number of states, and accepts or rejects the string when the input is exhausted.
Formal definition
M = (Q, Sigma, delta, q_0, F)
Q: finite set of states
Sigma: finite input alphabet (the set of symbols the machine can read)
delta: transition function, delta: Q x Sigma -> Q (exactly one next state for each state-symbol pair)
q_0: the start state (must be in Q)
F: set of accept states (a subset of Q)
How it processes input
Begin in q_0
Read the first symbol, follow the transition to the next state
Read the next symbol, follow the transition again
Continue until all symbols are consumed
If the final state is in F, accept; otherwise reject
Worked example
Alphabet: {a, b}
States: {q_0, q_1, q_2}
Transitions: delta(q_0, a) = q_1, delta(q_1, b) = q_2
Accept state: {q_2}
The string "ab" is accepted: q_0 reads a, moves to q_1; q_1 reads b, moves to q_2 (an accept state)
Key property
Deterministic means there is never a choice: given a state and a symbol, the next state is uniquely determined
Every DFA has exactly one computation path for any input string
An NFA relaxes the rules of a DFA. A state may have multiple transitions for the same input symbol, or none at all, and it may have lambda (epsilon) transitions that move between states without consuming any input.
Key differences from a DFA
Multiple transitions from one state on the same symbol are allowed
Lambda transitions (free moves between states) are allowed
A string is accepted if there exists at least one computation path that ends in an accept state
Equivalence to DFAs
Every NFA can be converted to an equivalent DFA (the subset construction algorithm)
Both recognise exactly the same class of languages: the regular languages
NFAs are often easier to design, but may have exponentially more states when converted to a DFA
Why NFAs matter
They are a convenient design tool: build an NFA first, then convert if you need a DFA
The proof that regular expressions and finite automata describe the same languages goes through NFAs
Regular expressions are a textual notation for describing sets of strings. They are equivalent in power to finite automata: every regular expression describes a regular language, and every regular language can be described by a regular expression.
Building blocks
Concatenation: ab means "a followed by b"
Union (alternation): a | b means "a or b"
Kleene star: a* means "zero or more a's"
These three operations, combined with parentheses for grouping, are sufficient to describe all regular languages
Worked example from the source
The regex (aa)*(bb)*b describes strings with an even number of a's (including zero) followed by an odd number of b's
(aa)* matches: empty string, aa, aaaa, aaaaaa, ...
(bb)*b matches: b, bbb, bbbbb, ...
Combined: b, aab, aabbb, aaaab, and so on
Connection to automata
For any regular expression, you can construct an NFA that accepts exactly the strings it describes
For any DFA, you can extract a regular expression describing its language
This equivalence is a central theorem in the theory of computation
The Turing machine is the most powerful standard model of computation. It can simulate any algorithm that a modern computer can execute. It was proposed by Alan Turing in 1936 as a mathematical model for the concept of an "effective procedure."
Formal definition
A 7-tuple: (Q, Sigma, Gamma, delta, q_0, q_a, q_r)
Q: finite set of states
Sigma: input alphabet (symbols that appear on the tape initially)
Gamma: tape alphabet (includes Sigma plus a blank symbol and possibly others)
delta: transition function, delta: Q x Gamma -> Q x Gamma x {L, R} (given a state and the symbol under the head, write a new symbol, move the head left or right, and enter a new state)
q_0: start state
q_a: accept state (machine halts and accepts)
q_r: reject state (machine halts and rejects)
How it works
The machine has an infinite tape divided into cells, each holding one symbol
A read/write head sits on one cell at a time
At each step, the machine reads the current symbol, consults delta, writes a symbol, moves left or right, and transitions to a new state
Computation ends when the machine enters q_a or q_r
A Turing machine may also loop forever (never halt), which is neither acceptance nor rejection
Why it matters
The Church-Turing thesis states that any function computable by an algorithm can be computed by a Turing machine
Problems that no Turing machine can solve (like the halting problem) are genuinely uncomputable, no matter what technology you use
Turing machines are strictly more powerful than finite automata: they can recognise languages that no DFA or NFA can
DFA formal definition: M = (Q, Sigma, delta, q_0, F)
DFA transition function type: delta: Q x Sigma -> Q
NFA transition function type: delta: Q x (Sigma union {lambda}) -> P(Q), where P(Q) is the power set of Q
Turing Machine formal definition: M = (Q, Sigma, Gamma, delta, q_0, q_a, q_r)
TM transition function type: delta: Q x Gamma -> Q x Gamma x {L, R}
Kleene star: L* = {empty string} union L union LL union LLL union ...
Regular expression operators: concatenation, union (|), Kleene star (*)
Finite automata power the pattern-matching engines inside text editors, compilers, and network intrusion detection systems. Every time you use a search-and-replace with a regular expression in your code editor, a DFA is doing the matching under the hood.
Turing machines, while theoretical, define what is and is not computable. This has practical consequences: the halting problem proves that no general-purpose debugger can detect all infinite loops, which is why testing and formal verification remain active areas of software engineering.
Students often think an NFA is more powerful than a DFA (can recognise more languages). It cannot. NFAs and DFAs recognise exactly the same class of languages (the regular languages). NFAs are just more convenient to design.
Students sometimes confuse the input alphabet (Sigma) with the tape alphabet (Gamma) in a Turing machine. Sigma is what appears on the tape initially; Gamma includes Sigma plus the blank symbol and any auxiliary symbols the machine uses.
Students often assume that if a Turing machine does not accept a string, it rejects it. This is not always true. A Turing machine can loop forever, in which case it neither accepts nor rejects.
Students sometimes think regular expressions in programming languages (Python, JavaScript) have the same power as formal regular expressions. They do not. Programming regex engines include features like backreferences that go beyond regular languages.
Know the 5-tuple definition of a DFA cold. Expect to be given states, an alphabet, and transitions, then asked whether a specific string is accepted
Be ready to trace an NFA computation path, showing that at least one path leads to an accept state
Expect to convert a simple regular expression to an NFA, or describe the language a given regex matches
Know the 7-tuple definition of a Turing machine and be able to trace a short computation on tape
Understand the hierarchy: DFA = NFA = regular expressions (in power) < Turing machines
True or False: A DFA can have multiple transitions from one state on the same input symbol. (False, that is an NFA property)
Fill in the blank: The set of languages recognised by DFAs, NFAs, and regular expressions are collectively called the ______ languages. (regular)
True or False: A Turing machine has a finite tape. (False, the tape is infinite)
Fill in the blank: In a Turing machine, the two halting states are the ______ state and the ______ state. (accept, reject)
True or False: Every NFA can be converted into an equivalent DFA. (True)
Q: Given a DFA with states {q_0, q_1, q_2}, alphabet {a, b}, transitions delta(q_0, a) = q_1 and delta(q_1, b) = q_2, and accept state {q_2}, does the DFA accept the string "ab"?
A: Yes. Start in q_0, read a, move to q_1. Read b, move to q_2. q_2 is an accept state, so "ab" is accepted.
*Q: What language does the regular expression (aa)*(bb)b describe?
A: Strings consisting of an even number of a's (possibly zero) followed by an odd number of b's (at least one).
Q: What is the key difference between a DFA and an NFA?
A: A DFA has exactly one transition for each state-symbol pair, so the computation path is unique. An NFA can have zero, one, or multiple transitions for a given state-symbol pair, and can also have lambda transitions.
Q: Name the seven components of a Turing machine's formal definition.
A: Q (states), Sigma (input alphabet), Gamma (tape alphabet), delta (transition function), q_0 (start state), q_a (accept state), q_r (reject state).
Q: Can a Turing machine loop forever without accepting or rejecting?
A: Yes. A Turing machine may enter an infinite loop and never reach q_a or q_r. This is distinct from rejection.
This connects to Cryptography because the security of systems like RSA depends on certain problems being computationally hard, a concept that only makes sense once you have a formal model of computation to define "hard." Regular expressions connect to compiler design (lexical analysis) and text processing. The Church-Turing thesis connects to the philosophy of mathematics and the limits of artificial intelligence.
finite automata, DFA, NFA, deterministic finite automaton, nondeterministic finite automaton, regular expression, regex, Kleene star, transition function, accept state, reject state, start state, 5-tuple, 7-tuple, Turing machine, TM, tape alphabet, input alphabet, lambda transition, epsilon transition, Church-Turing thesis, halting problem, regular language, computational model, theory of computation, CS 101, foundations of computer science