Jeff Erikson - Models of Computation
Jeff Erikson - Models of Computation
Jeff Erikson - Models of Computation
Jeff Erickson
http://jeffe.cs.illinois.edu/teaching/algorithms/ • http://algorithms.wtf/
© Copyright 2014–2017 Jeff Erickson. Last update December 28, 2018.
This work may be freely copied and distributed in any medium.
It may not be sold for more than the actual cost of reproduction, storage, or transmittal.
This work is available under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
For license details, see http://creativecommons.org/licenses/by-nc-sa/4.0/.
For the most recent edition, see http://jeffe.cs.illinois.edu/teaching/algorithms/.
I’m writing a book.
I’ve got the page numbers done,
so now I just have to fill in the rest.
— Stephen Wright
Caveat Lector!
These notes are best viewed as an unfinished first draft. You should assume the notes
contain several major errors, in addition to the usual unending supply of typos, fencepost errors,
off-by-one errors, and brain farts. Before Fall 2014, I had not taught this material in more than
two decades. Moreover, the course itself is still very new—Lenny Pitt and I developed the
course and offered the first pilot in Spring 2014 (with Lenny presenting the formal language
material)—so even the choice of which material to emphasize, sketch, or exclude is still very
much in flux.
I would sincerely appreciate feedback of any kind, especially bug reports.
Thanks, and enjoy!
— Jeff
ii
Contents
1 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Regular Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Finite-State Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4 Nondeterministic Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5 Context-Free Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6 Turing Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
7 Undecidability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
8 Universal Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
9 Nondeterministic Turing Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
iii
Models of Computation Lecture 1: Strings [Sp’18]
Vario, inquit [Epicurus], ordine ac positione conveniunt atomi sicut literae, quae cum sint paucae,
varie tamen collocatae innumerabilia verba conficiunt.
[Atoms, like letters, says Epicurus, come together in various orders and positions; there are few of
them, but different combinations produce countless words.]
— Gottfried Leibniz, Dissertatio de Arte Combinatoria (1666)
THOMAS GODFREY, a self-taught mathematician, great in his way, and afterward inventor of what is
now called Hadley’s Quadrant. But he knew little out of his way, and was not a pleasing companion;
as, like most great mathematicians I have met with, he expected universal precision in everything
said, or was forever denying or distinguishing upon trifles, to the disturbance of all conversation.
He soon left us.
— Benjamin Franklin, Memoirs, Part 1 (1771)
describing one of the founding members of the Junto
If indeed, as Hilbert asserted, mathematics is a meaningless game played with meaningless marks
on paper, the only mathematical experience to which we can refer is the making of marks on paper.
— Eric Temple Bell, The Queen of the Sciences (1931)
1 Strings
Throughout this course, we will discuss dozens of algorithms and computational models that
manipulate sequences: one-dimensional arrays, linked lists, blocks of text, walks in graphs,
sequences of executed instructions, and so on. Ultimately the input and output of any algorithm
must be representable as a finite string of symbols—the raw contents of some contiguous portion
of the computer’s memory. Reasoning about computation requires reasoning about strings.
This note lists several formal definitions and formal induction proofs related to strings. These
definitions and proofs are intentionally much more detailed than normally used in practice—most
people’s intuition about strings is fairly accurate—but the extra precision is necessary for any
sort of formal proof. It may be helpful to think of this material as part of the “assembly language”
of theoretical computer science. We normally think about computation at a much higher level
of abstraction, but ultimately every argument must “compile” down to these (and similar)
definitions.
But the actual definitions and theorems are not the point. The point of playing with this
material is to get some experience working with formal/mechanical definitions and proofs,
especially inductive definitions and recursive proofs. Or should I say recursive definitions and
inductive proofs? Whatever, they’re
induct the same thing. Strings are a particularly simple and
convenient playground for recurs ion; we’ll see many more examples throughout the course.
When you read this note, don’t just look at the content of the definitions and proofs; pay close
attention to their structure and the process for creating them.
1.1 Strings
Fix an arbitrary finite set Σ called the alphabet; the individual elements of Σ are called symbols
or characters. As a notational convention, I will always use lower-case letters near the start of
the English alphabet (a, b, c, . . . ) as symbol variables, and never as explicit symbols. For explicit
symbols, I will always use fixed-width upper-case letters (A, B, C, . . . ), digits (0, 1, 2, . . . ),
1
Models of Computation Lecture 1: Strings [Sp’18]
or other symbols (, $, #, •, . . . ) that are clearly distinguishable from variables. For further
emphasis, I will almost always typeset explicit symbols in RED.
A string (or word) over Σ is a finite sequence of zero or more symbols from Σ. Formally, a
string w over Σ is defined recursively as either
We normally write either a · x or simply ax to denote the ordered pair (a, x). Similarly, we
normally write explicit strings as sequences of symbols instead of nested ordered pairs; for
example, STRING is convenient shorthand for the formal expression (S, (T, (R, (I, (N, (G, ")))))).
As a notational convention, I will always use lower-case letters near the end of the English
alphabet (. . . , w, x, y, z) for string variables, and SHOUTY RED MONOSPACED TEXT to typeset
explicit (non-empty) strings.
The set of all strings over Σ is denoted Σ∗ (pronounced “sigma star”). It is very important to
remember that every element of Σ∗ is a finite string, although Σ∗ itself is an infinite set containing
strings of every possible finite length.
For example, the string FIFTEEN has length 7, the string SEVEN has length 5, and the string 5
has length 1. Although they are formally different objects, we do not normally distinguish
between symbols and strings of length 1.
The concatenation of two strings x and y, denoted either x • y or simply x y, is the
unique string containing the characters of x in order, followed by the characters in y in
order. For example, the string NOWHERE is the concatenation of the strings NOW and HERE;
that is, NOW • HERE = NOWHERE. (On the other hand, HERE • NOW = HERENOW.) Formally,
concatenation is defined recusively as follows:
¨
z if w = ",
w • z :=
a · (x • z) if w = ax.
(Here I’m using a larger dot • to formally distinguish the operator that concatenates two arbitrary
strings from from the syntactic sugar · that builds a string from a single character and a string.)
When we describe the concatenation of more than two strings, we normally omit all dots
and parentheses, writing wxyz instead of (w • (x • y)) • z, for example. This simplification is
justified by the fact (which we will prove shortly) that the function • is associative.
2
Models of Computation Lecture 1: Strings [Sp’18]
• The case structure of the proof should mirror the case structure of the recursive defin-
ition. For example, if you are proving something about all strings, your proof should have
two cases: Either w = ", or w = ax for some symbol a and string x.
• The inductive hypothesis should be as strong as possible. The (strong) inductive hypoth-
esis for statements about natural numbers is always “Assume there is no counterexample k
such that k < n.” I recommend adopting a similar inductive hypothesis for strings: “Assume
there is no counterexample x such that |x| < |w|.” Then for the case w = a x, we have
|x| = |w| − 1 < |w| by definition of |w|, so the inductive hypothesis applies to x.
Thus, string-induction proofs have the following boilerplate structure. Suppose we want to prove
that every string is perfectly cromulent, whatever that means. The white boxes hide additional
proof details that, among other things, depend on the precise definition of “perfectly cromulent”.
• Suppose w = " .
Here are three canonical examples of this proof structure. When developing proofs in this
style, I strongly recommend first mindlessly writing the green text (the boilerplate) with lots of
space for each case, then filling in the red text (the actual theorem and the induction hypothesis),
and only then starting to actually think.
Many students are confused (or at least bored and distracted) by the fact that we are proving
mind-bogglingly obvious facts. If you’re one of these students, try to remember that the lemmas
themselves are not the point. Pay close attention to the structure of the proofs. Notice how each
proof follows the boilerplate described above. Notice how every sentence of the proof follows
mechanically from earlier sentences, definitions, and the rules of standard logic and arithmetic.
Lemma 1.1. Adding nothing does nothing: For every string w, we have w • " = w.
3
Models of Computation Lecture 1: Strings [Sp’18]
Proof: Let w be an arbitrary string. Assume that x • " = x for every string x such that |x| < |w|.
There are two cases to consider:
• Suppose w = ".
Lemma 1.2. Concatenation adds length: |w • x| = |w| + |x| for all strings w and x.
Proof: Let w and x be arbitrary strings. Assume that | y • x| = | y| + |x| for every string y such
that | y| < |w|. (Notice that we are using induction only on w, not on x.) There are two cases to
consider:
• Suppose w = ".
|w • x| = |a y • x| because w = a y
= |a · ( y • x)| by definition of •
= 1 + | y • x| by definition of | · |
= 1 + | y| + |x| by the inductive hypothesis
= |a y| + |x| by definition of | · |
= |w| + |x| because w = a y
Proof: Let w, x, and y be arbitrary strings. Assume that (z • x) • y = z • (x • y) for every string
z such that |z| < |w|. (Again, we are using induction only on w.) There are two cases to consider.
4
Models of Computation Lecture 1: Strings [Sp’18]
• Suppose w = ".
(w • x) • y = (" • x) • y because w = "
=x•y by definition of •
= " • (x • y) by definition of •
= w • (x • y) because w = "
Proof: Let w, x, and y be arbitrary strings. Assume that (z • x 0 ) • y 0 = z • (x 0 • y 0 ) for all strings
x 0 , y 0 , and z such that |z| < |w|. (We need a stronger induction hypothesis here than in the
previous proofs!) There are three cases to consider.
• Suppose w = ".
(w • x) • y = (" • x) • y because w = "
=x•y by definition of •
= " • (x • y) by definition of •
= w • (x • y) because w = "
5
Models of Computation Lecture 1: Strings [Sp’18]
1The same bracket notation is also used for bibliographic references, instead of the traditional footnote/endnote
superscripts, for exactly the same reasons.
2A typewriter is an obsolete mechanical device loosely resembling a computer keyboard. Pressing a key on a
typewriter moves a lever (called a “typebar”) that strikes a cloth ribbon full of ink against a piece of paper, leaving the
image of a single character. Many historians believe that the ordering of letters on modern keyboards (QWERTYUIOP)
evolved in the late 1800s, reaching its modern form on the 1874 Sholes & Glidden Type-WriterTM , in part to separate
many common letter pairs, to prevent typebars from jamming against each other; this is also why the keys on most
modern keyboards are arranged in a slanted grid. (The common folk theory that the ordering was deliberately
intended to slow down typists doesn’t withstand careful scrutiny.) A more recent theory suggests that the ordering
was influenced by telegraph3 operators, who found older alphabetic arrangements confusing, in part because of
ambiguities in American Morse Code.
6
Models of Computation Lecture 1: Strings [Sp’18]
A proper substring of w is any substring other than w itself. For example, LAUGH is a proper
substring of SLAUGHTER. Whenever y is a (proper) substring of w, we also call w a (proper)
superstring of y.
A prefix of w[1 .. n] is any substring of the form w[1 .. j]. Equivalently, a string p is a prefix
of another string w if and only if there is a string x such that px = w. A proper prefix of w is
any prefix except w itself. For example, DIE is a proper prefix of DIET.
Similarly, a suffix of w[1 .. n] is any substring of the form w[i .. n]. Equivalently, a string s is a
suffix of a string w if and only if there is a string x such that xs = w. A proper suffix of w is
any suffix except w itself. For example, YES is a proper suffix of EYES, and HE is both a proper
prefix and a proper suffix of HEADACHE.
A subsequence of a string w is a string obtained by deleting zero or more symbols from
anywhere in w. More formally, z is a subsequence of w if and only if
• z = ", or
• w = a x for some symbol a and some string x such that z is a subsequence of x.
• w = a x and z = a y for some symbol a and some strings x and y, and y is a subsequence
of x.
Exercises
Most of the following exercises ask for proofs of various claims about strings. Here “prove” means
give a complete, self-contained, formal proof by inductive definition-chasing, using the boilerplate
structure recommended in Section 1.3. Feel free to use Lemmas 1.1, 1.2, and 1.3 without proof,
but don’t assume any other facts about strings that you have not actually proved. (Some later
exercises rely on results proved in earlier exercises.) Do not appeal to intuition, and do not use
the words “obvious” or “clearly” or “just”. Most of these claims are in fact obvious; the real
exercise is understanding and formally expressing why they’re obvious.
7
Models of Computation Lecture 1: Strings [Sp’18]
Note to instructors: Do not assign any of these problems before solving them
yourself, especially on exams. It’s very easy to underestimate the difficulty of these
problems, or at least the lengths of their solutions, which for exams is a reasonable proxy
for difficulty. Also, several later exercises rely implicitly on identities like #(a, x • y) =
#(a, x) + #(a, y) that are only proved in earlier exercises. It’s unfair to assign these problems
to students without telling them which earlier results they can use.
1. Let w be an arbitrary string, and let n = |w|. Prove each of the following statements.
2. Prove the following useful identities for all strings w, x, y, and z directly from the definition
of •, without referring to the length of any string.
3. Prove the following useful fact about substrings. An arbitrary string x is a substring of
another arbitrary string w = u • v if and only if at least one of the following conditions
holds:
• x is a substring of u.
• x is a substring of v.
• x = yz where y is a suffix of u and z is a prefix of v.
4. Let w be an arbitrary string, and let n = |w|. Prove the following statements for all indices
1 ≤ i ≤ j ≤ k ≤ n.
Recursive Functions
5. For any symbol a and any string w, let #(a, w ) denote the number of occurrences of a
in w. For example, #(A, BANANA) = 3 and #(X, FLIBBERTIGIBBET) = 0.
8
Models of Computation Lecture 1: Strings [Sp’18]
(b) Prove that #(a, x y) = #(a, x) + #(a, y) for every symbol a and all strings x and y.
Your proof must rely on both your answer to part (a) and the formal recursive
definition of string concatenation.
(c) Prove the following identity for all alphabets Σ and all strings w ∈ Σ∗ :
X
|w| = #(a, w)
a∈Σ
7. For any string w and any non-negative integer n, let w n denote the string obtained by
concatenating n copies of w; more formally, we define
(
" if n = 0
wn :=
n−1
w•w otherwise
(a) Prove that wm • wn = wm+n for every string w and all non-negative integers n and m.
(b) Prove that #(a, wn ) = n · #(a, w) for every string w, every symbol a, and every
non-negative integer n. (See Exercise 5.)
(c) Prove that (wR )n = (wn )R for every string w and every non-negative integer n.
(d) Prove that for all strings x and y that if x • y = y • x, then x = wm and y = wn for
some string w and some non-negative integers m and n. [Hint: Careful with "!]
9
Models of Computation Lecture 1: Strings [Sp’18]
9. For any string w ∈ {0, 1, 2}∗ , let w + denote the string obtained from w by replacing each
symbol a in w by the symbol corresponding to (a + 1) mod 3. for example, 0102101+ =
1210212. This function can be defined more formally as follows:
" if w = "
1· x +
if w = 0 x
w+ :=
2· x +
if w = 1 x
0· x +
if w = 2 x
(a) Prove that |w| = |w+ | for every string w ∈ {0, 1, 2}∗ .
(b) Prove that (x • y)+ = x + • y + for all strings x, y ∈ {0, 1, 2}∗ .
(c) Prove that #(1, w+ ) = #(0, w) for every string w ∈ {0, 1, 2}∗ .
(d) Prove that (w+ )R = (wR )+ for every string w ∈ {0, 1, 2}∗ .
10. For any string w ∈ {0, 1}∗ , let swap(w) denote the string obtained from w by swapping the
first and second symbols, the third and fourth symbols, and so on. For example:
swap(101) = 011
swap(100111) = 011011
swap(10 11 00 01 10 1) = 01 11 00 10 01 1.
The swap function can be formally defined as follows:
" if w = "
swap(w) := w if w = 0 or w = 1
ba • swap(x) if w = ab x for some a, b ∈ {0, 1} and x ∈ {0, 1}∗
11. For any string w ∈ {0, 1}∗ , let sort(w) denote the string obtained by sorting the characters
in w. For example, sort(010101) = 000111. The sort function can be defined recursively
as follows:
" if w = "
sort(w) := 0 · sort(x) if w = 0 x
sort(x) • 1 if w = 1 x
10
Models of Computation Lecture 1: Strings [Sp’18]
(a) Prove that merge(x, y) ∈ 0∗ 1∗ for all strings x, y ∈ 0∗ 1∗ . (The regular expression
0∗ 1∗ is shorthand for the language {0a 1 b | a, b ≥ 0}.)
(b) Prove that sort(x • y) = merge(sort(x), sort( y)) for all strings x, y ∈ {0, 1}∗ . (The
sort function is defined in the previous exercise.)
11
Models of Computation Lecture 1: Strings [Sp’18]
For example, faro(0011, 0101) = 00011011. (A "faro shuffle" splits a deck of cards into
two equal piles and then perfectly interleaves them.)
(a) Prove that |faro(x, y)| = |x| + | y| for all strings x and y.
(b) Prove that faro(w, w) = stutter(w) for every string w.
(c) Prove that faro(odds(w), evens(w)) = w for every string w.
16. For any string w, let declutter(w) denote the string obtained from w by deleting any symbol
that equals its immediate successor. For example, declutter(MISSISSIPPI) = MISISIPI,
and declutter(ABBCCCAAAACCCBBA) = ABCACBA.
12
Models of Computation Lecture 1: Strings [Sp’18]
20. The binary value of any string w ∈ {0, 1}∗ is the integer whose binary representation
(possibly with leading 0s) is w. The value function can be defined recursively as follows:
0 if w = "
value(w) := 2 · value(x) if w = x • 0
2 · value(x) + 1 if w = x • 1
(a) Prove that value(w) + value(wc ) = 2|w| − 1 for every string w ∈ {0, 1}∗ .
(b) Prove that value(x • y) = value(x) · 2| y| + value( y) for all strings x, y ∈ {0, 1}∗ .
? (c) Prove that value(x) is divisible by 3 if and only if value(x R ) is divisible by 3.
20. Recursively define a set L of strings over the alphabet {0, 1} as follows:
21. Recursively define a set L of strings over the alphabet {0, 1} as follows:
13
Models of Computation Lecture 1: Strings [Sp’18]
(c) Prove by induction that L contains every string with the same number of 0s and 1s.
22. Recursively define a set L of strings over the alphabet {0, 1} as follows:
23. Recursively define a set L of strings over the alphabet {0, 1, 2} as follows:
14
Models of Computation Lecture 1: Strings [Sp’18]
25. A string w ∈ Σ∗ is called a shuffle of two strings x, y ∈ Σ∗ if at least one of the following
recursive conditions is satisfied:
• w = x = y = ".
• w = aw0 and x = a x 0 and w0 is a shuffle of x 0 and y, for some a ∈ Σ and some
w0 , x 0 ∈ Σ∗ .
• w = aw0 and y = a y 0 and w0 is a shuffle of x and y 0 , for some a ∈ Σ and some
w0 , y 0 ∈ Σ∗ .
For example, the string BANANANANASA is a shuffle of the strings BANANA and ANANAS.
26. For any positive integer n, the Fibonacci string Fn is defined recursively as follows:
0
if n = 1,
Fn = 1 if n = 2,
F
n−2 • Fn−1 otherwise.
(a) Prove that for every integer n ≥ 2, the string Fn can also be obtained from Fn−1 by
replacing every occurrence of 0 with 1 and replacing every occurrence of 1 with 01.
More formally, prove that Fn = Finc(Fn−1 ), where
" if w = "
Finc(w) = 1 · Finc(x) if w = 0 x
01 • Finc(x) if w = 1 x
15
Models of Computation Lecture 1: Strings [Sp’18]
? 27. Prove that the following three properties of strings are in fact identical.
? 28. A string w ∈ {0, 1}∗ is equitable if it has an equal number of 0s and 1s.
(a) Prove that a string w is equitable if and only if it satisfies one of the following
conditions:
• w = ",
• w = 0 x 1 for some equitable string x,
• w = 1 x 0 for some equitable string x, or
• w = x y for some equitable strings x and y.
16
Models of Computation Lecture 1: Strings [Sp’18]
(b) Prove that a string w is equitable if and only if it satisfies one of the following
conditions:
• w = ",
• w = x 01 y for some strings x and y such that x y is equitable, or
• w = x 10 y for some strings x and y such that x y is equitable.
In the last two cases, the individual strings x and y are not necessarily equitable.
(c) Prove that a string w is equitable if and only if it satisfies one of the following
conditions:
• w = ",
• w = x y for some balanced string x and some equitable string y, or
• w = x R y for some for some balanced string x and some equitable string y.
(See the previous exercise for the definition of “balanced”.)
17
Models of Computation Lecture 2: Regular Languages [Sp’18]
But the Lord came down to see the city and the tower the people were building. The Lord
said, “If as one people speaking the same language they have begun to do this, then nothing
they plan to do will be impossible for them. Come, let us go down and confuse their language
so they will not understand each other.”
— Genesis 11:6–7 (New International Version)
Some people, when confronted with a problem, think "I know, I’ll use regular expressions."
Now they have two problems.
— Jamie Zawinski, alt.religion.emacs (August 12, 1997)
2 Regular Languages
2.1 Languages
A formal language (or just a language) is a set of strings over some finite alphabet Σ, or
equivalently, an arbitrary subset of Σ∗ . For example, each of the following sets is a language:
As a notational convention, I will always use italic upper-case letters (usually L, but also A, B, C,
and so on) to represent languages.
Formal languages are not “languages” in the same sense that English, Klingon, and Python
are “languages”. Strings in a formal language do not necessarily carry any “meaning”, nor
are they necessarily assembled into larger units (“sentences” or “paragraphs” or “packages”)
according to some “grammar”.
1The empty set symbol ∅ was introduced in 1939 by André Weil, as a member of the pseudonymous mathematical
collective Nicholai Bourbaki. The symbol derives from the Norwegian letter Ø, which pronounced like a German ö or
a sound of disgust, and not from the Greek letter φ. Calling the empty set “fie” or “fee” makes the baby Jesus cry.
1
Models of Computation Lecture 2: Regular Languages [Sp’18]
It is very important to distinguish between three “empty” objects. Many beginning students
have trouble keeping these straight.
• ∅ is the empty language, which is a set containing zero strings. ∅ is not a string.
• {"} is a language containing exactly one string, which has length zero. {"} is not empty,
and it is not a string.
• " is the empty string, which is a sequence of length zero. " is not a language.
A • B := {x y | x ∈ A and y ∈ B}.
The Kleene closure or Kleene star2 of a language L, denoted L∗ , is the set of all strings obtained
by concatenating a sequence of zero or more strings from L. For example, {0, 11}∗ = {", 0, 00, 11,
000, 011, 110, 0000, 0011, 0110, 1100, 1111, 00000, 00011, 011110011011, . . .}. More
formally, L ∗ is defined recursively as the set of all strings w such that either
• w = ", or
• w = x y, for some strings x ∈ L and y ∈ L ∗ .
∅∗ = {"}∗ = {"}.
For any other language L, the Kleene closure L ∗ is infinite and contains arbitrarily long (but
finite!) strings. Equivalently, L ∗ can also be defined as the smallest superset of L that contains the
empty string " and is closed under concatenation (hence “closure”). The set of all strings Σ∗ is,
just as the notation suggests, the Kleene closure of the alphabet Σ (where each symbol is viewed
as a string of length 1).
A useful variant of the Kleene closure operator is the Kleene plus, defined as L + := L • L ∗ .
Thus, L + is the set of all strings obtained by concatenating a sequence of one or more strings
from L.
The following identities, which we state here without (easy) proofs, are useful for designing,
simplifying, and understanding languages.
2named after logician Stephen Cole Kleene, who actually pronounced his last name “clay-knee”, not “clean” or
“cleanie” or “claynuh” or “dimaggio”.
2
Models of Computation Lecture 2: Regular Languages [Sp’18]
Lemma 2.1. The following identities hold for all languages A, B, and C:
(a) A ∪ B = B ∪ A.
(b) (A ∪ B) ∪ C = A ∪ (B ∪ C).
(c) ∅ • A = A • ∅ = ∅.
(d) {"} • A = A • {"} = A.
(e) (A • B) • C = A • (B • C).
(f) A • (B ∪ C) = (A • B) ∪ (A • C).
(g) (A ∪ B) • C = (A • C) ∪ (B • C).
Lemma 2.3 (Arden’s Rule). For any languages A, B, and L such that L = A • L ∪ B, we have
A∗ • B ⊆ L. Moreover, if A does not contain the empty string, then L = A • L ∪ B if and only if
L = A∗ • B.
• L is empty;
• L contains exactly one string (which could be the empty string ");
• L is the union of two regular languages;
• L is the concatenation of two regular languages; or
• L is the Kleene closure of a regular language.
Regular languages are normally described using a compact notation called regular expres-
sions, which omit braces around one-string sets, use + to represent union instead of ∪, and
juxtapose subexpressions to represent concatenation instead of using an explicit operator •. By
convention, in the absence of parentheses, the ∗ operator has highest precedence, followed by
the (implicit) concatenation operator, followed by +.
For example, the regular expression 10∗ is shorthand for the language {1} • {0}∗ (containing
all strings consisting of a 1 followed by zero or more 0s), and not the language {10}∗ (containing
all strings of even length that start with 1 and alternate between 1 and 0). As a larger example,
the regular expression
0∗ 0 + 0∗ 1(10∗ 1 + 01∗ 0)∗ 10∗
represents the language
∗
({0}∗ • {0}) ∪ {0}∗ • {1} • ({1} • {0}∗ • {1}) ∪ ({0} • {1}∗ • {0}) • {1} • {0}∗ .
3
Models of Computation Lecture 2: Regular Languages [Sp’18]
Most of the time we do not distinguish between regular expressions and the languages they
represent, for the same reason that we do not normally distinguish between the arithmetic
expression “2+2” and the integer 4, or the symbol π and the area of the unit circle. However, we
sometimes need to refer to regular expressions themselves as strings. In those circumstances, we
write L(R) to denote the language represented by the regular expression R. String w matches
regular expression R if and only if w ∈ L(R).
Here are several more examples of regular expressions and the languages they represent.
• (" + 1)(01)∗ (" + 0) — the set of all strings of alternating 0s and 1s, or equivalently, the
set of all binary strings that do not contain the substrings 00 or 11.
• (0 + 1)∗ 0000(0 + 1)∗ — the set of all binary strings that contain the substring 0000.
• ((" + 0 + 00 + 000)1)∗ (" + 0 + 00 + 000) — the set of all binary strings that do not contain
the substring 0000.
• ((0 + 1)(0 + 1))∗ — the set of all binary strings whose length is even.
• 1∗ (01∗ 01∗ )∗ — the set of all binary strings with an even number of 0s.
• 0 + 1(0 + 1)∗ 00 — the set of all non-negative binary numerals divisible by 4 and with no
redundant leading 0s.
• 0∗ 0 + 0∗ 1(10∗ 1 + 01∗ 0)∗ 10∗ — the set of all non-negative binary numerals divisible by 3,
possibly with redundant leading 0s.
The last example should not be obvious. It is straightforward, but really tedious, to prove
by induction that every string in 0∗ 0 + 0∗ 1(10∗ 1 + 01∗ 0)∗ 10∗ is the binary representation of a
non-negative multiple of 3. It is similarly straightforward, but even more tedious, to prove that
the binary representation of every non-negative multiple of 3 matches this regular expression. In
a later note, we will see a systematic method for deriving regular expressions for some languages
that avoids (or more accurately, automates) this tedium.
Two regular expressions R and R0 are equivalent if they describe the same language. For
example, the regular expressions (0 + 1)∗ and (1 + 0)∗ are equivalent, because the union
operator is commutative. More subtly, the regular expressions (0 + 1)∗ and (0∗ 1∗ )∗ and
(00 + 01 + 10 + 11)∗ (0 + 1 + ") are all equivalent; intuitively, these three expressions represent
different ways of thinking about the language {0, 1}∗ . In fact, almost every regular language can
be represented by infinitely many distinct but equivalent regular expressions, even if we ignore
ultimately trivial equivalences like L = (L∅)∗ L" + ∅.
ÆÆÆ Give some examples of designing regular expressions via Arden’s rule. For example: All
strings that don’t contain the substring 0011.
4
Models of Computation Lecture 2: Regular Languages [Sp’18]
These cases mirror the definition of regular language exactly. A leaf labeled ∅ represents the
empty language; a leaf labeled with a string represents the language containing only that string;
a node labeled + represents the union of the languages represented by its two children; a node
labeled • represents the concatenation of the languages represented by its two children; and a
node labeled ∗ represents the Kleene closure of the languages represented by its child.
+
• •
* 0 * •
0 0 1 •
* •
+ 1 *
• • 0
1 • 0 •
* 1 * 0
0 1
A regular expression tree for 0∗ 0 + 0∗ 1(10∗ 1 + 01∗ 0)∗ 10∗
5
Models of Computation Lecture 2: Regular Languages [Sp’18]
The size of a regular expression is the number of nodes in its regular expression tree. The size
of a regular expression could be either larger or smaller than its length as a raw string. On the
one hand, concatenation nodes in the tree are not represented by symbols in the string; on the
other hand, parentheses in the string are not represented by nodes in the tree. For example, the
regular expression 0∗ 0 + 0∗ 1(10∗ 1 + 01∗ 0)∗ 10∗ has size 29, but the corresponding raw string
0*0+0*1(10*1+01*0)*10* has length 22.
A subexpression of a regular expression R is another regular expression S whose regular
expression tree is a subtree of some regular expression tree for R. A proper subexpression of R
is any subexpression except R itself. Every subexpression of R is also a substring of R, but not
every substring is a subexpression. For example, the substring 10∗ 1 is a proper subexpression
of 0∗ 0 + 0∗ 1(10∗ 1 + 01∗ 0)∗ 10∗ . However, the substrings 0∗ 0 + 0∗ 1 and 0∗ 1 + 01∗ are not
subexpressions of 0∗ 0 + 0∗ 1(10∗ 1 + 01∗ 0)∗ 10∗ , even though they are well-formed regular
expressions.
• Suppose R = ∅.
6
Models of Computation Lecture 2: Regular Languages [Sp’18]
Students uncomfortable with structural induction can instead induct on the size of the regular
expression (defined as the number of nodes in the corresponding regular expression tree). This
variant changes only the statement of inductive hypothesis, not the structure of the proof itself;
the rest of the boilerplate is utterly identical.
Here is an example of the structural induction boilerplate in action. Again, this proof is longer
than a typical induction proof about strings or integers, but each individual case is still just a
short exercise in definition-chasing.
Lemma 2.4. Every regular expression that does not use the symbol ∅ represents a non-empty
language.
Proof: Let R be an arbitrary regular expression that does not use the symbol ∅. Assume that
every proper subexpression of R that does not use the symbol ∅ represents a non-empty language.
There are five cases to consider, mirroring the definition of R.
7
Models of Computation Lecture 2: Regular Languages [Sp’18]
Similarly, most algorithms that accept regular expressions as input actually require regular
expression trees, rather than regular expressions as raw strings. Fortunately, it is possible to parse
any regular expression of length n into an equivalent regular expression tree in O(n) time. (The
details of the parsing algorithm are beyond the scope of this chapter.) Thus, when we see an
algorithmic problem that starts “Given a regular expression. . . ”, we can assume without loss of
generality that we are actually given a regular expression tree.
Lemma 2.5. Every non-empty regular language is represented by a regular expression that does
not use the symbol ∅.
Proof: Let R be an arbitrary regular expression; we need to prove that either L(R) = ∅ or
L(R) = L(R0 ) for some ∅-free regular expression R0 . For every proper subexpression S of R,
assume that either L(S) = ∅ or L(S) = L(S 0 ) for some ∅-free regular expression S 0 . There are
five cases to consider, mirroring the definition of R.
• If R = ∅, then L(R) = ∅.
• Suppose R = S + T for some regular expressions S and T . There are four subcases to
consider:
• Suppose R = S • T for some regular expressions S and T . There are two subcases to
consider.
• Suppose R = S ∗ for some regular expression S. There are two subcases to consider.
8
Models of Computation Lecture 2: Regular Languages [Sp’18]
• Every regular expression over the one-symbol alphabet {} is itself a string over the
seven-symbol alphabet {, +, (, ), *, 3, Ø}. By interpreting these symbols as the digits 1
through 7, we can interpret any string over this larger alphabet as the base-8 representation
of some unique integer. Thus, the set of all regular expressions over {} is at most as large
as the set of integers, and is therefore countably infinite. It follows that the set of all regular
languages over {} is also countably infinite.
• On the other hand, for any real number 0 ≤ α < 1, we can define a corresponding language
Lα = n α2n mod 1 ≥ 1/2 .
In other words, Lα contains the string n if and only if the (n + 1)th bit in the binary
representation of α is equal to 1. For any distinct real numbers α 6= β, the binary
representations of α and β must differ in some bit, so Lα 6= Lβ . We conclude that the set
of all languages over {} is at least as large as the set of real numbers between 0 and 1,
and is therefore uncountably infinite.
We will see several explicit examples of non-regular languages in later lectures. In particular, the
set of all regular expressions over the alphabet {0, 1} is itself a non-regular language over the
alphabet {0, 1, +, (, ), *, 3, Ø}!
Exercises
1. (a) Prove that ∅ • L = L • ∅ = ∅, for every language L.
(b) Prove that {"} • L = L • {"} = L, for every language L.
(c) Prove that (A • B) • C = A • (B • C), for all languages A, B, and C.
(d) Prove that |A• B| ≤ |A| · |B|, for all languages A and B. (The second · is multiplication!)
i. Describe two languages A and B such that |A • B| < |A| · |B|.
ii. Describe two languages A and B such that |A • B| = |A| · |B|.
(e) Prove that L ∗ is finite if and only if L = ∅ or L = {"}.
(f) Prove that if A • B = B • C, then A∗ • B = B • C ∗ = A∗ • B • C ∗ , for all languages A, B,
and C.
(g) Prove that (A ∪ B)∗ = (A∗ • B ∗ )∗ , for all languages A and B.
9
Models of Computation Lecture 2: Regular Languages [Sp’18]
4. For each of the following languages in {0, 1}∗ , describe an equivalent regular expression.
There are infinitely many correct answers for each language. (This problem will become
significantly simpler after we’ve seen finite-state machines.)
10
Models of Computation Lecture 2: Regular Languages [Sp’18]
[Hint: Yes, all three proofs use induction, but induction on what? And yes, all three
proofs.]
For example, 1((0∗ 10)∗ 1)∗ 0 is plus-free and (therefore) top-plus; 01∗ 0 + 10∗ 1 + " is
top-plus but not plus-free, and 0(0 + 1)∗ (1 + ") is neither top-plus nor plus-free.
Recall that two regular expressions R and S are equivalent if they describe exactly the
same language: L(R) = L(S).
(a) Prove that for any top-plus regular expressions R and S, there is a top-plus regular
expression that is equivalent to RS.
(b) Prove that for any top-plus regular expression R, there is a plus-free regular expres-
sion S such that R∗ and S ∗ are equivalent.
11
Models of Computation Lecture 2: Regular Languages [Sp’18]
(c) Prove that for any regular expression, there is an equivalent top-plus regular expres-
sion.
You may assume the following facts without proof, for all regular expressions A, B, and C:
8. (a) Describe and analyze an efficient algorithm to determine, given a regular expression R,
whether L(R) = ∅.
(b) Describe and analyze an efficient algorithm to determine, given a regular expression R,
whether L(R) = {"}. [Hint: Use part (a).]
(c) Describe and analyze an efficient algorithm to determine, given a regular expression R,
whether L(R) is finite. [Hint: Use parts (a) and (b).]
In each problem, assume you are given R as a regular expression tree, not just a raw string.
12
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
Life only avails, not the having lived. Power ceases in the instant of repose;
it resides in the moment of transition from a past to a new state,
in the shooting of the gulf, in the darting to an aim.
— Ralph Waldo Emerson, “Self Reliance”, Essays, First Series (1841)
3 Finite-State Machines
3.1 Intuition
Suppose we want to determine whether a given string w[1 .. n] of bits represents a multiple of 5
in binary. After a bit of thought, you might realize that you can read the bits in w one at a time,
from left to right, keeping track of the value modulo 5 of the prefix you have read so far.
MultipleOf5(w[1 .. n]):
rem ← 0
for i ← 1 to n
rem ← (2 · rem + w[i]) mod 5
if rem = 0
return True
else
return False
Aside from the loop index i, which we need just to read the entire input string, this algorithm
has a single local variable rem, which has only four different values: 0, 1, 2, 3, or 4.
This algorithm already runs in O(n) time, which is the best we can hope for—after all, we
have to read every bit in the input—but we can speed up the algorithm in practice. Let’s define a
change or transition function δ : {0, 1, 2, 3, 4} × {0, 1} → {0, 1, 2, 3, 4} as follows:
(Here I’m implicitly converting the symbols 0 and 1 to the corresponding integers 0 and 1.) Since
we already know all values of the transition function, we can store them in a precomputed table,
and then replace the computation in the main loop of MultipleOf5 with a simple array lookup.
We can also modify the return condition to check for different values modulo 5. To be
completely general, we replace the final if-then-else lines with another array lookup, using an
array A[0 .. 4] of booleans describing which final mod-5 values are “acceptable”.
After both of these modifications, our algorithm looks like one of the following, depending on
whether we want something iterative or recursive (with q = 0 in the initial call):
DoSomethingCool(q, w):
DoSomethingCool(w[1 .. n]):
if w = "
q←0
return A[q]
for i ← 1 to n
else
q ← δ[q, w[i]]
decompose w = a · x
return A[q]
return DoSomethingCool(δ(q, a), x)
1
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
We can also visualize the behavior of DoSomethingCool by drawing a directed graph, whose
vertices represent possible values of the variable q—the possible states of the algorithm—and
whose edges are labeled with input symbols to represent transitions between states. Specifically,
a
the graph includes the labeled directed edge p−→q if and only if δ(p, a) = q. To indicate the
proper return value, we draw the “acceptable” final states using doubled circles. Here is the
resulting graph for MultipleOf5:
0
1 3
1 1 0
0 0 0 1 4 1
1 0
2
State-transition graph for MultipleOf5
If we run the MultipleOf5 algorithm on the string 00101110110 (representing the number
374 in binary), the algorithm performs the following sequence of transitions:
0 0 1 0 1 1 1 0 1 1 0
0 −→ 0 −→ 0 −→ 1 −→ 2 −→ 0 −→ 1 −→ 3 −→ 1 −→ 3 −→ 2 −→ 4
Because the final state is not the “acceptable” state 0, the algorithm correctly returns False.
We can also think of this sequence of transitions as a walk in the graph, which is completely
determined by the start state 0 and the sequence of edge labels; the algorithm returns True if
and only if this walk ends at an “acceptable” state.
2
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
Finally, a finite-state machine accepts a string w if and only if δ∗ (s, w) ∈ A, and rejects w
otherwise. (Compare this definition with the recursive formulation of DoSomethingCool!)
For example, our final MultipleOf5 algorithm is a DFA with the following components:
1It’s unclear why we use the letter Q to refer to the state set, and lower-case q to refer to a generic state, but that
is now the firmly-established notational standard. Although the formal study of finite-state automata began much
earlier, its modern formulation was established in a 1959 paper by Michael Rabin and Dana Scott, for which they won
the Turing award. Rabin and Scott called the set of states S, used lower-case s for a generic state, and called the start
state s0 . On the other hand, in the 1936 paper for which the Turing award was named, Alan Turing used q1 , q2 , . . . , qR
to refer to states (or “m-configurations”) of a generic Turing machine. Turing may have been mirroring the standard
notation Q for configuration spaces in classical mechanics, also of uncertain origin.
3
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
We have already seen a more graphical representation of this entire sequence of transitions:
0 0 1 0 1 1 1 0 1 1 0
0 −→ 0 −→ 0 −→ 1 −→ 2 −→ 0 −→ 1 −→ 3 −→ 1 −→ 3 −→ 2 −→ 4
The arrow notation is easier to read and write for specific examples, but surprisingly, most people
actually find the more formal functional notation easier to use in formal proofs. Try them both!
We can equivalently define a DFA as a directed graph whose vertices are the states Q, whose
edges are labeled with symbols from Σ, such that every vertex has exactly one outgoing edge
with each label. In our drawings of finite state machines, the start state s is always indicated
by an incoming arrow, and the accepting states A are always indicted by doubled circles. By
induction, for any string w ∈ Σ∗ , this graph contains a unique walk that starts at s and whose
edges are labeled with the symbols in w in order. The machine accepts w if this walk ends at an
accepting state. This graphical formulation of DFAs is incredibly useful for developing intuition
and even designing DFAs. For proofs, it’s largely a matter of taste whether to write in terms of
extended transition functions or labeled graphs, but (as much as I wish otherwise) I actually find
it easier to write correct proofs using the functional formulation.
1
0 s t 0
1
A simple finite-state machine.
For example, the two-state machine M at the top of this page accepts the string 00101110100
after the following sequence of transitions:
0 0 1 0 1 1 1 0 1 0 0
s −→ s −→ s −→ t −→ t −→ s −→ t −→ s −→ s −→ t −→ t −→ t.
The same machine M rejects the string 11101101 after the following sequence of transitions:
1 1 1 0 1 1 0 1
s −→ t −→ s −→ t −→ t −→ s −→ t −→ t −→ s.
Finally, M rejects the empty string, because the start state s is not an accepting state.
From these examples and others, it is easy to conjecture that the language of M is the set of
all strings of 0s and 1s with an odd number of 1s. So let’s prove it!
Proof (tedious case analysis): Let #(a, w) denote the number of times symbol a appears in
string w. We will prove the following stronger claims by induction, for any string w.
¨ ¨
∗ s if #(1, w) is even ∗ t if #(1, w) is even
δ (s, w) = and δ (t, w) =
t if #(1, w) is odd s if #(1, w) is odd
Let’s begin. Let w be an arbitrary string. Assume that for any string x that is shorter than w,
we have δ∗ (s, x) = s and δ∗ (t, x) = t if x has an even number of 1s, and δ∗ (s, x) = t and
δ∗ (t, x) = s if x has an odd number of 1s. There are five cases to consider.
4
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
Since the remaining cases are similar, I’ll omit the line-by-line justification.
• If w = 1 x and #(1, w) is odd, then #(1, x) is even, so the inductive hypothesis implies
• If w = 0 x and #(1, w) is even, then #(1, x) is even, so the inductive hypothesis implies
• Finally, if w = 0 x and #(1, w) is odd, then #(1, x) is odd, so the inductive hypothesis
implies
Notice that this proof contains |Q|2 · |Σ| + |Q| separate inductive arguments. For every pair of
states p and q, we must argue about the language of all strings w such that δ∗ (p, w) = q, and
we must consider every possible first symbol in w. We must also argue about δ(p, ") for every
state p. Each of those arguments is typically straightforward, but it’s easy to get lost in the deluge
of cases.
For this particular proof, however, we can reduce the number of cases by switching from tail
recursion to head recursion. The following identity holds for all strings x ∈ Σ∗ and symbols
a ∈ Σ:
δ∗ (q, x a) = δ(δ∗ (q, x), a)
We leave the inductive proof of this identity as a straightforward exercise (hint, hint).
Proof (clever renaming, head induction): Let’s rename the states with the integers 0 and 1
instead of s and t. Then the transition function can be described concisely as δ(q , a) =
(q + a) mod 2. We claim that for every string w, we have δ∗ (0, w) = #(1, w) mod 2.
Let w be an arbitrary string, and assume that for any string x that is shorter than w that
δ∗ (0, x) = #(1, x) mod 2. There are only two cases to consider: either w is empty or it isn’t.
5
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
Hmmm. This “clever” proof is certainly shorter than the earlier brute-force proof, but is it
actually better? Simpler? More intuitive? Easier to understand? I’m skeptical. Sometimes brute
force really is more effective.
This clock doesn’t quite match our abstraction, because there’s no “start” state or “accepting”
states, unless perhaps you consider the “accepting” state to be the time when your train arrives.
A more playful example of a finite-state machine is the Rubik’s cube, a well-known mechanical
puzzle invented independently by Ernő Rubik in Hungary and Terutoshi Ishigi in Japan in the mid-
1970s. This puzzle has precisely 519,024,039,293,878,272,000 distinct configurations. In the unique
solved configuration, each of the six faces of the cube shows exactly one color. We can change the
configuration of the cube by rotating one of the six faces of the cube by 90 degrees, either clockwise
or counterclockwise. The cube has six faces (front, back, left, right, up, and down), so there are
exactly twelve possible turns, typically represented by the symbols R, L, F, B, U, D, R̄, L̄, F̄, B̄, Ū, D̄,
where the letter indicates which face to turn and the presence or absence of a bar over the letter
2A second hand was added to the Swiss Railway clocks in the mid-1950s, which sweeps continuously around the
clock in approximately 58½ seconds and then pauses at 12:00 until the next minute signal “to bring calm in the last
moment and ease punctual train departure”. Let’s ignore that.
6
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
The basic approach is to try to construct an algorithm that looks like MultipleOf5: A simple
for-loop through the symbols, using a constant number of variables, where each variable (except
the loop index) has only a constant number of possible values. Here, “constant” means an actual
number that is not a function of the input size n. You should be able to compute the number of
possible values for each variable at compile time.
For example, the following algorithm determines whether a given string in Σ = {0, 1}
contains the substring 11.
Contains11(w[1 .. n]):
found ← False
for i ← 1 to n
if i = 1
last2 ← w[1]
else
last2 ← w[i − 1] · w[i]
if last2 = 11
found ← True
return found
Aside from the loop index, this algorithm has exactly two variables.
7
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
• A boolean flag found indicating whether we have seen the substring 11. This variable has
exactly two possible values: True and False.
• A string last2 containing the last (up to) three symbols we have read so far. This variable
has exactly 7 possible values: ", 0, 1, 00, 01, 10, and 11.
Thus, altogether, the algorithm can be in at most 2 × 7 = 14 possible states, one for each possible
pair (found, last2). Thus, we can encode the behavior of Contains11 as a DFA with fourteen
states, where the start state is (False, ") and the accepting states are all seven states of the form
(True, ∗). The transition function is described in the following table (split into two parts to save
space):
For example, given the input string 1001011100, this DFA performs the following sequence of
transitions and then accepts.
1 0 0 1
(False, ") −→ (False, 1) −→ (False, 10) −→ (False, 00) −→
0 1 1
(False, 01) −→ (False, 10) −→ (False, 01) −→
1 0 0
(True, 11) −→ (True, 11) −→ (True, 10) −→ (True, 00)
You can probably guess that the brute-force DFA we just constructed has considerably more states
than necessary, especially after seeing its transition graph:
0 0 1 1 0 0
1 0 0 1
0 1 1 1 1 0 0
0 1
For example, the state (False, 11) has no incoming transitions, so we can just delete it. (This
state would indicate that we’ve never read 11, but the last two symbols we read were 11, which
8
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
is impossible!) More significantly, we don’t need actually to remember both of the last two
symbols, but only the penultimate symbol, because the last symbol is the one we’re currently
reading. This observation allows us to reduce the number of states from fourteen to only six.
1
F,1 1 Τ,1
1 1
F,ε 0 1 0 1 Τ,ε
0 0
F,0 Τ,0
0 0
A less brute-force DFA for strings containing the substring 11
But even this DFA has more states than necessary. Once the flag part of the state is set to
True, we know the machine will eventually accept, so we might as well merge all the accepting
states together. More subtly, because both transitions out of (False, 0) and (False, ") lead to the
same states, we can merge those two states together as well. After all these optimizations, we
obtain the following DFA with just three states:
• The start state, which indicates that the machine has not read the substring 11 and did
not just read the symbol 1.
• An intermediate state, which indicates that the machine has not read the substring 11 but
just read the symbol 1.
• A unique accept state, which indicates that the machine has read the substring 11.
This is the smallest possible DFA for this language.
0 0,1
0
1
1
A minimal DFA for superstrings of 11
While it is important not to use an excessive number of states when we design DFAs—too
many states makes a DFA hard to understand—there is really no point in trying to reduce DFAs
by hand to the absolute minimum number of states. Clarity is much more important than brevity
(especially in this class), and DFAs with too few states can also be hard to understand. At the end
of this note, I’ll describe an efficient algorithm that automatically transforms any given DFA into
an equivalent DFA with the fewest possible states.
9
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
• The states of the new DFA are all ordered pairs (p, q), where p is a state in M00 and q is a
state in M11 .
• The start state of the new DFA is the pair (s, s0 ), where s is the start state of M00 and s0 is
the start state of M11 .
a
• The new DFA includes the transition (p, q) −→ (p0 , q0 ) if and only if M00 contains the
a a
transition p −→ p0 and M11 contains the transition q −→ q0 .
• Finally, (p, q) is an accepting state of the new DFA if and only if p is an accepting state in
M00 and q is an accepting state in M11 .
The resulting nine-state DFA is shown on the next page, with the two factor DFAs M00 and
M11 shown in gray for reference. (The state (a, a) can be removed, because it has no incoming
transition, but let’s not worry about that now.)
0 0,1
0
s a 1 b
1
1
1 s s,s 1 s,a 1 s,b
1 0 0 0 0 1
1 1
0 0 0 0
0
0,1 b b,s b,a 1 b,b
1
0 0,1
Building a DFA for the language of strings containing both 00 and 11.
More generally, let M1 = (Σ, Q 1 , δ1 , s1 , A1 ) be an arbitrary DFA that accepts some language L1 ,
and let M2 = (Σ, Q 2 , δ2 , s2 , A2 ) be an arbitrary DFA that accepts some language L2 (over the
same alphabet Σ). We can construct a third DFA M = (Σ, Q, δ, s, A) that accepts the intersection
language L1 ∩ L2 as follows.
Q := Q 1 × Q 2 = (p, q) p ∈ Q 1 and q ∈ Q 2
δ((p, q), a) := δ1 (p, a), δ2 (q, a)
s := (s1 , s2 )
A := A1 × A2 = (p, q) p ∈ A1 and q ∈ A2
To convince ourselves that this product construction is actually correct, let’s consider the
extended transition function δ∗ : (Q × Q0 ) × Σ∗ → (Q × Q0 ), which acts on strings instead of
individual symbols. Recall that this function is defined recursively as follows:
(
(p, q) if w = ",
δ∗ (p, q), w :=
∗
δ δ((p, q), a), x if w = ax.
This function behaves exactly as we should expect:
10
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
Lemma 3.1. δ∗ ((p, q), w) = δ1∗ (p, w), δ2∗ (q, w) for any string w.
Proof: Let w be an arbitrary string. Assume δ∗ ((p, q), x) = δ1∗ (p, x), δ2∗ (q, x) for every string x
that is shorter than w. As usual, there are two cases to consider.
• First suppose w = ":
δ∗ (p, q), " = (p, q) by the definition of δ∗
= δ1∗ (p, "), q by the definition of δ1∗
= δ1∗ (p, e), δ2∗ (q, ") by the definition of δ2∗
An immediate consequence of this lemma is that for every string w, we have δ∗ (s, w) ∈ A if
and only if both δ1∗ (s1 , w) ∈ A1 and δ2∗ (s2 , w) ∈ A2 . In other words, M accepts w if and only if
both M1 accepts w and M2 accept w, as required.
As usual, this construction technique does not necessarily yield minimal DFAs. For example,
in our first example of a product DFA, illustrated above, the central state (a, a) cannot be reached
by any other state and is therefore redundant. Whatever.
Similar product constructions can be used to build DFAs that accept any other boolean
combination of languages; in fact, the only part of the construction that changes is the choice of
accepting states. For example:
• To accept the union L1 ∪ L2 , define A = (p, q) p ∈ A1 or q ∈ A2 .
• To accept the difference L1 \ L2 , define A = (p, q) p ∈ A1 but q 6∈ A2 .
• To accept the symmetric difference L1 ⊕ L2 , define A = (p, q) p ∈ A1 xor q ∈ A2 .
Examples of these constructions are shown on the next page.
Moreover, by cascading this product construction, we can construct DFAs that accept arbitrary
boolean combinations of arbitrary finite collections of regular languages.
We call a language automatic if it is the language of some finite state machine. Our product
construction examples let us prove that the set of automatic languages is closed under simple
boolean operations.
11
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
1 1 1
s,s 1 s,a 1 s,b s,s 1 s,a 1 s,b s,s 1 s,a 1 s,b
0 0 0 1 0 0 0 1 0 0 0 1
1 1 1 1 1 1
0 0 0 0 0 0 0 0 0
0 0 0
b,s b,a 1 b,b b,s b,a 1 b,b b,s b,a 1 b,b
1 1 1
0 0,1 0 0,1 0 0,1
(a) (b) (c)
DFAs for (a) strings that contain 00 or 11, (b) strings that contain either 00 or 11 but not both, and (c) strings that
contain 11 if they contain 00. These DFAs are identical except for their choices of accepting states.
Theorem 3.2. Let L and L 0 be arbitrary automatic languages over an arbitrary alphabet Σ.
• L = Σ∗ \ L is automatic.
• L ∪ L 0 is automatic.
• L ∩ L 0 is automatic.
• L \ L 0 is automatic.
• L ⊕ L 0 is automatic.
Eager students may have noticed that a Google search for the phrase “automatic language”
turns up no results that are relevant for this class, except perhaps this lecture note. That’s
because “automatic” is just a synonym for “regular”! This equivalence was first observed by
Stephen Kleene (the inventor of regular expressions) in 1956.
Theorem 3.3 (Kleene). For any regular expression R, there is a DFA M such that L(R) = L(M ).
For any DFA M , there is a regular expression R such that L(M ) = L(R).
Unfortunately, we don’t yet have all the tools we need to prove Kleene’s theorem; we’ll
return to the proof in the next lecture note, after we have introduced nondeterministic finite-state
machines. The proof is actually constructive—there are explicit algorithms that transform
arbitrary DFAs into equivalent regular expressions and vice versa.3
This equivalence between regular and automatic languages implies that the set of regular
languages is also closed under simple boolean operations. The union of two regular languages
is regular by definition, but it’s much less obvious that every boolean combination of regular
languages can also be described by regular expressions.
Corollary 3.4. Let L and L 0 be arbitrary regular languages over an arbitrary alphabet Σ.
• L = Σ∗ \ L is regular.
• L ∩ L 0 is regular.
• L \ L 0 is regular.
• L ⊕ L 0 is regular.
Conversely, because concatenations and Kleene closures of regular languages are regular by
definition, we can immediately conclude that concatenations and Kleene closures of automatic
languages are automatic.
3These conversion algorithms run in exponential time in the worst case, but that’s unavoidable. There are regular
languages whose smallest accepting DFA is exponentially larger than their smallest regular expression, and there are
regular languages whose smallest regular expression is exponentially larger than their smallest accepting DFA.
12
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
These results give us several options to prove that a given languages is regular or automatic.
We can either (1) build a regular expression that describes the language, (2) build a DFA that
accepts the language, or (3) build the language from simpler pieces from other regular/automatic
languages. (Later we’ll see a fourth option, and possibly even a fifth.)
Perhaps the single most important feature of DFAs is that they have no memory other than the
current state. Once a DFA enters a particular state, all future transitions depend only on that
state and future input symbols; past input symbols are simply forgotten.
For example, consider our very first DFA, which accepts the binary representations of integers
divisible by 5.
0
1 3
1 1 0
0 0 0 1 4 1
1 0
2
DFA accepting binary multiples of 5.
The strings 0010 and 11011 both lead this DFA to state 2, although they follow different
transitions to get there. Thus, for any string z, the strings 0010z and 11011z also lead to the
same state in this DFA. In particular, 0010z leads to the accepting state if and only if 11011z
leads to the accepting state. It follows that 0010z is divisible by 5 if and only if 11011z is
divisible by 5.
More generally, any DFA M = (Σ, Q, s, A, δ) defines an equivalence relation over Σ∗ , where
two strings x and y are equivalent if and only if they lead to the same state, or more formally, if
δ∗ (s, x) = δ∗ (s, y). If x and y are equivalent strings, then for any string z, the strings xz and
yz are also equivalent. In particular, M accepts xz if and only if M accepts yz. Thus, if L is
the language accepted by M , then xz ∈ L if and only if yz ∈ L. In short, if the machine can’t
distinguish between x and y, then the language can’t distinguish between xz and yz for any
suffix z.
Now let’s turn the previous argument on its head. Let L be an arbitrary language, and let x
and y be arbitrary strings. A distinguishing suffix for x and y (with respect to L) is a third
string z such that exactly one of the strings xz and yz is in L. If x and y have a distinguishing
13
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
suffix z, then in any DFA that accepts L, the strings xz and yz must lead to different states, and
therefore the strings x and y must lead to different states!
For example, let L5 denote the the set of all strings over {0, 1} that represent multiples of 5
in binary. Then the strings x = 01 and y = 0011 are distinguished by the suffix z = 01:
It follows that in every DFA that accepts L5 , the strings 01 and 0011 lead to different states.
Moreover, since neither 01 nor 0011 belong to L5 , every DFA that accepts L5 must have at least
two non-accepting states, and therefore at least three states overall.
A fooling set for a language L is a set F of strings such that every pair of strings in F has a
distinguishing suffix. For example, F = {0, 1, 10, 11, 100} is a fooling set for the language L5 of
binary multiples of 5, because each pair of strings in F has a distinguishing suffix:
• 0 distinguishes 0 and 1;
• 0 distinguishes 0 and 10;
• 0 distinguishes 0 and 11;
• 0 distinguishes 0 and 100;
• 1 distinguishes 1 and 10;
• 01 distinguishes 1 and 11;
• 01 distinguishes 1 and 100;
• 1 distinguishes 10 and 11;
• 1 distinguishes 10 and 100;
• 11 distinguishes 11 and 100.
Each of these five strings leads to a different state, for any DFA M that accepts L5 . Thus,
every DFA that accepts the language L5 has at least five states. And hey, look, we already have a
DFA for L5 with five states, so that’s the best we can do!
More generally, for any language L, and any fooling set F for L, every DFA that accepts L must
have at least |F | states. In particular, if the fooling set F is infinite, then every DFA that accepts L
must have an infinite number of states. But there’s no such thing as a finite-state machine with
an infinite number of states!
This is arguably both the simplest and most powerful method for proving that a language is
non-regular. Here are a few canonical examples of the fooling-set technique in action.
14
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
Proof: Let F denote the set 0∗ 1, and let x and y be arbitrary distinct strings in F . Then we
must have x = 0i 1 and y = 0 j 1 for some integers i 6= j. The suffix z = 10i distinguishes x
and y, because xz = 0i 110i ∈ L, but yz = 0i 110 j 6∈ L. We conclude that F is a fooling set for L.
Because F is infinite, L cannot be regular.
n
Lemma 3.8. The language L = {02 | n ≥ 0} is not regular.
i
Proof (F = L): Let x and y be arbitrary distinct strings in L. Then we must have x = 02
j i
and y = 02 for some integers i 6= j. The suffix z = 02 distinguishes x and y, because
i i i+1 i j
xz = 02 +2 = 02 ∈ L, but yz = 02 +2 6∈ L. We conclude that L itself is a fooling set for L.
Because L is infinite, L cannot be regular.
Proof (F = 0∗ ): Let x and y be arbitrary distinct strings in 0∗ . Then we must have x = 0i and
y = 0 j for some integers i 6= j; without loss of generality, assume i < j. Let k be any positive
k k k
integer such that 2k > j. Consider the suffix z = 02 −i . We have xz = 0i+(2 −i) = 02 ∈ L, but
k k
yz = 0 j+(2 −i) = 02 −i+ j 6∈ L, because
Thus, z is a distinguishing suffix for x and y. We conclude that 0∗ is a fooling set for L. Because
L is infinite, L cannot be regular.
Proof (F = 0∗ again): Let x and y be arbitrary distinct strings in 0∗ . Then we must have x = 0i
and y = 0 j for some integers i 6= j; without loss of generality, assume i < j. Let k be any positive
k k k
integer such that 2k−1 > j. Consider the suffix z = 02 − j . We have xz = 0i+(2 − j) = 02 − j+i 6∈ L,
because
2k−1 < 2k − 2k−1 + i < 2k − j + i < 2k .
k k
On the other hand, yz = 0 j+(2 − j) = 02 ∈ L. Thus, z is a distinguishing suffix for x and y. We
conclude that 0∗ is a fooling set for L. Because L is infinite, L cannot be regular.
The previous examples show the flexibility of this proof technique; a single non-regular
language can have many different infinite fooling sets,⁴ and each pair of strings in any fooling
set can have many different distinguishing suffixes. Fortunately, we only have to find one infinite
set F and one distinguishing suffix for each pair of strings in F .
15
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
Proof (F = 0∗ ): Again, we use 0∗ as our fooling set, but but the actual argument is somewhat
more complicated than in our earlier examples.
Let x and y be arbitrary distinct strings in 0∗ . Then we must have x = 0i and y = 0 j for
some integers i 6= j; without loss of generality, assume that i < j. Let p be any prime number
larger than i. Because p + 0( j − i) is prime and p + p( j − i) > p is not, there must be a positive
integer k ≤ p such that p + (k − 1)( j − i) is prime but p + k( j − i) is not. Then I claim that the
suffix z = 0 p+(k−1) j−ki distinguishes x and y:
(Because i < j and i < p, the suffix 0 p+(k−1) j−ki = 0(p−i)+(k−1)( j−i) has positive length and
therefore actually exists!) We conclude that 0∗ is indeed a fooling set for L, which implies that L
is not regular.
Proof (F = L): Let x and y be arbitrary distinct strings in L. Then we must have x = 0 p and
y = 0q for some primes p 6= q; without loss of generality, assume p < q.
Now consider strings of the form 0 p+k(q−p) . Because p +0(q − p) is prime and p + p(q − p) > p
is not prime, there must be a non-negative integer k < p such that p + k(p − q) is prime but
p + (k + 1)(p − q) is not prime. I claim that the suffix z = 0k(q−p) distinguishes x and y:
We conclude that L is a fooling set for itself!! Because L is infinite, L cannot be regular!
Obviously the most difficult part of this technique is coming up with an appropriate fooling
set. Fortunately, most languages L—in particular, almost all languages that students are asked to
prove non-regular on homeworks or exams—fall into one of two categories:
• Some simple regular language like 0∗ or 10∗ 1 or (01)∗ is a fooling set for L. In particular,
the fooling set is a regular language with one Kleene star and no +.
The most important point to remember is that you choose the fooling set F , and you can use that
fooling set to effectively impose additional structure on the language L.
ÆÆÆ
16
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
I’m not sure yet how to express this effectively, but here is some more intuition about
choosing fooling sets and distinguishing suffixes.
As a sanity check, try to write an algorithm to recognize strings in L , as described at the
start of this note, where the only variable that can take on an unbounded number of values
is the loop index i . (I should probably rewrite that template as a while-loop or tail recursion,
but anyway. . . .) If you succeed, the language is regular. But if you fail, it’s probably because
there are counters of string variables that you can’t get rid of. One of those unavoidable
counters is the basis for your fooling set.
For example, any algorithm that recognizes the language {0n 1n 2n | n ≥ 0} “obviously”
has to count 0s and 1s in the input string. (We can avoid counting 2s by decrementing the 0
counter.) Because the 0s come first in the string, this intuition suggests using strings of the
form 0n as our fooling set and matching strings of the form 1n 2n as distinguishing suffixes.
(This is a rare example of an “obvious” fact that is actually true.)
It’s also important to remember that when you choose the fooling set, you can effectively
impose additional structure that isn’t present in the language already. For example, to prove
that the language L = {w ∈ (0 + 1)∗ | #(0, w) = (1, w)} is not regular, we can use strings of
the form 0n as our fooling set and matching strings of the form 1n as distinguishing suffixes,
exactly as we did for {0n 1n | n ≥ 0}. The fact that L contains strings that start with 1 is
irrelevant. There may be more equivalence classes that our proof doesn’t find, but since we
found an infinite set of equivalence class, we don’t care.
At some level, this fooling set proof is implicitly considering the simpler language L ∩ 0∗ 1∗ =
{0 1 | n ≥ 0}. If L were regular, then L ∩ 0∗ 1∗ would also be regular, because regular
n n
?
3.9 The Myhill-Nerode Theorem
The fooling set technique implies a necessary condition for a language to be accepted by a
DFA—the language must have no infinite fooling sets. In fact, this condition is also sufficient.
The following powerful theorem was first proved by Anil Nerode in 1958, strengthening a 1957
result of John Myhill.⁵ We write x ≡ L y if xz ∈ L ⇐⇒ yz ∈ L for all strings z.
The Myhill-Nerode Theorem. For any language L, the following are equal:
(a) the minimum number of states in a DFA that accepts L,
(b) the maximum size of a fooling set for L, and
(c) the number of equivalence classes of ≡ L .
In particular, L is accepted by a DFA if and only if every fooling set for L is finite.
17
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
let [w] denote its equivalence class. We define a DFA M≡ = (Σ, Q, s, A, δ) as follows:
Q := [w] w ∈ Σ∗
s := ["]
A := [w] w ∈ L
δ([w], a) := [w • a]
We claim that this DFA accepts the language L; this claim completes the proof of the theorem.
But before we can prove anything about this DFA, we first need to verify that it is actually
well-defined. Let x and y be two strings such that [x] = [ y]. By definition of L-equivalence,
for any string z, we have xz ∈ L if and only if yz ∈ L. It immediately follows that for any
symbol a ∈ Σ and any string z 0 , we have x az 0 ∈ L if and only if y az 0 ∈ L. Thus, by definition of
L-equivalence, we have [x a] = [ y a] for every symbol a ∈ Σ. We conclude that the function δ is
indeed well-defined.
An easy inductive proof implies that δ∗ (["], x) = [x] for every string x. Thus, M accepts
string x if and only if [x] = [w] for some string w ∈ L. But if [x] = [w], then by definition
(setting z = "), we have x ∈ L if and only if w ∈ L. So M accepts x if and only if x ∈ L. In other
words, M accepts L, as claimed, so the proof is complete.
?
3.10 Minimal Automata
Given a DFA M = (Σ, Q, s, A, δ), suppose we want to find another DFA M 0 = (Σ, Q0 , s0 , A0 , δ0 ) with
the fewest possible states that accepts the same language. In this final section, we describe
an efficient algorithm to minimize DFAs, first described (in slightly different form) by Edward
Moore in 1956. We analyze the running time of Moore’s in terms of two parameters: n = |Q| and
σ = |Σ|.
In the preprocessing phase, we find and remove any states that cannot be reached from the
start state s; this filtering can be performed in O(nσ) time using any graph traversal algorithm.
So from now on we assume that all states are reachable from s.
Now we recursively define two states p and q in the remaining DFA to be distingushable,
written p 6∼ q , if at least one of the following conditions holds:
• p ∈ A and q 6∈ A,
• p 6∈ A and q ∈ A, or
• δ(p, a) 6∼ δ(q, a) for some a ∈ Σ.
Equivalently, p 6∼ q if and only if there is a string z such that exactly one of the states δ∗ (p, z)
and δ∗ (q, z) is accepting. (Sound familiar?) Intuitively, the main algorithm assumes that all
states are equivalent until proven otherwise, and then repeatedly looks for state pairs that can be
proved distinguishable.
The main algorithm maintains a two-dimensional table, indexed by the states, where
Dist[p, q] = True indicates that we have proved states p and q are distinguishable. Initially, for all
states p and q, we set Dist[p, q] ← True if p ∈ A and q 6∈ A or vice versa, and Dist[p, q] = False
otherwise. Then we repeatedly consider each pair of states and each symbol to find more
distinguishable pairs, until we make a complete pass through the table without modifying it. The
table-filling algorithm can be summarized as follows:
18
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
MinDFATable(Σ, Q, s, A, δ):
for all p ∈ Q
for all q ∈ Q
if (p ∈ A and q 6∈ A) or (p 6∈ A and q ∈ A)
Dist[p, q] ← True
else
Dist[p, q] ← False
notdone ← True
while notdone
notdone ← False
for all p ∈ Q
for all q ∈ Q
if Dist[p, q] = False
for all a ∈ Σ
if Dist[δ(p, a), δ(q, a)]
Dist[p, q] ← True
notdone ← True
return Dist
The algorithm must eventually halt, because there are only a finite number of entries in the
table that can be marked. In fact, the main loop is guaranteed to terminate after at most n
iterations, which implies that the entire algorithm runs in O(σn 3 ) time. Once the table is filled,⁶
any two states p and q such that Dist(p, q) = False are equivalent and can be merged into a
single state. The remaining details of constructing the minimized DFA are straightforward.
ÆÆÆ Need to prove that the main loop terminates in at most n iterations.
With more care, Moore’s minimization algorithm can be modified to run in O(σn2 ) time. A
faster DFA minimization algorithm, due to John Hopcroft, runs in O(σn log n) time.
Example
To get a better idea how this algorithm works, let’s visualize its execution on our earlier brute-force
DFA for strings containing the substring 11. This DFA has four unreachable states: (False, 11),
(True, "), (True, 0), and (True, 1). We remove these states, and relabel the remaining states for
easier reference. (In an actual implementation, the states would almost certainly be represented
by indices into an array anyway, not by mnemonic labels.)
The main algorithm initializes (the bottom half of) a 10×10 table as follows. (In the following
figures, cells marked × have value True and blank cells have value False.)
⁶More experienced readers should be enraged by the mere suggestion that any algorithm merely fills in a table, as
opposed to evaluating a recurrence. This algorithm is no exception. Consider the boolean function Dist(p, q, k), which
equals True if and only if p and q can be distinguished by some string of length at most k. This function obeys the
following recurrence:
(p ∈ A) ⊕ (q ∈ A) if k = 0,
Dist(p, q, k) = _
Dist(p, q, k − 1) ∨ Dist δ(p, a), δ(q, a), k − 1 otherwise.
a∈Σ
Moore’s “table-filling” algorithm is just a space-efficient dynamic programming algorithm to evaluate this recurrence.
19
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
0 1 2
0 0 1 1
1 5 9 0 8
1 0 0
0
0 01 1 1 1
0 3 1 4 7 1 6 0
Our brute-force DFA for strings containing the substring 11, after removing all four unreachable states
0 1 2 3 4 5 6 7 8
1
2
3
4
5
6 × × × × × ×
7 × × × × × ×
8 × × × × × ×
9 × × × × × ×
In the first iteration of the main loop, the algorithm discovers several distinguishable pairs
of states. For example, the algorithm sets Dist[0, 2] ← True because Dist[δ(0, 1), δ(2, 1)] =
Dist[2, 9] = True. After the iteration ends, the table looks like this:
0 1 2 3 4 5 6 7 8
1
2 × ×
3 ×
4 × × ×
5 × ×
6 × × × × × ×
7 × × × × × ×
8 × × × × × ×
9 × × × × × ×
The second iteration of the while loop makes no further changes to the table—We got lucky!—so
the algorithm terminates.
The final table implies that the 10 states of our DFA fall into exactly three equivalence classes:
{0, 1, 3, 5}, {2, 4}, and {6, 7, 8, 9}. Replacing each equivalence class with a single state gives us
the three-state DFA that we already discovered.
Exercises
1. For each of the following languages in {0, 1}∗ , describe a deterministic finite-state machine
that accepts that language. There are infinitely many correct answers for each language.
“Describe” does not necessarily mean “draw”.
20
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
0 1 2
0 1
0
1
1 5 9 0 8
1 0 1 0
0 1 0
1
0 1
0 3 1 4 7 1 6 0
0 0,1
1
1
0
Equivalence classes of states in our DFA, and the resulting minimal equivalent DFA.
21
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
? (t) Strings w such that F#(10,w) mod 10 = 4, where #(10, w) denotes the number of
times 10 appears as a substring of w, and as usual Fn is the nth Fibonacci number:
0 if n = 0
Fn = 1 if n = 1
F +F
n−1 n−2otherwise
Æ
(u) Strings w such that F#(1···0,w) mod 10 = 4, where #(1 · · · 0, w) denotes the number of
times 10 appears as a subsequence of w, and as usual Fn is the nth Fibonacci number:
0 if n = 0
Fn = 1 if n = 1
F
n−1 + Fn−2 otherwise
22
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
(v) Strings of the form w1 #w2 # · · · #w n for some n ≥ 2, where w i ∈ {0, 1}∗ for every
index i, and w i = w j for some indices i 6= j.
(w) The set of all palindromes in (0 + 1)∗ whose length is divisible by 7.
(x) {w ∈ (0 + 1)∗ | w is the binary representation of a perfect square}
Æ
(y) {w ∈ (0 + 1)∗ | w is the binary representation of a prime number}
4. For each of the following languages over the alphabet Σ = {0, 1}, either prove that the
language is regular (by constructing an appropriate DFA or regular expression) or prove
that the language is not regular (using fooling sets). Recall that Σ+ denotes the set of all
nonempty strings over Σ. [Hint: Believe it or not, most of these languages are actually
regular.]
(a) 0n w1n w ∈ Σ∗ and n ≥ 0
(b) 0n 1n w w ∈ Σ∗ and n ≥ 0
(c) w0n 1n x w, x ∈ Σ∗ and n ≥ 0
(d) 0n w1n x w, x ∈ Σ∗ and n ≥ 0
(e) 0n w1 x 0n w, x ∈ Σ∗ and n ≥ 0
(f) 0n w0n w ∈ Σ+ and n > 0
(g) w0n w w ∈ Σ+ and n > 0
(h) wx w w, x ∈ Σ∗
(i) wx w w, x ∈ Σ+
(j) wx wR w, x ∈ Σ+
(k) wwx w, x ∈ Σ+
(l) wwR x w, x ∈ Σ+
(m) wx w y w, x, y ∈ Σ+
(n) wx wR y w, x, y ∈ Σ+
(o) x ww y w, x, y ∈ Σ+
(p) x wwR y w, x, y ∈ Σ+
(q) wx x w w, x ∈ Σ+
? (r) wx wR x w, x ∈ Σ+
23
Models of Computation Lecture 3: Finite-State Machines [Sp’18]
(a) Suppose for any two distinct strings x, y ∈ F , there is a string w ∈ Σ∗ such that
wx ∈ L and w y 6∈ L. (We can reasonably call w a distinguishing prefix for x and y.)
Prove that L cannot be regular. [Hint: The reversal of a regular language is regular.]
? (b) Suppose for any two distinct strings x, y ∈ F , there are two (possibly equal) strings
w, z ∈ Σ∗ such that wxz ∈ L and w yz 6∈ L. Prove that L cannot be regular.
24
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
Freedom of choice
Is what you got.
Freedom from choice
Is what you want.
— Devo, “Freedom of Choice”, Freedom of Choice (1980)
4 Nondeterminism
4.1 Nondeterministic State Machines
The following diagram shows something that looks like a finite-state machine over the alphabet
{0, 1}, but on closer inspection, it is not consistent with our earlier definitions. On one hand,
there are two transitions out of s for each input symbol. On the other hand, states a and b are
each missing an outgoing transition.
a
0 0
1,0 s c 1,0
1 1
b
A nondeterministic finite-state automaton
Nevertheless, there is a sense in which this machine “accepts” the set of all strings that contain
either 00 or 11 as a substring. Imagine that when the machine reads a symbol in state s, it
makes a choice about which transition to follow. If the input string contains the substring 00,
then it is possible for the machine to end in the accepting state c, by choosing to move into
state a when it reads a 0 immediately before another 0. Similarly, if the input string contains
the substring 11, it is possible for the machine to end in the accepting state c. On the other hand,
if the input string does not contain either 00 or 11—or in other words, if the input alternates
between 0 and 1—there are no choices that lead the machine to the accepting state. If the
machine incorrectly chooses to transition to state a and then reads a 1, or transitions to b and
then reads 0, it explodes; the only way to avoid an explosion is to stay in state s.
This object is an example of a nondeterministic finite-state automaton, or NFA, so named
because its behavior is not uniquely determined by the input string. Formally, every NFA has five
components:
The only difference from the formal definition of deterministic finite-state automata is the domain
of the transition function. In a DFA, the transition function always returns a single state; in an
NFA, the transition function returns a set of states, which could be empty, or all of Q, or anything
in between.
Just like DFAs, the behavior of an NFA is governed by an input string w ∈ Σ∗ , which the
machine reads one symbol at a time, from left to right. Unlike DFAs, however, an NFA does not
maintain a single current state, but rather a set of current states. S Whenever the NFA reads a
symbol a, its set of current states changes from C to δ(C, a) := q∈C δ(q, a). After all symbols
have been read, the NFA accepts w if its current state set contains at least one accepting state
and rejects w otherwise. In particular, if the set of current states ever becomes empty, it will stay
empty forever, and the NFA will reject.
More formally, we define the function δ∗ : Q × Σ∗ → 2Q that transitions on strings as follows:
{q} if w = ",
δ∗ (q, w) := [
δ∗ (r, x) if w = ax.
r∈δ(q,a)
ÆÆÆ It’s arguably more natural to an arbitrary set of start states S ⊆ Q instead of just one. Then
an NFA accepts a string w if and only if there is a sequence of transitions consistent with w
from some start state to some accepting state, or more formally if δ∗ (S, q) ∩ A 6= ∅. Change
the definition and chase through all the theorems? Or prove equivalence and bounce back
and forth, like we already do for " -transitions?
4.2 Intuition
There are at least three useful ways to think about non-determinism.
Clairvoyance. Whenever an NFA reads symbol a in state q, it chooses the next state from the
set δ(q, a), always magically choosing a state that leads to the NFA accepting the input string,
unless no such choice is possible. As the BSD fortune file put it, “Nondeterminism means never
having to say you’re wrong.”1 Of course real machines can’t actually look into the future; that’s
why I used the word “magic”.
Parallel threads. An arguably more “realistic” view is that when an NFA reads symbol a in
state q, it spawns an independent execution thread for each state in δ(q, a). In particular, if
δ(q, a) is empty, the current thread simply dies. The NFA accepts if at least one thread is in an
accepting state after it reads the last input symbol.
1This sentence is a riff on a horrible aphorism that was (sadly) popular in the US in the 70s and 80s. Fortunately,
everyone seems to have forgotten the original saying, except maybe for that one time it was mocked on The Simpsons.
Ah, who am I kidding? Nobody remembers The Simpsons either.
2
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
Equivalently, we can imagine that when an NFA reads symbol a in state q, it branches into
several parallel universes, one for each state in δ(q, a). If δ(q, a) is empty, the NFA destroys the
universe (including itself). Similarly, if the NFA finds itself in a non-accepting state when the
input ends, the NFA destroys the universe. Thus, when the input is gone, only universes in which
the NFA somehow chose a path to an accept state still exist. One slight disadvantage of this
metaphor is that if an NFA reads a string that is not in its language, it destroys all universes.
Proofs/oracles. Finally, we can treat NFAs not as a mechanism for computing something, but as
a mechanism for verifying proofs. If we want to prove that a string w contains one of the suffixes
00 or 11, it suffices to demonstrate a single walk in our example NFA that starts at s and ends
at c, and whose edges are labeled with the symbols in w. Equivalently, whenever the NFA faces a
nontrivial choice, the prover can simply tell the NFA which state to move to next.
This intuition can be formalized as follows. Consider a deterministic finite state machine
whose input alphabet is the product Σ × Ω of an input alphabet Σ and an oracle alphabet Ω.
Equivalently, we can imagine that this DFA reads simultaneously from two strings of the same
length: the input string w and the oracle string ω. In either formulation, the transition function
has the form δ : Q × (Σ × Ω) → Q. As usual, this DFA accepts the pair (w, ω) ∈ (Σ × Ω)∗ if and
only if δ∗ (s, (w, ω)) ∈ A. Finally, M nondeterministically accepts the string w ∈ Σ∗ if there is
an oracle string ω ∈ Ω∗ with |ω| = |w| such that (w, ω) ∈ L(M ).
4.3 "-Transitions
It is fairly common for NFAs to include so-called "-transitions, which allow the machine to
change state without reading an input symbol. An NFA with "-transitions accepts a string w
a1 a2 a3 a`
if and only if there is a sequence of transitions s −→ q1 −→ q2 −→ · · · −→ q` where the final
state q` is accepting, each ai is either " or a symbol in Σ, and a1 a2 · · · a` = w.
For example, consider the following NFA with "-transitions. (For this example, we indicate
the "-transitions using large red arrows; we won’t normally do that.) This NFA deliberately has
more "-transitions than necessary.
0 0
a b c
ε
ε
1,0 s ε ε g 1,0
ε ε
d e f
1 1
A (rather silly) NFA with " -transitions
The NFA starts as usual in state s. If the input string is 100111, the the machine might
non-deterministically choose the following transitions and then accept.
" 1 " " 0 0 " 1 1 " 1 " "
s −→ s −→ s −→ d −→ a −→ b −→ c −→ d −→ e −→ f −→ e −→ f −→ c −→ g
More formally, the transition function in an NFA with "-transitions has a slightly larger
domain δ : Q × (Σ ∪ {"}) → 2Q . The "-reach of a state q ∈ Q consists of all states r that satisfy
one of the following conditions:
• either r = q,
3
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
Finally, as usual, an NFA with "-transitions accepts a string w if and only if δ∗ (s, w) contains at
least one accepting state.
Although it may appear at first that "-transitions give us a more powerful set of machines,
NFAs with and without "-transitions are actually equivalent. Given an NFA M = (Σ, Q, s, A, δ)
with "-transitions, we can construct an equivalent NFA M 0 = (Σ, Q0 , s0 , A0 , δ0 ) without "-transitions
as follows:
Q0 := Q
s0 = s
A0 = q ∈ Q "-reach(q) ∩ A 6= ∅
δ0 (q, a) = δ("-reach(q), a)
Straightforward definition-chasing now implies that M and M 0 accept exactly the same language.
Thus, whenever we reason about or design NFAs, we are free to either allow or forbid "-transitions,
whichever is more convenient for the task at hand.
For example, our previous NFA with "-transitions can be transformed into an equivalent NFA
without "-transitions, as shown in the figure below. The NFA on the right has two unreachable
states a and d, but whatever.
0 0 0 0
a b c a b c
ε 0 1,0
ε 0 1
1,0 s ε ε g 1,0 1,0 s g 1,0
1 0
ε ε
1 1,0
d e f d e f
1 1 1 1
1
A (rather silly) NFA with " -transitions, and an equivalent NFA without " -transitions
ÆÆÆ
4
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
• When no more of the previous modifications are possible, delete all " -transitions. This
modification does not change the accepted language.
Theorem 4.1. A language L can be described by a regular expression if and only if L is the
language accepted by a DFA.
The first of these four transformations is completely trivial; a DFA is just a special type of NFA
where the transition function always returns a single state. Unfortunately, the other three
transformations require a bit more work.
Q0 := 2Q
s0 := {s}
A0 := S ⊆ Q S ∩ A 6= ∅
[
δ0 (q0 , a) := δ(p, a) for all q0 ⊆ Q and a ∈ Σ.
p∈q0
Q0 := 2Q
s0 := {s}
5
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
A0 := S ⊆ Q "-reach(S) ∩ A 6= ∅
[ [
δ0 (q0 , a) := δ(r, a) for all q0 ⊆ Q and a ∈ Σ.
p∈q0 r∈"-reach(p)
This conversion from NFA to DFA is often called the subset construction, but that name is
somewhat misleading; it’s not a “construction” so much as a change in perspective.
For example, the subset construction converts the 4-state NFA on the first page of this note
into the following 16-state DFA. To simplify notation, I’ve named each DFA state using a simple
string, omitting the braces and commas from the corresponding subset of NFA states; for example,
DFA state sbc corresponds to the subset {s, b, c} of NFA states.
1 abc bc
1
sb sbc 0 0 a
1 1 0 1
1
0,1
s 0 1 sab 0 1 sc ab c Ø 0,1
0
0 0 1 0
1 1
sa sac 0,1 b
0
0 sabc ac
0
The 16-state DFA obtained from our first 4-state NFA by the subset construction.
Only the five yellow states are reachable from the start state.
An obvious disadvantage of this “construction” is that it (usually) leads to DFAs with far more
states than necessary, in part because many states cannot even be reached from the start state.
In the example above, there are eleven unreachable states; only five states are reachable from s.
Instead of building the entire subset DFA and then discarding the unreachable states, we can avoid
the unreachable states from the beginning by constructing the DFA incrementally, essentially by
performing a breadth-first search of the DFA graph.
To execute this algorithm by hand, we prepare a table with |Σ| + 3 columns, with one row for
each DFA state we discover. In order, these columns record the following information:
We start with DFA-state {s} in the first row and first column. Whenever we discover an unexplored
state in one of the last |Σ| columns, we copy it to the left column in a new row. To reduce
notational clutter, we write all subsets of NFA states without braces or commas.
For example, given the NFA with "-transitions from Section 4.3, the standard subset construc-
tion would produce a DFA with 256 states, but the incremental subset construction produces an
nine-state DFA, described by the following table and illustrated on the next page. We would fill
in the first row, for the starting DFA state s, as follows:
6
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
• The "-reach of NFA state s is {s, a, d}, so we write sad in the first column.
• None of the NFA states {s, a, d} is an accepting state, so {s} is not an accepting state of the
DFA, so we do not check the second column.
• Next, δ0 ({s, a, d}, 0) = δ(s, 0) ∪ δ(a, 0) ∪ δ(d, 0) = {s} ∪ {b} ∪ ∅ = {s, b}, so we write sb
in the third column. Because sb does not already appear in the first column in any existing
row, we have discovered a new DFA state! We start a new row for DFA state sb.
• Finally, δ0 ({s, a, d}, 1) = δ(s, 1) ∪ δ(a, 1) ∪ δ(d, 1) = {s} ∪ ∅ ∪ {e} = {s, e}, so we write se
in the fourth column, and we start a new row for the new DFA state se.
We now have two new rows to fill in, corresponding to states sb and se. The algorithm continues
filling in rows (and discovering new rows) until all rows are filled, ending with the following
table:
q0 "-reach(q0 ) q0 ∈ A0 ? δ0 (q0 , 0) δ0 (q0 , 1)
s sad sb se
sb sabd sbc se
se sade sb sef
sbc sabcdg Ø sbcg seg
sef sacdefg Ø sbg sefg
sbcg sabcdg Ø sbcg seg
seg sadeg Ø sbg sefg
sbg sabdg Ø sbcg seg
sefg sacdefg Ø sbg sefg
0
sbc sbcg 0
0 1 1
0 0
a b c sb seg
ε 0 1
ε
1,0 s ε ε g 1,0 s 0 1 0 1
ε ε 1 0
d e f se sbg
1 1 0 0
1
sef 1 sefg 1
An eight-state NFA with " -transitions, and the output of the incremental subset construction for that NFA.
Although it avoids unreachable states, the incremental subset algorithm still gives us a DFA
with far more states than necessary, intuitively because it keeps looking for 00 and 11 substrings
even after it’s already found one. After all, after the NFA finds both 00 and 11 as substrings, it
doesn’t kill all the other parallel execution threads, because it can’t. NFAs often have significantly
fewer states than equivalent DFAs, but that efficiency also makes them kind of stupid.
7
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
Proof: In fact, we will prove the following stronger claim: Every regular language is accepted
by an NFA with exactly one accepting state, which is different from its start state. The following
construction was first described by Ken Thompson in 1968. Thompson’s algorithm actually proves
a stronger statement: For any regular language L, there is an NFA that accepts L that has exactly
one accepting state t, which is distinct from the starting state s.
Let R be an arbitrary regular expression over an arbitrary finite alphabet Σ. Assume that for
any sub-expression S of R, the language described by S is accepted by an NFA with one accepting
state distinct from its start state, which we denote pictorially by S . There are six cases
to consider—three base cases and three recursive cases—mirroring the recursive definition of a
regular expression.
• Suppose R = ST for some regular expressions S and T . The inductive hypothesis implies
that the languages L(S) and L(T ) are accepted by NFAs S and T , respectively.
Then L(R) = L(S T ) = L(S) • L(T ) is accepted by the NFA S
ε
T , built by
connecting the two component NFAs in series.
built by connecting the two component NFAs in parallel with new start and accept states.
• Finally, suppose R = S ∗ for some regular expression S. The inductive hypothesis implies that
the language L(S) is accepted by an NFA S . Then the language L(R) = L(S ∗ ) = L(S)∗
ε
As an example, given the regular expression (0 + 10∗ 1)∗ of strings containing an even number
of 1s, Thompson’s algorithm produces a 14-state NFA shown on the next page. As this example
shows, Thompson’s algorithm tends to produce NFAs with many redundant states. Fortunately,
just as there are for DFAs, there are algorithms that can reduce any NFA to an equivalent NFA
with the smallest possible number of states.
Interestingly, applying the incremental subset algorithm to Thompson’s NFA tends to yield
a DFA with relatively few states, in part because the states in Thompson’s NFA tend to have
large "-reach, and in part because relatively few of those states are the targets of non-"-
transitions. Starting with the Thompson’s NFA for (0 + 10∗ 1)∗ , for example, the incremental
subset construction yields a DFA with just five states.
8
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
1 ε ε 0 ε ε 1
b c d e f g h i
ε ε
ε
ε ε
s a l m
ε ε
0
j k
ε
The NFA constructed by Thompson’s algorithm for the regular expression (0 + 10∗ 1)∗ .
The four non-" -transitions are drawn with with bold red arrows for emphasis.
1
0
q0 "-reach(q0 ) q0 ∈ A0 ? δ0 (q0 , 0) δ0 (q0 , 1)
s sabjm Ø k c c
0
f
1
i
k sabjklm Ø k c 1
1
c cdegh f i s 1 0
f defgh f i 0
i sabjilm Ø k c k
0
The DFA computed by the incremental subset algorithm from Thompson’s NFA for (0 + 10∗ 1)∗ .
This DFA can be further simplified to just two states, by observing that all three accepting
states are equivalent, and that both non-accepting states are equivalent. But still, five states is
pretty good, especially compared with the 214 = 16384 states that the naïve subset construction
would yield!
ε ε
Thompson’s NFA for the regular expression (0 + 1)∗ (00 + 11)(0 + 1)∗ ,
with the " -reach of the start state s highlighted.
Given this NFA as input, the incremental subset construction computes the following table,
leading to a DFA with just nine states. Yeah, the "-reaches get a bit ridiculous; unfortunately, this
is typical for Thompson’s NFA. As usual, the resulting DFA has far more states than necessary.
9
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
0 0
0 0
cj cjl cjv cjlv
0 1 1
s 0 1 0 1
1 0 0
en 1 enp enx 1
enpx
1 0
The DFA computed by the incremental subset algorithm from Thompson’s NFA for (0 + 1)∗ (00 + 11)(0 + 1)∗ .
Finally, the DFA-minimization algorithm from the previous lecture note correctly discovers
that all six accepting states of the incremental-subset DFA are equivalent, and thus reduces the
DFA to just four states.
0 0
0 1 0,1
1 1
The minimal DFA that accepts the language (0 + 1)∗ (00 + 11)(0 + 1)∗ .
?
4.8 NFA to Regular Expression: Han and Wood’s Algorithm
The only component of Kleene’s theorem left to prove is that every language accepted by an NFA
is regular. I’ll describe a relatively recent proof, due Yo-Sub Han and Derick Wood in 20052, that
is morally equivalent to Kleene’s 1951 argument, but uses more modern standard notation.
Recall that a standard NFA can be represented by a state-transition graph, whose vertices are
the states and whose edges represent possible transitions. Each edge is labeled with a single
symbol in Σ. A string w ∈ Σ∗ is accepted if and only if there is a sequence of transitions
a1 a2 a3 a`
s −→ q1 −→ q2 −→ · · · −→ q`
2Yo-Sub Han* and Derick Wood. The generalization of generalized automata: Expression automata. International
Journal of Foundations of Computer Science 16(3):499–510, 2005.
10
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
The requirement that the start and target states are unique and disatinct is not essential to the
model. We impose this requirement for convenience of the equivalence proof; it can be easily
enforced using "-transitions.
Expression automata are even more nondeterministic than NFAs. A single string could match
several (even infinitely many) transition sequences from s to t, and it could match each of
those sequences in several (even infinitely many) different ways. A string w is accepted if any
decomposition of w into a sequence of substrings matches any sequence of transitions from s to t.
Conversely, a string might match no state sequences, in which case the string is rejected.
Two extreme special cases of expression automata are already familiar. First, every regular
language is clearly the language of an expression automaton with exactly two states. Second,
with only minor modifications, any DFA or NFA can be converted into an expression automaton
with trivial transition expressions. Thompson’s algorithm can be used to transform any expression
automaton into a standard NFA (with "-transitions), by recursively expanding any nontrivial
transition expression. To complete the proof of Kleene’s theorem, we show how to convert an
arbitrary expression automaton into a regular expression, by repeatedly deleting vertices.
11
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
Proof: Let E = (Q, Σ, R, s, t) be an arbitrary expression automaton. Assume that any expression
automaton with fewer states than E accepts a regular language. There are two cases to consider,
depending on the number of states in Q:
• If Q = {s, t}, then trivially, E accepts the regular language R(s t).
• On the other hand, suppose Q has more than two states; fix an arbitrary state q ∈ Q \ {s, t}.
We modify the automaton, without changing its language, so that state q is redundant and
can be removed. Define a new transition function R0 : Q × Q → Reg(Σ) by setting
With this modified transition function in place, any string w that matches the sequence
pqq · · · q r with any number of q’s also matches the single transition p r. Thus,
by induction, if w matches a sequence of states, it also matches the subsequence obtained
by removing all q’s. Let E 0 be the expression automaton with states Q0 = Q \ {q} that uses
this modified transition function R0 . This new automaton accepts exactly the same strings
as the original automaton E. Because E 0 has fewer states than E, the inductive hypothesis
implies E 0 accepts a regular language.
This proof can be mechanically translated into an algorithm to convert any DFA or NFA into
an equivalent regular expression, via a sequence of expression automata with fewer and fewer
states, but increasingly complex transition expressions.
C C
q q
B D B D
p r p r
A A + BC*D
One step in Kleene’s/Han and Wood’s reduction algorithm.
The figure on the next page shows Han and Wood’s algorithm in action, starting with a DFA
that accepts the binary representations of non-negative integers divisible by 3, possibly with extra
leading 0s. (State i means the binary number we’ve read so far is congruent to i mod 3.) First
we convert the DFA into an expression automaton by adding a new accept state. (We don’t need
to add a new start state, because there are no transitions the original start state s.) Then we
remove state‘2, then state 0, and finally state 1, updating the transition expressions between
any remaining states at each iteration. For the sake of clarity, edges pq with R(pq) = ∅ are
omitted from the figures. The final regular expression 00∗ + (00∗ 1 + 1)(10∗ 1 + 01∗ 0)∗ 10∗ can
be slightly simplified to 0∗ 0 + 0∗ 1(10∗ 1 + 01∗ 0)∗ 10∗ , which is precisely the regular expression
we gave for this language back in Lecture Note 2!
Given an NFA with n states (including s and t), Han and Wood’s algorithm iteratively removes
n − 2 states, updating O(n2 ) transition expressions in each iteration. If the concatenation and
Kleene star operations could be performed in constant time, the resulting algorithm would run in
O(n3 ) time. However, in the worst case, the transition expressions grows in length by roughly a
factor of 4 in each iteration, so the final expression has length Θ(4n ). If we insist on representing
the expressions as explicit strings, the worst-case running time is actually Θ(4n ).
12
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
01*0
0 0
1 2 1 1 2 1 1
0 0
1 1 1
1 1 1
1 1 1
s 0 0 0 s 0 0 t s 0 t
ε 0 ε
0 0
01*0+10*1
1
00*+(00*1+1)(01*0+10*1)*10* 10*
s t
00*1+1
s 00* t
Converting a DFA into an equivalent regular expression using Han and Wood’s algorithm.
• Describe an algorithm that transforms an arbitrary regular expression R into a new regular
expression R0 such that L(R0 ) = f (L(R)).
• Describe an algorithm that transforms an arbitrary DFA M into a new NFA M 0 such that
L(M 0 ) = f (L(M )).
The equivalence between regular expressions and finite automata implies that in principle we
can always use either technique, but in practice, the second one is far more powerful and usually
simpler. The asymmetry in the second technique is important. We start with a DFA for L to
impose as much structure as possible in the input; we aim for an NFA with "-transitions to give
ourselves as much freedom as possible in the output.3
For our first example, I’ll describe proofs using both techniques.
Lemma 4.4. For any regular language L, the language L R = {wR | w ∈ L} is also regular.
• If R = ∅, then L R = L = ∅, so L(R) = L R .
13
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
• Suppose R = A + B. The inductive hypothesis implies that there are regular expressions
A0 and B 0 such that L(A0 ) = L(A)R and L(B 0 ) = L(B)R . Let R0 = A0 + B 0 . Then L(R0 ) =
L(A0 ) ∪ L(B 0 ) = L(A)R ∪ L(B)R = (L(A) ∪ L(B))R = L R .
• Suppose R = A • B. The inductive hypothesis implies that there are regular expressions
A0 and B 0 such that L(A0 ) = L(A)R and L(B 0 ) = L(B)R . Let R0 = B 0 • A0 . Then L(R0 ) =
L(B 0 ) • L(A0 ) = L(B)R • L(A)R = (L(A) • L(B))R = L R .
• Finally, suppose R = A∗ . The inductive hypothesis implies that there is a regular expression A0
such that L(A0 ) = L(A)R . Let R0 = (A0 )∗ . Then L(R0 ) = L(A0 )∗ = (L(A)R )∗ = (L(A)∗ )R = L R .
In all cases, we have constructed a regular expression R0 such that L(R0 ) = L R . We conclude that
L R is regular.
Careful readers may be unsatisfied with the previous proof, because it assumes several
“obvious” properties of string and language reversal. Specifically, for all strings x and y and all
languages L and L 0 , we assumed the following:
• (x • y)R = y R • x R
• (L · L 0 )R = (L 0 )R · L R .
• (L ∪ L 0 )R = L R ∪ (L 0 )R .
• (L ∗ )R = (L R )∗ .
All of these claims are all easy to prove by inductive definition-chasing.
Proof (DFA to NFA): Let M = (Σ, Q, s, A, δ) be an arbitrary DFA that accepts L. We construct
an NFA M R = (Σ, QR , sR , AR , δR ) with "-transitions that accepts L R , intuitively by reversing every
transition in M , and swapping the roles of the start state and the accepting states. Because
M does not have a unique accepting state, we need to introduce a special start state sR , with
"-transitions to each accepting state in M . These are the only "-transitions in M R .
QR = Q ∪ {sR }
AR = {s}
δR (sR , ") = A
δR (sR , a) = ∅ for all a ∈ Σ
δR (q, ") = ∅ for all q ∈ Q
δR (q, a) = p q ∈ δ(p, a) for all q ∈ Q and a ∈ Σ
Routine inductive definition-chasing now implies that the reversal of any sequence q0 q1 · · · q`
of transitions in M is a valid sequence q` q`−1 · · · q0 of transitions in M R . Because the
transitions retain their labels (but reverse directions), it follows that M accepts any string w if
and only if M R accepts wR .
We conclude that the NFA M R accepts L R , so L R must be regular.
Lemma 4.5. For any regular language L, the language half(L) := {w | ww ∈ L} is also regular.
14
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
• First M 0 non-deterministically guesses the state h = δ∗ (s, w) that M will reach after reading
input w. (We can’t just run M on input w to compute the correct state h, because that
would consume the input string!)
• Then M 0 runs two copies of M in parallel (using a product construction): a “left” copy
starting at s and a “right” copy starting at the (guessed) halfway state h.
• Finally, when M 0 is done reading w, it accepts if and only if the first copy of M actually
stopped in state h (so our initial guess was correct) and the second copy of M stopped in
an accepting state. That is, M 0 accepts if and only if δ∗ (s, w) = h and δ∗ (h, w) ∈ A.
To implement this strategy, M 0 needs to maintain three states of M : the state of the left copy
of M , the guess h for the halfway state, and the state of the right copy of M . The first and
third states evolve according to the transition function δ, but the second state never changes.
Finally, to implement the non-deterministic guessing, M 0 includes a special start state s0 with
"-transitions to every triple of the form (s, h, h).
Summing up, our new NFA M 0 = (Σ, Q0 , s0 , A0 , δ0 ) is formally defined as follows.
Q0 = (Q × Q × Q) ∪ {s0 }
A0 = (h, h, q) h ∈ Q and q ∈ A
δ0 (s0 , ") = (s, h, h) h ∈ Q
δ0 (s0 , a) = ∅ for all a ∈ Σ
δ0 ((p, h, q), ") = ∅ for all p, h, q ∈ Q
δ0 ((p, h, q), a) = (δ(p, a), h, δ(q, a)) for all p, h, q ∈ Q and a ∈ Σ
Exercises
1. For each of the following regular expressions, describe or draw two finite-state machines:
• An NFA that accepts the same language, constructed using Thompson’s algorithm.
• An equivalent DFA, built from the previous NFA using the incremental subset con-
struction. For each state in your DFA, identify the corresponding subset of states in
your NFA. Your DFA should have no unreachable states.
15
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
(a) L∀ (M ) := w ∈ Σ∗ A ⊆ δ∗ (s, w) . That is, a string w is in the language L∀ (M ) if and
only if δ∗ (s, w) contains every accepting states.
(b) L ⊆ (M ) := w ∈ Σ∗ δ∗ (s, w) ⊆ A . That is, a string w is in the language L ⊆ (M ) if
and only if δ∗ (s, w) contains only accepting states.
(c) L ≡ (M ) := w ∈ Σ∗ δ∗ (s, w) = A . That is, a string w is in the language L = (M ) if
and only if δ∗ (s, w) is exactly the set of accepting states.
3. A certain professor who really should know better once woke up in the middle of the night
with a startling revelation—Thompson’s algorithm doesn’t need all those "-transitions!
Filled with the certainty that only sleep deprivation can bring, he ran to his laptop and
quickly changed two cases in his description of Thompson’s algorithm.
simpler NFA S !
ε
Satisfied with his simplification, he thanked the penguin who gave him the idea, and
then flew his hat back into the ocean marshmallows, where a giant man with the head of a
dog gave him the power of bread. The next morning, while he was proudly teaching his
new simplified proof for the first time, he realized his horrible mistake.
Prove that neither of the professor’s optimizations is actually correct.
(a) Find a regular expression R, such that the NFA constructed from R by Thompson’s
algorithm with only the first modification accepts strings that are not in L(R).
(b) Find a regular expression R, such that the NFA constructed from R by Thompson’s
algorithm with only the second modification accepts strings that are not in L(R).
16
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
More intuitively, a Moore machine is a graph with a special start vertex, where every node
(state) has one outgoing edge labeled with each symbol from the input alphabet, and each
node (state) is additionally labeled with a symbol from the output alphabet.
The Moore machine reads an input string w ∈ Σ∗ one symbol at a time. For each
symbol, the machine changes its state according to the transition function δ, and then
outputs the symbol ω(q), where q is the new state. Formally, we recursively define a
transducer function ω∗ : Σ∗ × Q → Γ ∗ as follows:
¨
" if w = "
ω∗ (w, q) = ∗
ω(δ(a, q)) · ω (x, δ(a, q)) if w = ax
Given the input string w ∈ Σ∗ , the machine outputs the string ω∗ (w, s) ∈ Γ ∗ . To simplify
notation, we define M (w) = ω∗ (w, s).
Finally, the output language L◦ (M) of a Moore machine M is the set of all strings that
the machine can output:
L ◦ (M ) := M (w) w ∈ Σ∗
[Hint: Parts (a) and (b) are easier than they look!]
More intuitively, a Mealy machine is a graph with a special start vertex, where every node
(state) has one outgoing edge labeled with each symbol from the input alphabet, and
each edge (transition) is additionally labeled with a symbol from the output alphabet.
(Mealy machines are closely related to Moore machines, which produce output at each
state instead of at each transition.)
17
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
The Mealy machine reads an input string w ∈ Σ∗ one symbol at a time. For each symbol,
the machine changes its state according to the transition function δ, and simultaneously
outputs a symbol according the output function ω. Formally, we recursively define a
transducer function ω∗ : Q × Σ∗ → Γ ∗ as follows:
¨
∗ " if w = "
ω (q, w) = ∗
ω(q, a) · ω (δ(q, a), x) if w = a x
Given any input string w ∈ Σ∗ , the machine outputs the string ω∗ (w, s) ∈ Γ ∗ . To simplify
notation, we define M (w) = ω∗ (w, s).
Finally, the output language L◦ (M) of a Mealy machine M is the set of all strings that
the machine can output:
L ◦ (M ) := {M (w) | w ∈ Σ∗ }
L = (M ) = {w ∈ Σ∗ | w = ω∗ (s, w)}
is regular. L = (M ) consists of all strings w such that M outputs w when given input w;
these are also called fixed points for the transducer function ω∗ .
? (c) As in part (b), let M be an arbitrary Mealy
machine
whose input and
output alphabets
are identical. Prove that the language w ∈ Σ∗ M (M (w)) = w is regular.
[Hint: Parts (a) and (b) are easier than they look!]
6. Let L ⊆ Σ∗ be an arbitrary regular language. Prove that the following languages are regular.
Assume # ∈ Σ.
(a) censor(L) := #|w| w ∈ L
(b) dehash(L) = dehash(w) w ∈ L , where dehash(w) is the subsequence of w obtained
by deleting every #.
(c) insert#(L) := x # y x y ∈ L .
(d) delete#(L) := x y x # y ∈ L .
(e) prefix(L) := {x ∈ Σ∗ | x y ∈ L for some y ∈ Σ∗ }
(f) suffix(L) := { y ∈ Σ∗ | x y ∈ L for some x ∈ Σ∗ }
(g) substring(L) := { y ∈ Σ∗ | x yz ∈ L for some x, z ∈ Σ∗ }
(h) superstring(L) := {x yz | y ∈ L and x, z ∈ Σ∗ }
(i) cycle(L) := {x y | x, y ∈ Σ∗ and y x ∈ L}
(j) prefmax(L) := {x ∈ L | x y ∈ L ⇐⇒ y = "}.
(k) sufmin(L) := {x y ∈ L | y ∈ L ⇐⇒ x = "}.
18
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
7. Let L and L 0 be arbitrary regular languages over the alphabet {0, 1}. Prove that the
following languages are also regular:
(a) L u L 0 := x u y x ∈ L and y ∈ L 0 and |x| = | y| , where x u y denotes bitwise-and.
For example, 0011 u 0101 = 0001.
(b) L t L 0 := x t y x ∈ L and y ∈ L 0 with |x| = | y| , where x t y denotes bitwise-or.
For example, 0011 t 0101 = 0111.
(c) L L 0 := x y x ∈ L and y ∈ L 0 with |x| = | y| , where x y denotes bitwise-
exclusive-or. For example, 0011 0101 = 0110.
(d) faro(L, L 0 ) := faro(x, z) x ∈ L and z ∈ L 0 with |x| = |z| , where
¨
z if x = "
faro(x, z) :=
a · faro(z, y) if x = a y
19
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
For example, shuffles(01, 10) = {0101, 0110, 1001, 1010} and shuffles(00, 11) =
{0011, 0101, 1001, 0110, 1010, 1100}.
8. (a) Let inc: {0, 1}∗ → {0, 1}∗ denote the increment function, which transforms the binary
representation of an arbitrary integer n into the binary representation of n + 1,
truncated to the same number of bits. For example:
Let L ⊆ {0, 1}∗ be an arbitrary regular language. Prove that inc(L) = {inc(w) | w ∈ L}
is also regular.
(b) Let dbl: {0, 1}∗ → {0, 1}∗ denote the doubling function, which transforms the binary
representation of an arbitrary integer n into the binary representation of 2n, truncated
to the same number of bits. For example:
Let L ⊆ {0, 1}∗ be an arbitrary regular language. Prove that dbl(L) = {dbl(w) | w ∈ L}
is also regular.
? (c) Let tpl: {0, 1}∗ → {0, 1}∗ denote the tripling function, which transforms the binary
representation of an arbitrary integer n into the binary representation of 3n, truncated
to the same number of bits. For example:
Let L ⊆ {0, 1}∗ be an arbitrary regular language. Prove that tpl(L) = {tpl(w) | w ∈ L}
is also regular. [Hint: It may be easier to consider the language tpl(L R )R first.]
? 9. Let L ⊆ Σ∗ be an arbitrary regular language. Prove that the following languages are
regular.
(a) sqrt(L) := x ∈ Σ∗ x y ∈ L for some y ∈ Σ∗ such that | y| = |x|2
(b) log(L) := x ∈ Σ∗ x y ∈ L for some y ∈ Σ∗ such that | y| = 2|x|
(c) flog(L) := x ∈ Σ∗ x y ∈ L for some y ∈ Σ∗ such that | y| = F|x| , where Fn is the
nth Fibonacci number.
? 10. Let L ⊆ Σ∗ be an arbitrary regular language. Prove that the following languages are
regular.
20
Models of Computation Lecture 4: Nondeterministic Automata [Sp’18]
Æ
(f) whattheN (L) := {w ∈ Σ∗ | wn ∈ L for some n ∈ N }, where N is an arbitrary fixed set
of non-negative integers. [Hint: You only have to prove that an accepting NFA exists;
you don’t have to describe how to construct it.]
[Hint: For each of these languages, there is an accepting NFA with at most qq states,
where q is the number of states in some DFA that accepts L.]
? 11. For any string w ∈ (0 + 1)∗ , let 〈w〉2 denote the integer represented by w in binary. For
example:
Let L and L 0 be arbitrary regular languages over the alphabet {0, 1}. Prove that the
following language is also regular:
w ∈ (0 + 1)∗ 〈w〉2 = 〈x〉2 + 〈 y〉2 for some strings x ∈ L and y ∈ L 0
Æ
12. Let L ⊆ Σ∗ be an arbitrary regular language. Prove that the following languages are
regular.
(a) repsqrt(L) = w ∈ Σ∗ w|w| ∈ L .
|w|
(b) replog(L) = w ∈ Σ∗ w2 ∈ L .
(c) repflog(L) = w ∈ Σ∗ w F|w| ∈ L , where Fn is the nth Fibonacci number.
[Hint: The NFAs for these languages use a LOT of states. Let M = (Σ, Q, s, A, δ) be a DFA
that accepts L. Imagine that you somehow know δ∗ (q, w) in advance, for every state q ∈ Q.
Ha, ha, ha! Mine is an evil laugh!]
21
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
The product of mental labor — science — always stands far below its value, because the
labor-time necessary to reproduce it has no relation at all to the labor-time required for its
original production. For example, a schoolboy can learn the binomial theorem in an hour.
— Karl Marx, Theories of Surplus Value (1863)
Imagine a piano keyboard, eh, 88 keys, only 88 and yet, and yet, hundreds of new melodies,
new tunes, new harmonies are being composed upon hundreds of different keyboards every
day in Dorset alone. Our language, tiger, our language: Hundreds of thousands of available
words, frillions of legitimate new ideas, so that I can say the following sentence and be
utterly sure that nobody has ever said it before in the history of human communication:
“Hold the newsreader’s nose squarely, waiter, or friendly milk will countermand
my trousers.” Perfectly ordinary words, but never before put in that precise order. A unique
child delivered of a unique mother.
— Stephen Fry, A Bit of Fry and Laurie, Series 1, Episode 3 (1989)
S→A A → 0A B → B1 C →"
S→B A → 0C B → C1 C → 0C 1
Normally we write grammars more compactly by combining the right sides of all rules for
each non-terminal into one list, with alternatives separated by vertical bars.1 For example, the
previous grammar can be written more compactly as follows:
S →A| B
A → 0A | 0C
B → B1 | C 1
C → " | 0C 1
1Yes, this means we now have three symbols ∪, +, and | with exactly the same meaning. Sigh.
For the rest of this lecture, I will almost always use the following notational conventions.
More generally, for any strings x, z ∈ (Σ ∪ Γ )∗ , we say that z derives from x , written x ∗ z,
if we can transform x into z by applying a finite sequence of production rules, or more formally,
if either
• x = z, or
• x y and y ∗ z for some string y ∈ (Σ ∪ Γ )∗ .
L(w) := {x ∈ Σ∗ | w ∗ x} .
The language generated by a context-free grammar G, denoted L(G), is the language of its
starting non-terminal. Finally, a language is context-free if it is generated by some context-free
grammar.
Context-free grammars are sometimes used to model natural languages. In this context, the
symbols are words, and the strings in the languages are sentences. For example, the following
grammar describes a simple subset of English sentences. (Here I diverge from the usual notation
conventions. Strings in 〈angle brackets〉 are non-terminals, and regular strings are terminals.)
2
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
• Each leaf is labeled with a terminal or the empty string ". Concatenating these in order
from left to right yields the string w.
• Each internal node is labeled with a non-terminal. In particular, the root is labeled with
the start non-terminal S.
• For each internal node v, there is a production rule A → ω where A is the label of v and
the symbols in ω are the labels of the children of v in order from left to right.
In other words, the production rules of the grammar describe template trees that can be
assembled into larger parse trees. For example, the simple grammar on the previous page has
the following templates, one for each production rule:
S S A A B B C C
A B 0 A 0 C B 1 C 1 " 0 C 1
The same grammar gives us the following parse tree for the string 000011:
S
A
0 A
0 C
0 C 1
0 C 1
"
Our more complicated “English” grammar gives us parse trees like the following:
〈sentence〉
my
Any parse tree that contains at least one node with more than one non-terminal child corresponds
to several different derivations. For example, when deriving an “English” sentence, we have a
choice of whether to expand the first 〈noun phrase〉 (“your furious green time lord”) before or
after the second (“my dog’s trousers”).
3
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
A string w is ambiguous with respect to a grammar if there is more than one parse tree for w,
and a grammar G is ambiguous is some string is ambiguous with respect to G. Neither of the
previous example grammars is ambiguous. However, the grammar S → 1 | S +S is ambiguous,
because the string 1+1+1+1 has five different parse trees:
S S S S S
S + S S + S S + S S + S
S + S
S + S 1 S + S 1 1 S + S 1 S + S
S + S S + S
S + S 1 1 S + S S + S 1 1 S + S
1 1 1 1 1 1 1 1 1 1 1 1
S →A| B A → 0A | 0C B → B1 | C 1 C → " | 0 C 1.
Since the production rules for non-terminal C do not refer to any other non-terminal, let’s begin
by figuring out L(C). After playing around with the smaller grammar C → " | 0C 1 for a few
seconds, you can probably guess that its language is {", 01, 0011, 000111, . . .}, that is, the
set all of strings of the form 0n 1n for some integer n. For example, we can derive the string
00001111 from the start non-terminal S using the following derivation:
0 C 1
0 C 1
0 C 1
0 C 1
"
In fact, it is not hard to prove by induction that L(C) = {0n 1n | n ≥ 0} as follows. As usual when
we prove that two sets X and Y are equal, the proof has two stages: one stage to prove X ⊆ Y ,
the other to prove Y ⊆ X .
Proof: Fix an arbitrary non-negative integer n. Assume that C ∗ 0k 1k for every non-negative
integer k < n. There are two cases to consider.
4
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
• If n = 0, then 0n 1n = ". The rule C → " implies that C " and therefore C ∗ ".
• Suppose n > 0. The inductive hypothesis implies that C ∗ 0n−1 1n−1 . Thus, the rule
C → 0C 1 implies that C 0C 1 ∗ 0(0n−1 1n−1 )1 = 0n 1n .
Lemma 5.2. For every string w ∈ L(C), we have w = 0n 1n for some non-negative integer n.
Proof: Fix an arbitrary string w ∈ L(C). Assume that for any string x ∈ L(C) such that |x| < |w|,
we have x = 0k 1k for some non-negative integer k. There are two cases to consider, one for each
production rule.
• If w = ", then w = 00 10 .
• Otherwise, w = 0 x 1 for some string x ∈ L(C). Because |x| = |w| − 2 < |w|, the inductive
hypothesis implies that x = 0k 1k for some integer k. Then we have w = 0k+1 1k+1 .
The first proof uses induction on strings, following the boilerplate proposed in the very first
lecture; in particular, the case analysis mirrors the recursive definition of “string”. The second
proof uses structural induction on the parse tree of the string 0n 1n ; the case analysis mirrors
the recursive definition of the language of S, as described by the production rules. In both
proofs, as in every proof by induction, the inductive hypothesis is “Assume there is no smaller
counterexample.”
Similar analysis implies that L(A) = {0m 1n | m > n} and L(B) = {0m 1n | m < n}, and
therefore L(S) = {0m 1n | m 6= n}.
There is an important subtlety in the proof of Lemma 5.2. The proof is written as induction on
the length of the string w; unfortunately, this induction pattern does not work for all context-free
grammars. Consider the following ambiguous grammar
S → " | SS | 0S 1 | 1S 0.
A bit of experimentation should convince you that L(S) is the language of all binary strings with
the same number of 0s and 1s. We cannot use the string-induction boilerplate for this grammar,
because there are arbitrarily long2 derivations of the form
S SS S SS S SS SS · · · w,
which alternately apply the productions S → SS and S → ". Specifically, even if we knew that
our arbitrary string w can be written as x y for some strings x, y ∈ L(S), we cannot guarantee
that |x| < |w| and | y| < |w|, to we cannot apply the standard string-induction hypothesis.
However, we can still argue inductively about this grammar, by considering a minimum-length
derivation of w, and basing the case analysis on the first production in this derivation. Here’s
an example of this induction boilerplate in action, with the modified boilerplate language
highlighted.
5
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
Lemma 5.3. For every string w ∈ L(S), we have #(0, w) = #(1, w).
• Suppose the first production is S → ". Then w = " and therefore #(0, w) = #(1, w) = 0 by
definition.
• Suppose the first production is S → SS. Then w = x y for some strings x, y ∈ L(S). Both
x and y must be non-empty; otherwise, we could shorten our derivation of w. Thus,
both x and y are shorter than w. The inductive hypothesis implies #(0, x) = #(1, x) and
#(0, y) = #(1, y), so #(0, w) = #(0, x) + #(0, y) = #(1, x) + #(1, y) = #(1, w).
• Suppose the first production is S → 0S 1. Then w = 0 x 1 for some string x ∈ L(S). The
inductive hypothesis implies #(0, x) = #(1, x) so #(0, w) = #(0, x) + 1 = #(1, x) + 1 =
#(1, w).
• Finally, suppose the first production is S → 1S 0. Then w = 1 x 0 for some string x ∈ L(S).
The inductive hypothesis implies #(0, x) = #(1, x) so #(0, w) = #(0, x) + 1 = #(1, w) +
1 = #(1, w).
Another (more traditional) way to handle this issue is to fix an arbitrary derivation, and then
induct on the length of the derivation, rather than the length of the string itself. The case analysis
is still based on the first production in the chosen derivation.
In fact, this subtlety only matters for grammars that either contain a nullable non-terminal A
such that A ∗ " or equivalent nonterminals A and B such that A ∗ B and B ∗ A. We describe
algorithms to identify these pathologies and remove them from the grammar (without changing
its language) in Section 5.9 below.
Another pitfall in induction proofs for context-free languages is that non-terminals may invoke
each other. Consider, for example, the grammar
Because each non-terminal appears on the right side of a production rule for the other, we must
argue about L(S) and L(A) simultaneously.
Proof: We actually prove simultaneously that L(S) = (01)∗ and L(A) = (10)∗ .
First, we claim that for any non-negative integer n, we have (01)n ∈ L(S) and (10)n ∈ L(A).
Let n be an arbitrary non-negative integer, and assume, for all non-negative integers m < n, that
(01)m ∈ L(S) and (10)m ∈ L(A). There are two cases to consider.
• If n = 0, the production rules S → " and A → " immediately imply S " = (01)n and
A " = (10)n .
6
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
• Suppose n > 0. We easily observe that (01)n = 0(10)n−1 1, so the production rule S → 0A1
and inductive hypothesis imply S 0A1 ∗ (01)n . Symmetrically, (10)n = 1(01)n−1 0, so
the production rule A → 1S 0 and the inductive hypothesis implies A 1S 0 ∗ (10)n .
Next we claim that for every string w ∈ L(S), we have w = (01)n for some non-negative
integer n, and for every string w ∈ L(A), we have w = (10)n for some non-negative integer n.
The proof requires two stages.
• Let w be an arbitrary string in L(S), and assume for all x ∈ L(A) such that |x| < |w| that
x = (10)n for some non-negative integer n. There are two cases to consider.
• Let w be an arbitrary string in L(A), and assume for all x ∈ L(S) such that |x| < |w| that
x = (01)n for some non-negative integer n. There are two cases to consider.
Together these two claims imply L(S) = (01)∗ and L(A) = (10)∗ , as required.
S → 0S 0 | 1S 1 | 0 | 1 | "
S → 0S 0 | 1S 1 | 0 Z 1 | 1 Z 0
Z → " | 0Z | 1Z
S → 0S 1 | 1S 0 | SS | "
A non-empty string w has the same number of 0s and 1s if and only one of the following
conditions holds:
– We can write w = x y for some non-empty strings x and y such that #(0, x) = #(1, x)
and #(0, y) = #(1, y).
7
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
– #(0, x) > #(1, x) for every non-empty proper prefix x of w. In this case, w = 0z 1
for some string z with #(0, z) = #(1, z).
– #(0, x) < #(1, x) for every non-empty proper prefix x of w. In this case, w = 1z 0
for some string z with #(0, z) = #(1, z).
• Strings in {0, 1}∗ with the same number of 0s and 1s, again:
S → 0S 1S | 1S 0S | "
Let w be any non-empty string such that #(0, w) = #(1, w), let x be the shortest non-empty
prefix of w such that #(0, x) = #(1, x), and let y be the complementary suffix of w, so
w = x y. It is not hard to prove that x begins and ends with different symbols, so either
w = 0z 1 y or w = 1z 0 y, where #(0, y) = #(1, y) and #(0, z) = #(1, z).
• Strings in {0, 1}∗ in which the number of 0s is greater than or equal to the number of 1s:
We have to different grammars, each constructed from a grammar for strings with equal 0s
and 1s by either dropping the 1 or keeping the 1 from the right side of each production rule
containing a 1. For example, we split the production rule S → 0S 1 in the first grammar
into two production rules S → 0S 1 and S → 0S.
If we add the trivial production S → 0 to the first grammar, we can remove two
redundant productions to get the simpler grammar
S → 0S 1 | 1S 0 | SS | 0 | "
S→O|I (different)
O → E 0O | E 0 E (more 0s)
I → E1I | E1E (more 1s)
E → 0E1E | 1E0E | " (equal)
– E generates all strings with the same number of 0s and 1s, as in the previous example.
– I generates all strings with more 1s than 0s. Any such string can be decomposed into
its longest prefix with the same number of 0s and 1s (E), followed by a 0, followed
by a suffix with at least as many 0s as 1s (I or E).
– Symmetrically, O generates all strings with more 0s than 1s.
– Finally, S generates all strings with different numbers of 0s and 1s. Any such string
either has more 0s (O) or more 1s (I)
S → (S ) | SS | " or S → (S )S | "
Here we have two grammars for the same language. The first one uses simpler productions,
and is a bit closer to the natural recursive definition. However, the first grammar is
8
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
ambiguous — consider the string ()()() — while the second grammar is not. The second
grammar decomposes any balanced string of parentheses into its shortest non-empty
balanced prefix, which must start with ( and end with ), and the remaining suffix, which
must be balanced.
S → L | RX (unbalanced)
L → E( L | E(E (more left parens)
R → E )R | E ) E (more right parens)
E → " | (E)E | )E(E (equal left and right)
X → " | (X | )X (anything)
A string w of parens is balanced if and only if both (a) w has the same number of left and
right parens and (b) no prefix of w has more right parens than left parens. (Proving this
fact is a good homework exercise.) Thus, a string w of parens is unbalanced if and only if
either w has more left parens than right parens or some prefix of w has more right parens
than left parens.
• Arithmetic expressions, possibly with redundant parentheses, over the variables X and Y:
E → E+T | T (expressions)
T → T×F | F (terms)
F → (E) | X | Y (factors)
Every Eexpression is a sum of T erms, every T erm is a product of F actors, and every F actor
is either a variable or a parenthesized Eexpression.
S → T | T +S (Regular expressions)
T → F | FT (Terms = summable expressions)
F → Ø | W | ( T +S ) | X * | (Y )* (Factors = concatenable expressions)
X →Ø|3|0|1 (Directly starrable expressions)
Y → T +S | F • T | X * | (Y )* | Z Z (Starrable expressions needing parens)
W →3|Z (Words = strings)
Z → 0 | 1 | ZZ (Non-empty strings)
Every regular expression is a sum of terms; every term is a concatenation of factors. Every
factor is either the empty-set symbol, a string, a nontrivial sum of terms in parens, or a
starred expression. The expressions Ø*, 3*, 0*, and 1* require no parentheses; otherwise,
the starred subexpression is either a nontrivial sum of terms, a nontrivial concatenation of
factors, a starred expression, or a string of length 2 or more.
The “epsilon” symbol 3 in the production rules for W and Z does not represent the
empty string per se, but rather an actual symbol that might appear in a regular expression.
The empty string is not a regular expression, but the one-symbol string 3 is a regular
expression that represents the set containing only the empty string!
9
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
The final grammar illustrates an important subtlety for certain applications of context-free
grammars. This grammar is considerably more complicated than one might initially expect from
the definition of regular languages. It’s tempting to suggest a much simpler grammar like
S → Ø | 3 | 0 | 1 | S +S | SS | S * | (S )
but this is incorrect! This grammar does correctly generate all regular expressions as raw strings,
but it allows parse trees that do not respect the meaning of the regular expression. For example,
this “simpler” grammar can parse the regular expression string 0*+1* in two different ways:
S
S
S*
S +S
S +S *
S* + S*
S* + 1
0 * 1 *
0 *
The first tree correctly parses the regular expression string 1*+0* as the expression (1∗ ) + (0∗ )
but without the redundant parentheses. The second tree incorrectly parses the same string as
(1∗ + 0)∗ , which describes a very different regular language!
10
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
S →A| B A → 0A | 0 C B → B1 | C 1 C → " | 0C 1
SKA|B$AK0A|0C$BKB1|C1$CK3|0C1$
We can further encode any such string as a binary string by associating each symbol in the
set Σ ∪ Γ ∪ {3, K, |, $} with a different binary substring. Specifically, if we encode each of the
grammar symbols 3, K, |, $ as a string of the form 11∗ 0, each terminal in Σ as a string of the
form 011∗ 0, and each non-terminal as a string of the form 0011∗ 0, we can unambiguously
recover the grammar from the encoding. For example, applying the code
3 7→ 10 0 7→ 010 S 7→ 0010
K 7→ 110 1 7→ 0110 A 7→ 00110
| 7→ 1110 B 7→ 001110
$ 7→ 11110 C 7→ 0011110
00101100011011100011101111000110
11001000110111001000111101111000
11101100011100110111000111100110
11110001111011010111001000111100
11011110.
Adding a 1 to the start of this bit string gives us the binary encoding of the integer
102 231 235 533 163 527 515 344 124 802 467 059 875 038.
Our construction guarantees that two different context-free grammars over the same alphabet
(ignoring changing the names of the non-terminals) yield different positive integers. Thus, the
set of context-free grammars over any alphabet is at most as large as the set of integers, and is
therefore countably infinite. (Most integers are not encodings of context-free grammars, but that
only helps us.) It follows that the set of all context-free languages over any fixed alphabet is
also countably infinite. But we already showed that the set of all languages over any alphabet is
uncountably infinite. So almost all languages are non-context-free!
There are techniques for proving that specific languages are not context-free, just as there
are for proving certain languages are not regular; unfortunately, they are beyond the scope of
this course. In particular, the {0n 1n 0n | n ≥ 0} is not context-free. (In fact, this is the canonical
example of a non-context-free language.)
11
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
?
5.7 Recursive Automata
All the flavors of finite-state automata we have seen so far describe/encode/accept/compute
regular languages; these are precisely the languages that can be constructed from individual
strings by union, concatenation, and unbounded repetition. Just as context-free grammars are
recursive generalizations of regular expressions, we can define a class of machines called recursive
automata, which generalize (nondeterministic) finite-state automata. Recursive automata were
introduced by Walter Woods in 1970 for natural language parsing; Wodds’ terminology recursive
transition networks is more common among computational linguists.
Formally, a recursive automaton consists of the following components:
• A non-empty finite set Σ, called the input alphabet
• Another non-empty finite set N , disjoint from Σ, whose elements are called module names
• A start name S ∈ N
• A set M = {MA | A ∈ N } of NFAs, called modules, over the alphabet Σ ∪ N . Each module
MA has the following components:
Equivalently,
S we have a single global transition function δ : Q × (Σ ∪ {"} ∪ N ) → 2Q , where
Q = A∈N Q A, such that for any name A and any state q ∈ Q A we have δ(q) ⊆ Q A. Machine MS is
called the main module.
A configuration of a recursive automaton is a triple (w, q, s), where w is a string in Σ∗ called
the input, q is a state in Q called the local state, and σ is a string in Q∗ called the stack. The
module containing the local state q is called the active module. A configuration can be changed
by three types of transitions.
• A read transition consumes the first symbol in the input and changes the local state within
the active module, just like a standard NFA.
• An epsilon transition changes the local state within the active module, without consuming
any input characters, just like a standard NFA.
• A call transition chooses a module name A, pushes some state in δ(q, A) onto the stack,
and then changes the local state to sA (thereby changing the active module to MA), without
consuming any input characters.
• Finally, if the current state is the terminal state of the active module and the stack is
non-empty, a return transition pops the top state off the stack and makes it the new
local state (thereby possibly changing the active module), without consuming any input
characters.
Symbolically, we can describe these transitions as follows:
read: ax, q, σ 7−→ x, q0 , σ for some q0 ∈ δ(q, a)
epsilon: w, q, σ 7−→ w, q0 , σ for some q0 ∈ δ(q, ")
call: w, q, σ 7−→ w, sA, q0 · σ for some A ∈ N and some q0 ∈ δ(q, A)
return: w, t A, q · σ 7−→ w, q, σ
12
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
A recursive automaton accepts a string w if there is a finite sequence of transitions starting at the
start configuration (w, sS , ") and ending at the terminal configuration (", t S , ").
α1 α2 α3 α`
sA = q0 −→ q1 −→ q2 −→ · · · −→ q` = t A
For example, the following recursive automaton accepts the language {0m 1n | m 6= n}. The
recursive automaton has two component modules; the start machine named S and a “subroutine”
named E (for “equal”) that accepts the language {0n 1n | n ≥ 0}. White arrows indicate recursive
transitions. The large arrow into each module indicates that module’s start state; the large arrow
leading out of each module indicates that modules terminal state.
S E
E ε
1
0 1 0 1
0
E E
Proof:
ÆÆÆ Direct construction from the CFG, with one module per nonterminal.
13
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
S → 0A | B1
A → 0A | E
B → B1 | E
E → " | 0E0
ÆÆÆ Figure!
• epsilon: For any two states p and q such that p ∈ δ(q, "), the grammar contains the
production rule [q] → [p].
• call: Each name A and each pair of states states p and q such that p ∈ δ(q, A), the grammar
contains the production rule [q] → [sA][p].
• return: Each name A, the grammar contains the production rule [t A] → ".
Finally, the starting nonterminal of G is [sS ], which corresponds to the start state of the main
module.
We can now argue inductively that the grammar G and the recursive automaton R describe
the same language. Specifically, any sequence of transitions in R from (w, sS , ") to (", t S , ") can be
transformed mechanically into a derivation of w from the nonterminal [sS ] in G. Symmetrically,
the leftmost derivation of any string w in G can be mechanically transformed into an accepting
sequence of transitions in R. We omit the straightforward but tedious details.
For example, the recursive automaton on the previous page gives us the following context-free
grammar. To make the grammar more readable, I’ve renamed the nonterminals corresponding to
start and terminal states: S = [sS ], T = [t S ], and E = [s E ] = [t E ]:
S → EA | 0B E → " | 0X
A → 1A | 1 T X → EY
B → 0B | E T Y → 1Z
T →" Z→E
Our earlier proofs imply that we can forbid "-transitions or even allow regular-expression
transitions in our recursive automata without changing the set of languages they accept.
14
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
• The starting non-terminal S does not appear on the right side of any production rule.
• The starting non-terminal S may have the production rule S → ".
• The right side of every other production rule is either a single terminal symbol or a string
of exactly two non-terminals—that is, every other production rule has the form A → BC or
A → a.
A particularly attractive feature of CNF grammars is that they yield full binary parse trees; in
particular, every parse tree for a string of length n > 0 has exactly 2n − 1 non-terminal nodes.
Consequently, any string of length n in the language of a CNF grammar can be derived in exactly
2n − 1 production steps. It follows that we can actually determine whether a string belongs to
the language of a CNF grammar by brute-force consideration of all possible derivations of the
appropriate length.
For arbitrary context-free grammars, there is no similar upper bound on the length of a
derivation, and therefore no similar brute-force membership algorithm, because the grammar
may contain additional "-productions of the form A → " and/or unit productions of the form
A → B, where both A and B are non-terminals. Unit productions introduce nodes of degree 1
into any parse tree, and "-productions introduce leaves that do not contribute to the word being
parsed.
Fortunately, it is possible to determine membership in the language of an arbitrary context-free
grammar, thanks to the following theorem. Two context-free grammars are equivalent if they
define the same language.
Moreover, there are algorithms to automatically convert any context-free grammar into Chomsky
normal form. Unfortunately, these conversion algorithms are quite complex, but for most
applications of context-free grammars, the details of the conversion are unimportant—it’s enough
to know that the algorithms exist. For the sake of completeness, however, I will describe one
such conversion algorithm in the next section.
?
5.9 CNF Conversion Algorithm
I’ll actually prove a stronger statement: Not only can we convert any context-free grammar into
Chomsky normal form, but we can do so quickly. We analyze the running time of our conversion
algorithm in terms of the total length of the input grammar, which is just the number of symbols
needed to write down the grammar. Up to constant factors, the total length is the sum of the
lengths of the production rules.
Theorem 5.7. Given an arbitrary context-free grammar with total length L, we can compute an
equivalent grammar in Chomsky normal form with total length O(L 2 ) in O(L 2 ) time.
15
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
0. Add a new starting non-terminal. Add a new non-terminal S 0 and a production rule S 0 → S,
where S is the starting non-terminal for the given grammar. S 0 will be the starting non-terminal
for the resulting CNF grammar. (In fact, this step is necessary only when S ∗ ", but at this point
in the conversion process, we don’t yet know whether that’s true.)
1. Decompose long production rules. For each production rule A → ω whose right side w has
length greater than two, add new production rules of length two that still permit the derivation
A ∗ ω. Specifically, suppose ω = αχ for some symbol α ∈ Σ ∪ Γ and string χ ∈ (Σ ∪ Γ )∗ . The
algorithm replaces A → ω with two new production rules A → αB and B → χ, where B is a new
non-terminal, and then (if necessary) recursively decomposes the production rule B → χ. For
example, we would replace the long production rule A → 0BC 1C B with the following sequence
of short production rules, where each Ai is a new non-terminal:
This stage can significantly increase the number of non-terminals and production rules, but it
increases the total length of all production rules by at most a small constant factor.3 Moreover,
for the remainder of the conversion algorithm, every production rule has length at most two. The
running time of this stage is O(L).
Nullables(Σ, Γ , R, S):
Γ" ← ∅ 〈〈known nullable non-terminals〉〉
done ← False
while ¬done
done ← True
for each non-terminal A ∈ Γ \ Γ"
for each production rule A → ω
if ω ∈ Γ∗"
add A to Γ"
done ← False
return Γ"
At this point in the conversion algorithm, if S 0 is not identified as nullable, then we can safely
remove it from the grammar and use the original starting nonterminal S instead.
As written, Nullables runs in O(nL) = O(L 2 ) time, where n is the number of non-terminals
in Γ . Each iteration of the main loop except the last adds at least one non-terminal to Γ" , so the
3In most textbook descriptions of the CFG conversion algorithm, this stage is performed last, after removing
"-productions and unit productions. But with the stages in that traditional order, removing "-productions could
exponentially increase the length of the grammar in the worst case! Consider the production rule A → (BC)k , where B
is nullable but C is not. Decomposing this rule first and then removing "-productions introduces about 3k new rules;
whereas, removing "-productions first introduces 2k new rules, most of which then must then be further decomposed!
16
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
algorithm halts after at most n + 1 ≤ L iterations, and in each iteration, we examine at most L
production rules. There is a faster implementation of Nullables that runs in O(n + L) = O(L)
time,⁴ but since other parts of the conversion algorithm already require O(L 2 ) time, we needn’t
bother.
3. Eliminate "-productions. First, remove every production rule of the form A → ". Then for
each production rule A → w, add all possible new production rules of the form A → w0 , where w0
is a non-empty string obtained from w by removing one nullable non-terminal. For example, if if
the grammar contained the production rule A → BC, where B and C are both nullable, we would
add two new production rules A → B | C. Finally, if the starting nonterminal S 0 was identified as
nullable in the previous stage, add the production rule S 0 → "; this will be the only "-production
in the final grammar. This phase of the conversion runs in O(L) time and at most triples the
number of production rules.
4. Merge equivalent non-terminals. We say that two non-terminals A and B are equivalent if
they can be derived from each other: A ∗ B and B ∗ A. Because we have already removed
"-productions, any such derivation must consist entirely of unit productions. For example, in the
grammar
S → B | C, A → B | D | C C | 0, B → C | AD | 1, C → A | DA, D → BA | C S,
non-terminals A, B, C are all equivalent, but S is not in that equivalence class (because we cannot
derive S from A) and neither is D (because we cannot derive A from D).
Construct a directed graph G whose vertices are the non-terminals and whose edges correspond
to unit productions, in O(L) time. Then two non-terminals are equivalent if and only if they are
in the same strong component of G. Compute the strong components of G in O(L) time using,
for example, the algorithm of Kosaraju and Sharir. Then merge all the non-terminals in each
equivalence class into a single non-terminal. Finally, remove any unit productions of the form
A → A. The total running time for this phase is O(L). Starting with our example grammar above,
merging B and C with A and removing the production A → A gives us the simpler grammar
S → A, A → AA | D | DA | 0 | 1, D → AA | AS.
We could further simplify the grammar by merging all non-terminals reachable from S using only
unit productions (in this case, merging non-terminals S and S), but this further simplification is
unnecessary.
5. Remove unit productions. Once again, we construct a directed graph G whose vertices are
the non-terminals and whose edges correspond to unit productions, in O(L) time. Because no
two non-terminals are equivalent, G is acyclic. Thus, using topological sort, we can index the
non-terminals A1 , A2 , . . . , An such that for every unit production Ai → A j we have i < j, again
in O(L) time; moreover, we can assume that the starting non-terminal is A1 . (In fact, both the
dag G and the linear ordering of non-terminals was already computed in the previous phase!!)
Then for each index j in decreasing order, for each unit production Ai → A j and each
production A j → ω, we add a new production rule Ai → ω. At this point, all unit productions are
⁴Consider the bipartite graph whose vertices correspond to non-terminals and the right sides of production rules,
with one edge per rule. The faster algorithm is a modified breadth-first search of this graph, starting at the vertex
representing ".
17
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
redundant and can be removed. Applying this algorithm to our example grammar above gives us
the grammar
S → AA | AS | DA | 0 | 1, A → AA | AS | DA | 0 | 1, D → AA | AS.
In the worst case, each production rule for An is copied to each of the other n − 1 non-
terminals. Thus, this phase runs in Θ(nL) = O(L 2 ) time and increases the length of the grammar
to Θ(nL) = O(L 2 ) in the worst case.
This phase dominates the running time of the CNF conversion algorithm. Unlike previous
phases, no faster algorithm for removing unit transformations is known! There are grammars of
length L with unit productions such that any equivalent grammar without unit productions has
length Ω(L 1.499999 ) (for any desired number of 9s), but this lower bound does not rule out the
possibility of an algorithm that runs in only O(L 3/2 ) time. Closing the gap between Ω(L 3/2−" )
and O(L 2 ) has been an open problem since the early 1980s!
This completes the conversion to Chomsky normal form! As claimed, the total running time
of the algorithm is O(L 2 ), and the total length of the output grammar is also O(L 2 ).
To see the conversion algorithm in action, let’s apply these stages one at a time to our very
first example grammar for the language {0m 1n | m 6= n}:
S →A| B A → 0A | 0 C B → B1 | C 1 C → " | 0C 1
0. Add a new starting non-terminal S 0 .
S0 → S S →A| B A → 0A | 0 C B → B1 | C 1 C → " | 0C 1
2. Identify C as the only nullable non-terminal. Because S 0 is not nullable, remove the
production rule S 0 → S.
3. Eliminate the "-production C → ".
S →A| B A → 0A | 0 C | 0 B → B1 | C 1 | 1 C → 0D D → C1 | 1
6. Finally, protect the terminals 0 and 1 to obtain the final CNF grammar.
S → EA | EC | BF | C F | 0 | 1
A → EA | EC | 0 B → BF | C F | 1
C → ED D → CF | 1
E→0 F →1
18
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
Exercises
1. Describe context-free grammars that generate each of the following languages. The
function #(x, w) returns the number of occurrences of the substring x in the string w.
For example, #(0, 101001) = 3 and #(010, 1010100011) = 2. These are not listed in
order of increasing difficulty.
2. Describe recursive automata for each of the languages in problem 1. (“Describe” does not
necessarily mean “draw”!)
4. Consider a generalization of context-free grammars that allows any regular expression over
Σ ∪ Γ to appear on the right side of a production rule. Without loss of generality, for each
non-terminal A ∈ Γ , the generalized grammar contains a single regular expression R(A). To
19
Models of Computation Lecture 5: Context-Free Languages and Grammars [Sp’18]
apply a production rule to a string, we replace any non-terminal A with an arbitrary word
in the language described by R(A). As usual, the language of the generalized grammar is
the set of all strings that can be derived from its start non-terminal.
For example:, the following generalized context-free grammar describes the language
of all regular expressions over the alphabet {0, 1}:
Here is a parse tree for the regular expression 0+1(10*1+01*0)*10* (which represents
the set of all binary numbers divisible by 3):
T + T
0 F F F F
1 ( S ) * 1 0 *
T + T
F F F F F F
1 0 * 1 0 1 * 0
20
Models of Computation Lecture 6: Turing Machines [Fa’16]
6 Turing Machines
In 1936, a few months before his 24th birthday, Alan Turing launched computer science as a
modern intellectual discipline. In a single remarkable paper, Turing provided the following
results:
• A description of a single universal machine that can be used to compute any function
computable by any other Turing machine.
• A proof that no Turing machine can solve the halting problem—Given the formal description
of an arbitrary Turing machine M , does M halt or run forever?
• A proof that no Turing machine can determine whether an arbitrary given proposition
is provable from the axioms of first-order logic. This is Hilbert and Ackermann’s famous
Entscheidungsproblem (“decision problem”).
• Compelling arguments1 that his machines can execute arbitrary “calculation by finite
means”.
Although Turing did not know it at the time, he was not the first to prove that the Entschei-
dungsproblem had no algorithmic solution. The first such proof is implicit in the work of Kurt
Gödel; in lectures on his incompleteness theorems2 at Princeton in 1934, Gödel described a
model of general recursive functions, which he largely credited to Jacques Herbrand.3 Gödel’s
incompleteness theorem can be viewed as a proof that some propositions cannot be proved using
general recursive functions. However, Gödel viewed his definition as a “heuristic principle” rather
than an accurate model of effective computation, or even a complete definition of recursion.
The first published proof was written by Alonzo Church and published just a new months
before Turing’s paper, using another different model of computation, now called the untyped
λ-calculus. Turing and Church developed their results independently; indeed, Turing rushed
1As Turing put it, “All arguments which can be given are bound to be, fundamentally, appeals to intuition, and for
this reason rather unsatisfactory mathematically.” The claim that anything that can be computed can be computing
using Turing machines is now known as the Church-Turing thesis.
2which he published at the ripe old age of 25
3Herbrand was a brilliant French mathematician who was killed in a mountain-climbing accident at the age of 23.
the submission of his own paper immediately after receiving a copy of Church’s paper, pausing
only long enough to prove that any function computable via λ-calculus can also be computed
by a Turing machine and vice versa.⁴ Church was the referee for Turing’s paper; between the
paper’s submission and its acceptance, Turing was admitted to Princeton as a PhD student, where
Church became his advisor. He finished his PhD two years later.
Informally, Turing described an abstract machine with a finite number of internal states that
has access to “memory” in the form of a tape. The tape consists of a semi-infinite sequence of
cells, each containing a single symbol from some arbitrary finite alphabet. The Turing machine
can access the tape only through its head, which is positioned over a single cell. Initially, the tape
contains an arbitrary finite input string followed by an infinite sequence of blanks, and the head
is positioned over the first cell on the tape. In a single iteration, the machine reads the symbol in
that cell, possibly write a new symbol into that cell, possibly changes its internal state, possibly
moves the head to a neighboring cell, and possibly halts. The precise behavior of the machine at
each iteration is entirely determined by its internal state and the symbol that it reads. When the
machine halts, it indicates whether it has accepted or rejected the original input string.
Write O
Move left
T O R T U R I N G M A C H I N E
Write N
Move right
T O R T U R I N G M A C H I N E
Write U
Move right
N O R T U R I N G M A C H I N E
Halt and
accept!
N U R T U R I N G M A C H I N E
2
Models of Computation Lecture 6: Turing Machines [Fa’16]
random-access model can require arbitrarily many steps on a Turing machine. Worse, seemingly
minor variations in the precise definition of “Turing machine” can have significant impact on
problem complexity. As a simple example (which will make more sense later), we can reverse
a string of n bits in O(n) time using a two-tape Turing machine, but the same task provably
requires Ω(n2 ) time on a single-tape machine.
But here we are not interested in finding fast algorithms, or indeed in finding algorithms
at all, but rather in proving that some problems cannot be solved by any computational means.
Such a bold claim requires a formal definition of “computation” that is simple enough to support
formal argument, but still powerful enough to describe arbitrary algorithms. Turing machines
are ideal for this purpose. In particular, Turing machines are powerful enough to simulate other
Turing machines, while still simple enough to let us build up this self-simulation from scratch,
unlike more complex but efficient models like the standard random-access machine
(Arguably, self-simulation is even simpler in Church’s λ-calculus, or in Schönfinkel and
Curry’s combinator calculus, which is one of many reasons those models are more common in the
design and analysis of programming languages than Turing machines. Those models are much
more abstract; in particular, they are harder to show equivalent to standard iterative models of
computation.)
• An arbitrary finite set Γ with at least two elements, called the tape alphabet.
• An arbitrary symbol ∈ Γ , called the blank symbol or just the blank.
• An arbitrary nonempty subset Σ ⊆ (Γ \ {}), called the input alphabet.
• Another arbitrary finite set Q whose elements are called states.
• Three distinct special states start, accept, reject ∈ Q.
• A transition function δ : (Q \ {accept, reject}) × Γ → Q × Γ × {−1, +1}.
3
Models of Computation Lecture 6: Turing Machines [Fa’16]
The initial configuration is (start, w, 0) for some arbitrary (and possibly empty) input string
w ∈ Σ∗ . If M eventually reaches the accept state—more formally, if (start, w, 0) ⇒∗ (accept, x, i)
for some string x ∈ Γ ∗ and some integer i—we say that M accepts the original input string w.
Similarly, if M eventually reaches the reject state, we say that M rejects w. We must emphasize
that “rejects” and “does not accept” are not synonyms; if M crashes or runs forever, then M
neither accepts nor rejects w.
We distinguish between two different senses in which a Turing machine can “accept” a
language. Let M be a Turing machine with input alphabet Σ, and let L ⊆ Σ∗ be an arbitrary
language over Σ.
• M recognizes or accepts L if and only if M accepts every string in L but nothing else. A
language is recognizable (or semi-computable or recursively enumerable) if it is recognized
by some Turing machine.
• M decides L if and only if M accepts every string in L and rejects every string in Σ∗ \ L.
Equivalently, M decides L if and only if M recognizes L and halts (without crashing) on all
inputs. A language is decidable (or computable or recursive) if it is decided by some Turing
machine.
Trivially, every decidable language is recognizable, but (as we will see later), not every recognizable
language is decidable.
Γ = {0, 1, $, x,}
Σ = {0, 1}
Q = {start, seek1, seek0, reset, verify, accept, reject}
The transition function is described in the table on the next page; all unspecified transitions lead
to the reject state. The figure below shows a graphical representation of the same machine,
which resembles a drawing of a DFA, but with output symbols and actions specified on each edge.
For example, we indicate the transition δ(p, 0) = (q, 1, +1) by writing 0/1, +1 next to the arrow
from state p to state q.
$/$,+1
4
Models of Computation Lecture 6: Turing Machines [Fa’16]
δ( p , a) = ( q , b, ∆ ) explanation
δ( start , 0) = ( seek1 , $, +1) mark first 0 and scan right
δ( start , x) = ( verify , $, +1) looks like we’re done, but let’s make sure
δ(seek1, 0) = ( seek1 , 0, +1) scan rightward for 1
δ(seek1, x) = ( seek1 , x, +1)
δ(seek1, 1) = ( seek0 , x, +1) mark 1 and continue right
δ(seek0, 1) = ( seek0 , 1, +1) scan rightward for 0
δ(seek0, x) = ( seek0 , x, +1)
δ(seek0, 0) = ( reset , x, +1) mark 0 and scan left
δ( reset , 0) = ( reset , 0, −1) scan leftward for $
δ( reset , 1) = ( reset , 1, −1)
δ( reset , x) = ( reset , x, −1)
δ( reset , $) = ( start , $, +1) step right and start over
δ( verify , x) = ( verify , $, +1) scan right for any unmarked symbol
δ( verify , ) = (accept, , −1) success!
The transition function for a Turing machine that decides the language {0n 1n 0n | n ≥ 0}.
Finally, we trace the execution of this machine on two input strings: 001100 ∈ L and
00100 6∈ L. In each configuration, we indicate the position of the head using a small triangle
instead of listing the position explicitly. Notice that we automatically add blanks to the tape
string as necessary. Proving that this machine actually decides L—and in particular, that it never
crashes or infinite-loops—is a straightforward but tedious exercise in induction.
6.4 Variations
There are actually several formal models that all fall under the name “Turing machine”, each
with small variations on the definition we’ve given. Although we do need to be explicit about
which variant we want to use for any particular problem, the differences between the variants are
relatively unimportant. For any machine defined in one model, there is an equivalent machine in
each of the other models; in particular, all of these variants recognize the same languages and
decide the same languages. For example:
• Halting conditions. Some models allow multiple accept and reject states, which (depend-
ing on the precise model) trigger acceptance or rejection either when the machine enters
the state, or when the machine has no valid transitions out of such a state. Others include
only explicit accept states, and either equate crashing with rejection or do not define a
rejection mechanism at all. Still other models include halting as one of the possible actions
of the machine, in addition to moving left or moving right; in these models, the machine
accepts/rejects its input if and only if it halts in an accepting/non-accepting state.
• Actions. Some Turing machine models allow transitions that do not move the head, or
that move the head by more than one cell in a single step. Others insist that a single step of
the machine either writes a new symbol onto the tape or moves the head one step. Finally,
as mentioned above, some models include halting as one of the available actions.
5
Models of Computation Lecture 6: Turing Machines [Fa’16]
(start, 001100
Î
)
⇒ (seek1, $01100
Î
)
⇒ (seek1, $01100
Î
)
⇒ (seek0, $0x100
Î
)
⇒ (seek0, $0x100
Î
)
⇒ (reset, $0x1x0
Î
)
⇒ (reset, $0x1x0
Î
)
⇒ (reset, $0x1x0
Î
)
⇒ (reset, $0x1x0
Î
)
⇒ (start, $0x1x0
Î
)
⇒ (seek1, $$x1x0
Î
)
⇒ (seek1, $$x1x0
Î
)
⇒ (seek0, $$xxx0
Î
)
⇒ (seek0, $$xxx0)
Î
⇒ (reset, $$xxxx
Î
)
⇒ (reset, $$xxxx
Î
)
⇒ (reset, $$xxxx
Î
)
⇒ (reset, $$xxxx
Î
)
⇒ (start, $$xxxx
Î
)
⇒ (verify, $$$xxx)
Î
⇒ (verify, $$$$xx
Î
)
⇒ (verify, $$$$$x
Î
)
⇒ (verify, $$$$$$)
Î
⇒ (accept, $$$$$$
Î
) ⇒ accept!
The evolution of the example Turing machine on the input string 001100 ∈ L
(start, 00100
Î
)
⇒ (seek1, $0100
Î
)
⇒ (seek1, $0100
Î
)
⇒ (seek0, $0x00)
Î
⇒ (reset, $0xx0
Î
)
⇒ (reset, $0xx0)
Î
⇒ (reset, $0xx0
Î
)
⇒ (start, $0xx0
Î
)
⇒ (seek1, $$xx0
Î
)
⇒ (seek1, $$xx0
Î
)
⇒ (seek1, $$xx0Î
) ⇒ reject!
The evolution of the example Turing machine on the input string 00100 6∈ L
6
Models of Computation Lecture 6: Turing Machines [Fa’16]
• Beginning of the tape. Some models forbid the head to move past the beginning of the
tape, either by starting the tape with a special symbol that cannot be overwritten and
that forces a rightward transition, or by declaring that a leftward transition at position 0
leaves the head in position 0, or even by pure fiat—declaring any machine that performs a
leftward move at position 0 to be invalid.
To prove that any two of these variant “species” of Turing machine are equivalent, we must
show how to transform a machine of one species into a machine of the other species that accepts
and rejects the same strings. For example, let M = (Γ ,, Σ, Q, s, accept, reject, δ) be a Turing
machine with explicit accept and reject states. We can define an equivalent Turing machine
M 0 that halts only when it moves left from position 0, and accepts only by halting while in an
accepting state, as follows. We define the set of accepting states for M 0 as A = {accept} and
define a new transition function
(accept, a, −1) if q = accept
0
δ (q, a) := (reject, a, −1) if q = reject
δ(q, a) otherwise
6.5.1 Shifting
One basic operation that is used in many Turing machine constructions is shifting the input
string a constant number of steps to the right or to the left. For example, given any input
7
Models of Computation Lecture 6: Turing Machines [Fa’16]
string w ∈ {0, 1}∗ , we can compute the string 0w using a Turing machine with tape alphabet
Γ = {0, 1,}, state set Q = {0, 1, halt}, start state 0, and the following transition function:
δ(p, a) = ( q , b, ∆)
δ(0, 0) = ( 0 , 0, +1)
δ(0, 1) = ( 1 , 0, +1)
δ(0, ) = (halt, 0, +1)
δ(1, 0) = ( 0 , 1, +1)
δ(1, 1) = ( 1 , 1, +1)
δ(1, ) = (halt, 1, +1)
By increasing the number of states, we can build a Turing machine that shifts the input string any
fixed number of steps in either direction. For example, a machine that shifts its input to the left
by five steps might read the string from right to left, storing the five most recently read symbols in
its internal state. A typical transition for such a machine would be δ(12345, 0) = (01234, 5, −1).
With a more complex Turing machine, we can implement binary addition. The input is a string of
the form w+ x, where w, x ∈ {0, 1}n , representing two numbers in binary; the output is the binary
representation of w+ x. To simplify our presentation, we assume that |w| = |x| > 0; however, this
restrictions can be removed with the addition of a few more states. The following figure shows
the entire Turing machine at a glance. The machine uses the tape alphabet Γ = {, 0, 1, +, 0, 1};
the start state is shift0. All missing transitions go to a fail state, indicating that the input was
badly formed.
Execution of this Turing machine proceeds in several phases, each with its own subset of
states, as indicated in the figure. The initialization phase scans the entire input, shifting it to
the right to make room for the output string, marking the rightmost bit of w, and reading and
erasing the last bit of x.
δ( p , a) = ( q , b, ∆)
δ( shift0 , 0) = ( shift0 , 0, +1)
δ( shift0 , 1) = ( shift1 , 0, +1)
δ( shift0 , +) = (shift+, 0, +1)
δ( shift0 , ) = ( add0 , , −1)
δ( shift1 , 0) = ( shift0 , 1, +1)
δ( shift1 , 1) = ( shift1 , 1, +1)
δ( shift1 , +) = (shift+, 1, +1)
δ( shift1 , ) = ( add1 , , −1)
δ(shift+, 0) = ( shift0 , +, +1)
δ(shift+, 1) = ( shift1 , +, +1)
The first part of the main loop scans left to the marked bit of w, adds the bit of x that was
just erased plus the carry bit from the previous iteration, and records the carry bit for the next
iteration in the machines internal state.
8
Models of Computation Lecture 6: Turing Machines [Fa’16]
initialization
shift+
+/0,+1 +/1,+1
0/+,+1 1/+,+1
1/0,+1
0/0,+1 shift0 shift1 1/1,+1
0/1,+1
□/□,−1 □/□,−1 main loop
scan right
back0 back1
and read
1/0,+1 1/1,+1
0/0,+1 0/0,+1
1/1,+1 next0 next1 1/1,+1
+/+,+1 +/+,+1
□/□,−1
□/□,−1
get0 get1
0/□,−1 1/□,−1 0/□,−1 1/□,−1
+/□,−1 +/□,−1
termination
0/0,−1 0/0,−1
1/1,−1 last0 halt last1 1/1,−1
0/0,−1 0/0,−1
A Turing machine that adds two binary numbers of the same length.
δ( p , a) = ( q , b, ∆) δ( p , a) = ( q , b, ∆) δ( p , a) = ( q , b, ∆)
δ(add0, 0) = ( add0 , 0, −1) δ(add1, 0) = ( add1 , 0, −1) δ(add2, 0) = ( add2 , 0, −1)
δ(add0, 1) = ( add0 , 0, −1) δ(add1, 1) = ( add1 , 0, −1) δ(add2, 1) = ( add2 , 0, −1)
δ(add0, +) = ( add0 , 0, −1) δ(add1, +) = ( add1 , 0, −1) δ(add2, +) = ( add2 , 0, −1)
δ(add0, 0) = (back0, 0, −1) δ(add1, 0) = (back0, 1, −1) δ(add2, 0) = (back1, 0, −1)
δ(add0, 1) = (back0, 1, −1) δ(add1, 1) = (back1, 0, −1) δ(add2, 1) = (back1, 1, −1)
The second part of the main loop marks the previous bit of w, scans right to the end of x, and
then reads and erases the last bit of x, all while maintaining the carry bit.
δ( p , a) = ( q , b, ∆) δ( p , a) = ( q , b, ∆)
δ(back0, 0) = (next0, 0, +1) δ(back1, 0) = (next1, 0, +1)
δ(back0, 1) = (next0, 1, +1) δ(back1, 1) = (next1, 1, +1)
δ( next0 , 0) = (next0, 0, +1) δ( next1 , 0) = (next1, 0, +1)
δ( next0 , 1) = (next0, 0, +1) δ( next1 , 1) = (next1, 0, +1)
δ( next0 , +) = (next0, 0, +1) δ( next1 , +) = (next1, 0, +1)
δ( next0 , ) = ( get0 , , −1) δ( next1 , ) = ( get1 , , −1)
δ( get0 , 0) = ( add0 , , −1) δ( get1 , 0) = ( add1 , , −1)
δ( get0 , 1) = ( add1 , , −1) δ( get1 , 1) = ( add2 , , −1)
δ( get0 , +) = ( last0 , , −1) δ( get1 , +) = ( last1 , , −1)
Finally, after erasing the + in the last iteration of the main loop, the termination phase adds the
last carry bit to the leftmost output bit and halts.
9
Models of Computation Lecture 6: Turing Machines [Fa’16]
δ( p , a) = ( q , b, ∆)
δ(last0, 0) = (last0, 0, −1)
δ(last0, 1) = (last0, 0, −1)
δ(last0, 0) = ( halt , 0, )
δ(last1, 0) = (last1, 0, −1)
δ(last1, 1) = (last1, 0, −1)
δ(last1, 0) = ( halt , 1, )
It is sometimes convenient to endow the Turing machine tape with multiple tracks, each with its
own tape alphabet, and allow the machine to read from and write to the same position on all
tracks simultaneously. For example, to define a Turing machine with three tracks, we need three
tape alphabets Γ1 , Γ2 , and Γ3 , each with its own blank symbol, where (say) Γ1 contains the input
alphabet Σ as a subset; we also need a transition function of the form
δ : Q × Γ1 × Γ2 × Γ3 → Q × Γ1 × Γ2 × Γ3 × {−1, +1}
Describing a configuration of this machine requires a quintuple (q, x 1 , x 2 , x 3 , i), indicating that
each track i contains the string x i followed by an infinite sequence of blanks. The initial
configuration is (start, w, ", ", 0), with the input string written on the first track, and the other
two tracks completely blank.
But any such machine is equivalent (if not identical) to a single-track Turing machine with
the (still finite!) tape alphabet Γ := Γ1 × Γ2 × Γ3 . Instead of thinking of the tape as three infinite
sequences of symbols, we think of it as a single infinite sequence of “records”, each containing
three symbols. Moreover, there’s nothing special about the number 3 in this construction; a
Turing machine with any constant number of tracks is equivalent to a single-track machine.
Doubly-Infinite Tape
It is also sometimes convenient to allow the tape to be infinite in both directions, for example,
to avoid boundary conditions. There are several ways to simulate a doubly-infinite tape on a
machine with only a semi-infinite tape. Perhaps the simplest method is to use a semi-infinite tape
with two tracks, one containing the cells with positive index and the other containing the cells
with negative index in reverse order, with a special marker symbol at position zero to indicate
the transition.
0 +1 +2 +3 +4 · · ·
É −1 −2 −3 −4 · · ·
Another method is to shuffle the positive-index and negative-index cells onto a single track,
and add additional states to allow the Turing machine to move two steps in a single transition.
Again, we need a special symbol at the left end of the tape to indicate the transition:
É 0 −1 +1 −2 +2 −3 +3 ···
A third method maintains two sentinel symbols É and Ê that surround all other non-blank
symbols on the tape. Whenever the machine reads the right sentinel Ê, we write a blank, move
right, write Ê, move left, and then proceed as if we had just read a blank. On the other hand,
when the machine reads the left sentinel É, we shift the entire contents of the tape (up to and
10
Models of Computation Lecture 6: Turing Machines [Fa’16]
including the right sentinel) one step to the right, then move back to the left sentinel, move right,
write a blank, and finally proceed as if we had just read a blank. Since the Turing machine does
not actually have access to the position of the head as an integer, shifting the head and the tape
contents one step right has no effect on its future evolution.
É −3 −2 −1 0 +1 +2 +3 +4 +5 Ê ···
Using either of the first two methods, we can simulate t steps of an arbitrary Turing machine
with a doubly-infinite tape using only O(t) steps on a standard Turing machine. The third
method, unfortunately, requires Θ(t 2 ) steps in the worst case.
We can also allow Turing machines to insert and delete cells on the tape, in addition to simply
overwriting existing symbols. We’ve already seen how to insert a new cell: Leave a special mark
on the tape (perhaps in a second track), shift everything to the right of this mark one cell to the
right, scan left to the mark, erase the mark, and finally write the correct character into the new
cell. Deletion is similar: Mark the cell to be deleted, shift everything to the right of the mark one
step to the left, scan left to the mark, and erase the mark. We may also need to maintain a mark
in some cell to the right every non-blank symbol, indicating that all cells further to the right are
blank, so that we know when to stop shifting left or right.
Multiple Heads
Another convenient extension is to allow machines simultaneous access to more than one position
on the tape. For example, to define a Turing machine with three heads, we need a transition
function of the form
δ : Q × Γ 3 → Q × Γ 3 × {−1, +1}3 .
Describing a configuration of such a machine requires a quintuple (q, x, i, j, k), indicating that the
machine is in state q, the tape contains string x, and the three heads are at positions i, j, k. The
transition function tells us, given q and the three symbols x[i], x[ j], x[k], which three symbols
to write on the tape and which direction to move each of the heads.
We can simulate this behavior with a single head by adding additional tracks to the tape
that record the positions of each head. To simulate a machine M with three heads, we use a
tape with four tracks: track 0 is the actual work tape; each of the remaining tracks has a single
non-blank symbol recording the position of one of the heads. We also insert a special marker
symbols at the left end of the tape.
É M Y W O R K T A P E ···
É Î ···
É Î ···
É Î ···
We can simulate any single transition of M , starting with our single head at the left end of
the tape, as follows. Throughout the simulation, we maintain the internal state of M as one of
the components of our current state. First, for each i, we read the symbol under the ith head of
M as follows:
Scan to the right to find the mark on track i, read the corresponding symbol from
track 0 into our internal state, and then return to the left end of the tape.
11
Models of Computation Lecture 6: Turing Machines [Fa’16]
At this point, our internal state records M ’s current internal state and the three symbols under
M ’s heads. After one more transition (using M ’s transition function), our internal state records
M ’s next state, the symbol to be written by each head, and the direction to move each head.
Then, for each i, we write with and move the ith head of M as follows:
Scan to the right to find the mark on track i, write the correct symbol onto on track
0, move the mark on track i one step left or right, and then return to the left end of
the tape.
Again, there is nothing special about the number 3 here; we can simulate machines with any
fixed number of heads.
Careful analysis of this technique implies that for any integer k, we can simulate t steps
of an arbitrary Turing machine with k independent heads in Θ(t 2 ) time on a standard Turing
machine with only one head. Unfortunately, this quadratic blowup is unavoidable. It is relatively
easy to recognize the language of marked palindromes {w•wR | w ∈ {0, 1}∗ } in O(n) time using
a Turing machine with two heads, but recognizing this language provably requires Ω(n2 ) time
on a standard machine with only one head. On the other hand, with much more sophisticated
techniques, it is possible to simulate t steps of a Turing machine with k head, for any fixed
integer k, using only O(t log t) steps on a Turing machine with just two heads.
Multiple Tapes
We can also allow machines with multiple independent tapes, each with its own head. To
simulate such a machine with a single tape, we simply maintain each tape as an independent
track with its own head. Equivalently, we can simulate a machine with k tapes using a single
tape with 2k tracks, half storing the contents of the k tapes and half storing the positions of the k
heads.
É T A P E # O N E ···
É Î ···
É T A P E # T W O ···
É Î ···
É T A P E # T H R E E ···
É Î ···
Just as for multiple tracks, for any constant k, we can simulate t steps of an arbitrary Turing
machine with k independent tapes in Θ(t 2 ) steps on a standard Turing machine with one tape,
and this quadratic blowup is unavoidable. Moreover, it is possible to simulate t steps on a
k-tape Turing machine using only O(t log t) steps on a two-tape Turing machine using more
sophisticated techniques. (This faster simulation is easier to obtain for multiple independent
tapes than for multiple heads on the same tape.)
By combining these tricks, we can simulate a Turing machine with any fixed number of tapes,
each of which may be infinite in one or both directions, each with any fixed number of heads and
any fixed number of tracks, with at most a quadratic blowup in the running time.
12
Models of Computation Lecture 6: Turing Machines [Fa’16]
ÆÆÆ Use a second tape/track as a “call stack”. Add save and restore actions. In the simplest
formulation, subroutines do not have local memory. To call a subroutine, save the current
state onto the call stack and jump to the first state of the subroutine. To return, restore (and
remove) the return state from the call stack. We can simulate t steps of any recursive Turing
machine with O(t) steps on a multitape standard Turing machine, or in O(t 2 ) steps on a
standard Turing machine.
More complex versions of this simulation can adapt to
ÆÆÆ Keep [address•data] pairs on a separate “memory” tape. Write address to an “address”
tape; read data from or write data to a “data” tape. Add new or changed [address•data]
pairs at the end of the memory tape. (Semantics of reading from an address that has never
been written to?)
Suppose all memory accesses require at most ` address and data bits. Then we can
simulate the kth memory access in O(k`) steps on a multitape Turing machine or in O(k2 `2 )
steps on a single-tape machine. Thus, simulating t memory accesses in a random-access
machine with `-bit words requires O(t 2 `) time on a multitape Turing machine, or O(t 3 `2 ) time
on a single-tape machine.
The next few pages, I will sketch a universal Turing machine U that uses the input alphabet
{0, 1, [, ], •, |} and a somewhat larger tape alphabet (via marks on additional tracks). However,
I will not require that the Turing machines that U simulates have similarly small alphabets, so
we first need a method to encode arbitrary input and tape alphabets.
Encodings
Let M = (Γ , , Σ, Q, start, accept, reject, δ) be an arbitrary Turing machine, with a single half-
infinite tape and a single read-write head. (I will consistently indicate the states and tape symbols
of M in slanted green to distinguish them from the upright red states and tape symbols of U.)
We encode each symbol a ∈ Γ as a unique string |a| of dlg(|Γ |)e bits. Thus, if Γ = {0, 1, $, x, },
we might use the following encoding:
〈0〉 = 001, 〈1〉 = 010, 〈$〉 = 011, 〈x〉 = 100, 〈〉 = 000.
13
Models of Computation Lecture 6: Turing Machines [Fa’16]
The input string w is encoded by its sequence of symbol encodings, with separators • between
every pair of symbols and with brackets [ and ] around the whole string. For example, with this
encoding, the input string 001100 would be encoded on the input tape as
〈001100〉 = [001•001•010•010•001•001]
Similarly, we encode each state q ∈ Q as a distinct string 〈q〉 of dlg|Q|e bits. Without loss of
generality, we encode the start state with all 1s and the reject state with all 0s. For example, if
Q = {start, seek1, seek0, reset, verify, accept, reject}, we might use the following encoding:
We encode the machine M itself as the string 〈M 〉 = [〈reject〉•〈〉]〈δ〉, where 〈δ〉 is the
concatenation of substrings [〈p〉•〈a〉|〈q〉•〈b〉•〈∆〉] encoding each transition δ(p, a) = (q, b, ∆)
such that q 6= reject. We encode the actions ∆ = ±1 by defining 〈−1〉 := 0 and 〈+1〉 := 1.
Conveniently, every transition string has exactly the same length. For example, with the symbol
and state encodings described above, the transition δ(reset, $) = (start, $, +1) would be encoded
as
[100•011|001•011•1].
Our first example Turing machine for recognizing {0n 1n 0n | n ≥ 0} would be represented by
the following string (here broken into multiple lines for readability):
[000•000][[001•001|010•011•1][001•100|101•011•1]
[010•001|010•001•1][010•100|010•100•1]
[010•010|011•100•1][011•010|011•010•1]
[011•100|011•100•1][011•001|100•100•1]
[100•001|100•001•0][100•010|100•010•0]
[100•100|100•100•0][100•011|001•011•1]
[101•100|101•011•1][101•000|110•000•0]]
Finally, we encode any configuration of M on U’s work tape by alternating between encodings
of states and encodings of tape symbols. Thus, each tape cell is represented by the string
[〈q〉•〈a〉] indicating that (1) the cell contains symbol a; (2) if q 6= reject, then M ’s head is
located at this cell, and M is in state q; and (3) if q = reject, then M ’s head is located somewhere
else. Conveniently, each cell encoding uses exactly the same number of bits. We also surround
the entire tape encoding with brackets [ and ].
For example, with the encodings described above, the initial configuration (start, 001100
Î
, 0)
for our first example Turing machine would be encoded on U’s tape as follows.
[[111•001][000•001][000•010][000•010][000•001][000•001]]
| {z }| {z }| {z }| {z }| {z }| {z }
start 0 reject 0 reject 1 reject 1 reject 0 reject 0
[[000•011][000•011][000•100][010•010][000•100][000•001]]
| {z }| {z }| {z }| {z }| {z }| {z }
reject $ reject 0 reject x reset 1 reject x reject 0
14
Models of Computation Lecture 6: Turing Machines [Fa’16]
Without loss of generality, we assume that the input to our universal Turing machine U is given
on a separate read-only input tape, as the encoding of an arbitrary Turing machine M followed
by an encoding of its input string x. Notice the substrings [[ and ]] each appear only only once
on the input tape, immediately before and after the encoded transition table, respectively. U also
has a read-write work tape, which is initially blank.
We start by initializing the work tape with the encoding 〈start, x, 0〉 of the initial configuration
of M with input x. First, we write [[〈start〉•. Then we copy the encoded input string 〈x〉 onto
the work tape, but we change the punctuation as follows:
The state encodings 〈start〉 and 〈reject〉 can be copied directly from the beginning of 〈M 〉
(replacing 0s for 1s for 〈start〉). Finally, we move the head back to the start of U’s tape.
At the start of each step of the simulation, U’s head is located at the start of the work tape.
We scan through the work tape to the unique encoded cell [〈p〉•〈a〉] such that p 6= reject.
Then we scan through the encoded transition function 〈δ〉 to find the unique encoded tuple
[〈p〉•〈a〉|〈q〉•〈b〉•〈∆〉] whose left half matches our the encoded tape cell. If there is no such
tuple, then U immediately halts and rejects. Otherwise, we copy the right half 〈q〉•〈b〉 of the
tuple to the work tape. Now if q = accept, then U immediately halts and accepts. (We don’t
bother to encode reject transformations, so we know that q 6= reject.) Otherwise, we transfer
the state encoding to either the next or previous encoded cell, as indicated by M ’s transition
function, and then continue with the next step of the simulation.
During the final state-copying phase, we ever read two right brackets ]], indicating that
we have reached the right end of the tape encoding, we replace the second right bracket with
[〈reject〉•〈〉]] (mostly copied from the beginning of the machine encoding 〈M 〉) and then
scan back to the left bracket we just wrote. This trick allows our universal machine to pretend
that its tape contains an infinite sequence of encoded blanks [〈reject〉•〈〉] instead of actual
blanks .
Example
[[000•011][000•011][000•100][010•010][000•100][000•001]]
Î
First U scans for the first encoded tape cell whose state is not reject. That is, U repeatedly
compares the first half of each encoded state cell on the work tape with the prefix [〈reject〉• of
the machine encoding 〈M 〉 on the input tape. U finds a match in the fourth encoded cell.
[[000•011][000•011][000•100][010•010][000•100][000•001]]
Î
Next, U scans the machine encoding 〈M 〉 for the substring [010•010 matching the cur-
rent encoded cell. U eventually finds a match in the left size of the the encoded transition
15
Models of Computation Lecture 6: Turing Machines [Fa’16]
[010•010|011•100•1]. U copies the state-symbol pair 011•100 from the right half of this
encoded transition into the current encoded cell. (The underline indicates which symbols are
changed.)
[[000•011][000•011][000•100][011•100][000•100][000•001]]
Î
The encoded transition instructs U to move the current state encoding one cell to the right. (The
underline indicates which symbols are changed.)
[[000•011][000•011][000•100][000•100][011•100][000•001]]
Î
Finally, U scans left until it reads two left brackets [[; this returns the head to the left end of
the work tape to start the next step in the simulation. U’s tape now holds the encoding of M ’s
configuration (seek0, $$xxx0, 4), as required.
Î
[[000•011][000•011][000•100][000•100][011•100][000•001]]
Î
Exercises
In the following problems, a standard Turing machine has a single semi-infinite tape, one
read-write head, and the input alphabet Σ = {0, 1}. For problems that ask you to construct a
standard Turing machine, you may assume without loss of generality that the initial tape contains
a special symbol É just to the left of the input string, indicating the left end of the tape; the
read-write head starts just to the right of this symbol. For problems that ask you to simulate a
standard Turing machine, you may assume without loss of generality that the tape alphabet is
{0, 1,}.
2. Let 〈n〉2 denote the binary representation of the non-negative integer n. For example,
〈17〉2 = 10001 and 〈42〉2 = 101010. Describe standard Turing machines that compute
the following functions from {0, 1}∗ to {0, 1}∗ :
(a) w 7→ www
(b) 1n 01m 7→ 1mn
n
(c) 1n 7→ 12
(d) 1n 7→ 〈n〉2
(e) 0∗ 〈n〉2 7→ 1n
(f) 〈n〉2 7→ 〈n2 〉2
16
Models of Computation Lecture 6: Turing Machines [Fa’16]
3. Describe standard Turing machines that write each of the following infinite streams of bits
onto their tape. Specifically, for each integer n, there must be a finite time after which the
first n symbols on the tape always match the first n symbols in the target stream.
where w indicates the binary string obtained from w by flipping every bit. Equivalently,
the nth bit of the Thue Morse sequence if 0 if the binary representation of n has an
even number of 1s and 1 otherwise.
0110100110010110100101100110100110010110011010010110 . . .
01011010110110101101011011010110110101101011011010101 . . .
17
Models of Computation Lecture 6: Turing Machines [Fa’16]
that takes the internal state and the signs of the registers as input, and produces a new
internal state and changes to the registers as output. The instructions halve, nop, double,
and double+1 change any register with value n to n/2, n, 2n, and 2n + 1, respectively.
For example, if δ(p, 0, 1, 0, 1) = (q, halve, nop, halve, double+1), then from the config-
uration (p, 0, 2, 3, 1), the machine would transition to (q, 1, 2, 1, 3).
Prove that any standard Turing machine (with suitably encoded input and output) can
be simulated by a two-register machine. The input to the register machine is encoded in
reversed binary in one of the registers, so the parity of the register value is the first input
bit; the other register is initially zero.
that takes the internal state and the signs of the registers as input, and produces a new
internal state and changes to the registers as output. The instructions inc, nop, and dec
change any register with value n to n + 1, n, and n − 1, respectively. The transition function
must forbid decrementing a register whose value is already zero.
For example, if δ(p, 0, +, +, +) = (q, inc, dec, nop, dec), then from the configuration
(p, 0, 2, 3, 1), the machine would transition to (q, 1, 1, 3, 0).
(a) Prove that any standard Turing machine (with suitably encoded input and output) can
be simulated by a three-counter machine. [Hint: Simulate a two-register machine,
using the third counter for scratch work.]
(b) Prove that any three-counter machine (with suitably encoded input and output) can
be simulated by a two-counter machine. [Hint: Store all three counters in a single
integer of the form 2a 3 b 5c , and use the other counter for scratch work.]
? (c) Prove that a three-counter machine can compute a suitable encoding of any computable
function. Specifically, for any computable function f : N → N, prove there is a three-
counter machine M that transforms any input (n, 0, 0) into ( f (n), 0, 0). [Hint: First
transform (n, 0, 0) to (2n , 0, 0) using all three counters; then run a two- (or three-
)counter TM simulation to obtain (2 f (n) , 0, 0); and finally transform (2 f (n) , 0, 0) to
( f (n), 0, 0) using all three counters.]
Æ
(d) Prove that not two-counter machine can transform (n, 0) to (2n , 0). This impossiblity
result was independently proved by Bārzdin, š in 1963, Yao in 1971, and Schroeppel in
1972. ⁵
7. A hole-punch Turing machine is a standard Turing machine with two restrictions. First, the
tape alphabet has only two symbols and , and thus the input alphabet is the singleton
⁵Ja. M. Barzdin0 [Jānis Bārzdin, š]. Ob odnom klasse mašin T0 ûringa (mašiny Minskogo) [On a class of Turing
machines (Minsky machines)]. Algebra i Logika 1(6):42–51, 1963. In Russian. Sorry.
Oscar H. Ibarra, Nicholas Q. Trân. A note on simple programs with two variables. Theoretical Computer Science
112(2): 391–397, 1993.
Rich Schroeppel. A two counter machine cannot calculate 2N . Artificial Intelligence Memo 257, MIT AI Lab, May
1972. [Schroeppel claims that the same result was independently proved by Frances Yao in 1971.
18
Models of Computation Lecture 6: Turing Machines [Fa’16]
set {}. Second, the machine can never write a blank () over a non-blank (); intuitively,
the machine can punch new holes (s) into the tape, but it cannot erase holes.
Prove that any standard Turing machine (with a unary input alphabet) can be simulated
by a hole-punch Turing machine.
8. A tag-Turing machine has two heads: one can only read, the other can only write. Initially,
the read head is located at the left end of the tape, and the write head is located at the first
blank after the input string. At each transition, the read head can either move one cell to
the right or stay put, but the write head must write a symbol to its current cell and move
one cell to the right. Neither head can ever move to the left.
Prove that any standard Turing machine can be simulated by a tag-Turing machine.
That is, given any standard Turing machine M , describe a tag-Turing machine M 0 that
accepts and rejects exactly the same input strings as M .
9. ? (a) Prove that any standard Turing machine can be simulated by a standard Turing
machine with only three states. [Hint: Keep an encoding of the state of the simulated
machine on the tape of the simulating machine.]
Æ
(b) Prove that any standard Turing machine can be simulated by a standard Turing
machine with only two states.
(a) Prove that any two-dimensional Turing machine can be simulated by a standard
Turing machine.
(b) Suppose further that we endow our two-dimensional Turing machine with the
following additional actions, in addition to moving the head:
• Insert row: Move all symbols on or above the row containing the head up one
row, leaving the head’s row blank.
• Insert column: Move all symbols on or to the right of the column containing the
head one column to the right, leaving the head’s column blank.
• Delete row: Move all symbols above the row containing the head down one row,
deleting the head’s row of symbols.
• Delete column: Move all symbols the right of the column containing the head
one column to the right, deleting the head’s column of symbols.
Show that any two-dimensional Turing machine that can add an delete rows can be
simulated by a standard Turing machine.
11. A binary-tree Turing machine uses an infinite binary tree as its tape; that is, every cell in
the tape has a left child and a right child. At each step, the head moves from its current
19
Models of Computation Lecture 6: Turing Machines [Fa’16]
cell to its Parent, its Left child, or to its Right child. Thus, the transition function of such a
machine has the form δ : Q × Γ → Q × Γ × {P, L, R}. The input string is initially given along
the left spine of the tape.
Show that any binary-tree Turing machine can be simulated by a standard Turing
machine.
12. A stack-tape Turing machine uses an semi-infinite tape, where every cell is actually the
top of an independent stack. The behavior of the machine at each iteration is governed by
its internal state and the symbol at the top of the current cell’s stack. At each transition,
the head can optionally push a new symbol onto the stack, or pop the top symbol off the
stack. (If a stack is empty, its “top symbol” is a blank and popping has no effect.)
Show that any stack-tape Turing machine can be simulated by a standard Turing
machine. (Compare with Problem 4!)
13. A tape-stack Turing machine has two actions that modify its work tape, in addition to
simply writing individual cells: it can save the entire tape by pushing in onto a stack, and it
can restore the entire tape by popping it off the stack. Restoring a tape returns the content
of every cell to its content when the tape was saved. Saving and restoring the tape do not
change the machine’s state or the position of its head. If the machine attempts to “restore”
the tape when the stack is empty, the machine crashes.
Show that any tape-stack Turing machine can be simulated by a standard Turing
machine.
ÆÆÆ Rewrite in the language of algorithms instead of the language of Turing machines, using
“source code” instead of “encoding” everywhere. Formulation in terms of TMs makes almost
everything much more complicated than it needs to be. (The dovetail/product construction in
the proof of Lemma 4 may be an exception.)
7 Undecidability
Perhaps the single most important result in Turing’s remarkable 1936 paper that introduces Turing
machines is his observation that there are problems that cannot be solved by any algorithm.
Turing’s canonical example of an undecidable problem was the halting problem, which asks
whether a given Turing machine halts when given a particular input string. Among other
consequences, Turing’s undecidability result provided an elegant negative solution to Hilbert’s
Entscheidungsproblem, which asked for an algorithm to decide whether a given statement of
first-order logic is true—no such algorithm exists.
For any language L, the sentence “M accepts L” means Accept(M ) = L, and the sentence “M
decides L” means Accept(M ) = L and Diverge(M ) = ∅.
1
Models of Computation Lecture 7: Undecidability [Fa’16]
• Suppose the binary expansion of π contains arbitrarily long substrings of 1s. Then any
Turing machine that accepts all inputs correctly decides Π.
We have no idea which of these machines correctly decides Π, but one of them does, and that’s
enough!
2
Models of Computation Lecture 7: Undecidability [Fa’16]
Lemma 4. For all acceptable languages L and L 0 , the languages L ∪ L 0 and L ∩ L 0 are also
acceptable.
Proof: Let M and M 0 be Turing machines that decide L and L 0 , respectively. We can build a
Turing machine M∩ that decides L ∩ L 0 as follows. First, M∩ copies its input string w onto a
second tape. Then M∩ runs M on input w using the first tape, and then runs M 0 on input w using
the second tape. If both M and M 0 accept, then M∩ accepts; if either M or M 0 reject, then M∩
rejects; if either M or M 0 diverge, then M∩ diverges (automatically).
The construction for L ∪ L 0 is more subtle; instead of running M and M 0 in series, we must
run them in parallel. Like M∩ , the new machine M∪ starts by copying its input string w onto
a second tape. But then M∪ runs M and M 0 simultaneously; with each step of M∪ simulating
both one step of M on the first tape and one step of M 0 on the second. Ignoring the states and
transitions needed for initialization, the state set of M∪ is the product of the state sets of M
and M 0 , and the transition function is
accept∪ if q = accept or q0 = accept0
δ∪ (q, a, q0 , a0 ) = reject∪ if q = reject and q0 = reject0
(δ(q, a), δ0 (q0 , a0 )) otherwise
Thus, M∪ accepts as soon as either M or M 0 accepts, and rejects only after both M or M 0
reject.
Proof: Let M and M be Turing machines that accept L and Σ∗ \ L, respectively. Following the
previous proof, we construct a new Turing machine M ∗ that copies its input onto a second tape,
and then simulates M and M 0 in parallel on the two tapes. If M accepts, then M ∗ accepts; if M
accepts, then M ∗ rejects. Since every string is accepted by either M or M , we conclude that M ∗
decides L.
The other direction follows immediately from Lemma 1.
3
Models of Computation Lecture 7: Undecidability [Fa’16]
• Modifiable: We can algorithmically modify any Turing machine M , given the encoding
of M as input. For example, there are algorithms to swap the accept and reject states of any
Turing machine, or to add new states and transitions representing pre- and post-processing
phases, or to build a new machine that calls M as a subroutine, or to build a new machine
that runs several copies of M in parallel.
• Executable: There is a fixed universal Turing machine U that can simulate the behavior
of an arbitrary Turing machine M , given the encodings of M and w as input. For example,
if we decided to encode Turing machines as Python programs, then U would be a Python
interpreter.
The precise details of the encoding are unimportant, but for the sake of concreteness, let
me describe a natural encoding of Turing machines as strings over the six-character alphabet
{0, 1, {, •, }}. Let M = (Γ , , Σ, Q, start, accept, reject, δ) be an arbitrary Turing machine, with
a single half-infinite tape and a single read-write head. (I will consistently indicate the states
and tape symbols of M in slanted green to distinguish them from the upright red symbols in the
encoding alphabet.)
• We encode each symbol a ∈ Γ as a unique string |a| of dlg(|Γ |)e bits. For example, if
Γ = {0, 1, $, x, }, we might use the following encoding:
〈0〉 = 001, 〈1〉 = 010, 〈$〉 = 011, 〈x〉 = 100, 〈〉 = 000.
• Similarly, we encode each state q ∈ Q as a distinct string 〈q〉 of dlg|Q|e bits. Without
loss of generality, we encode the start state with all 1s and the reject state with all 0s.
For example, if Q = {start, seek1, seek0, reset, verify, accept, reject}, we might use the
following encoding:
• Finally, we encode the machine M itself as the string 〈M 〉 = {〈reject〉•〈〉}〈δ〉, where 〈δ〉
is the concatenation of substrings {〈p〉•〈a〉•〈q〉•〈b〉•〈∆〉} encoding each transition
δ(p, a) = (q, b, ∆) such that q 6= reject. We encode the actions ∆ = ±1 by defining
〈−1〉 := 0 and 〈+1〉 := 1. Conveniently, every transition string has exactly the same
length. For example, with the symbol and state encodings described above, the transition
δ(reset, $) = (start, $, +1) would be encoded as the string
{100•011•001•011•1}.
Our first example Turing machine for recognizing {0n 1n 0n | n ≥ 0} would be represented
by the following string (broken into multiple lines for readability):
{000•000}{{001•001•010•011•1}{001•100•101•011•1}{010•001•010•001•1}
{010•100•010•100•1}{010•010•011•100•1}{011•010•011•010•1}
{011•100•011•100•1}{011•001•100•100•1}{100•001•100•001•0}
{100•010•100•010•0}{100•100•100•100•0}{100•011•001•011•1}
{101•100•101•011•1}{101•000•110•000•0}}
4
Models of Computation Lecture 7: Undecidability [Fa’16]
Building a universal Turing machine U that uses this encoding is more a matter of careful
bookkeeping than real insight. We can encode any configuration of M on U’s work tape by
encoding each cell of M ’s tape as a string {〈q〉•〈a〉} indicating that (1) the cell contains symbol a;
(2) if q 6= reject, then M ’s head is located at this cell, and M is in state q; and (3) if q = reject,
then M ’s head is located somewhere else. We also surround the entire tape encoding with
brackets { and }. For example, the initial configuration (start, 00110
Î
, 0) for our example Turing
machine would be encoded as follows.
To simulate one step of M ’s execution, we (1) find the location of the head (or reject if the head
has vanished), (2) look up the transition for the state-symbol pair at the head, and (3) update
the current cell and one of its neighbors to reflect the transition. The remaining grungy details
are left as an exercise.
Turing used this observation about self-reference to derive his first undecidable language as
follows. Let’s say that a Turing machine M is self-rejecting if it rejects its own encoding 〈M 〉.
Let SelfReject be the set of all encodings of self-rejecting Turing machines:
SelfReject := 〈M 〉 M rejects 〈M 〉
Proof: Suppose to the contrary that there is a Turing machine SR that decides SelfReject.
Then by definition, Accept(SR) = SelfReject and Diverge(SR) = ∅. More explicitly, for any
Turing machine M ,
In particular, these equivalences must hold when M is the machine SR. Thus,
In short, SR accepts 〈SR〉 if and only if SR rejects 〈SR〉, which is impossible! The only logical
conclusion is that the Turing machine SR does not exist.
5
Models of Computation Lecture 7: Undecidability [Fa’16]
Proof: Fix an arbitrary function f : X → 2X . Call an element x ∈ X happy if x ∈ f (x) and sad
if x 6∈ f (x). Let Y be the set of all sad elements of X ; that is, for every element x ∈ X , we have
x ∈ Y ⇐⇒ x 6∈ f (x).
For the sake of argument, suppose f is a surjection. Then (by definition of surjection) there must
be an element y ∈ X such that f ( y) = Y . Then for every element x ∈ X , we have
x ∈ f ( y) ⇐⇒ x 6∈ f (x).
y ∈ f ( y) ⇐⇒ y 6∈ f ( y).
Cantor’s theorem immediately implies that not all languages are acceptable.
Alternatively, let X be the set of all Turing machines that halt on all inputs. For any Turing
machine M ∈ X , let f (M ) be the set of all Turing machines N ∈ X such that M accepts the
encoding 〈N 〉. Then a Turing machine M is sad if it rejects its own encoding 〈M 〉; thus, Y is
essentially the set SelfReject. Cantor’s argument now immediately implies that no Turing
machine decides the language SelfReject.
The core of Cantor’s diagonalization argument also appears in the “barber paradox” popular-
ized by Bertrand Russell in the 1910s. In a certain small town, every resident has a haircut on
Haircut Day. Some residents cut their own hair; others have their hair cut by another resident of
the same town. To obtain an official barber’s license, a resident must cut the hair of all residents
who don’t cut their own hair, and no one else. Given these assumptions, we can immediately
conclude that there are no licensed barbers. After all, who would cut the barber’s hair?
To map Russell’s barber paradox back to Cantor’s theorem, let X be the set of residents, and
let f (x) be the set of residents who have their hair cut by x; then a resident is sad if they do not
cut their own hair. To prove that SelfReject is undecidable, replace “resident” with “a Turing
machine that halts on all inputs”, and replace “A cuts B’s hair” with “A accepts 〈B〉”.
1more commonly, flouting all reasonable standards of grammatical English, “an onto function”
6
Models of Computation Lecture 7: Undecidability [Fa’16]
The proofs for these three languages are not quite as direct as the proof for SelfReject; each
fictional deciding machine requires a small modification to create the contradiction.
Proof: For the sake of argument, suppose there is a Turing machine SA such that Accept(SA) =
SelfAccept and Diverge(M ) = ∅. Let SAR be the Turing machine obtained from SA by
swapping its accept and reject states (as in the proof of Lemma 1). Then Reject(SAR ) =
SelfAccept and Diverge(SAR ) = ∅. It follows that SAR rejects 〈SAR 〉 if and only if SAR accepts
〈SAR 〉, which is impossible.
Proof: Suppose to the contrary that there is a Turing machine SH such that Accept(SH) =
SelfHalt and Diverge(SH) = ∅. Let SH X be the Turing machine obtained from SH by
redirecting every transition to accept to a new hanging state hang, and then redirecting every
transition to reject to accept. Then Accept(SH X ) = Σ∗ \ SelfHalt and Reject(SH X ) = ∅.
It follows that SH X accepts 〈SH X 〉 if and only if SH X does not halt on 〈SH X 〉, and we have a
contradiction.
Proof: Suppose to the contrary that there is a Turing machine SD such that Accept(M ) =
SelfDiverge. Let S DA be the Turing machine obtained from M by redirecting every transition
to reject to a new hanging state hang such that δ(hang, a) = (hang, a, +1) for every symbol a.
Then Accept(S DA) = SelfDiverge and Reject(SDA) = ∅. It follows that SDA accepts 〈SDA〉 if
and only if S DA does not halt on 〈S DA〉, which is impossible.
?
7.8 Nevertheless, Acceptable
Our undecidability argument for SelfDiverge actually implies the stronger result that SelfDi-
verge is unacceptable; we never assumed that the hypothetical accepting machine SD halts on
all inputs. However, we can use or modify our universal Turing machine U to accept the other
three self-referential languages.
Proof: We describe a Turing machine SA that accepts the language SelfAccept. Given any
string w as input, SA first verifies that w is the encoding of a Turing machine. If w is not
the encoding of a Turing machine, then SA diverges. Otherwise, w = 〈M 〉 for some Turing
machine M ; in this case, SA writes the string ww = 〈M 〉〈M 〉 onto its tape and passes control to
the universal Turing machine U. U then simulates M (the machine encoded by the first half of
7
Models of Computation Lecture 7: Undecidability [Fa’16]
its input) on the string 〈M 〉 (the second half of its input).2 In particular, U accepts 〈M , M 〉 if and
only if M accepts 〈M 〉. We conclude that SR accepts 〈M 〉 if and only if M accepts 〈M 〉.
Proof: Let U R be the Turing machine obtained from our universal machine U by swapping the
accept and reject states. We describe a Turing machine SR that accepts the language SelfReject
as follows. SR first verifies that its input string w is the encoding of a Turing machine and
diverges if not. Otherwise, SR writes the string ww = 〈M , M 〉 onto its tape and passes control to
the reversed universal Turing machine U R . Then U R accepts 〈M , M 〉 if and only if M rejects 〈M 〉.
We conclude that SR accepts 〈M 〉 if and only if M rejects 〈M 〉.
Finally, because SelfHalt is the union of two acceptable languages, SelfHalt is also
acceptable.
Deciding the language Halt is usually called the halting problem: Given a program M and an
input w to that program, does the program halt? This problem may seem trivial; why not just run
the program and see? More formally, why not just pass the input string 〈M , x〉 to our universal
Turing machine U? That strategy works perfectly if we just want to accept Halt, but we actually
want to decide Halt; if M is not going to halt on w, we still want an answer in a finite amount of
time. Sadly, we can’t always get what we want.
Proof: Suppose to the contrary that there is a Turing machine H that decides Halt. Then we
can use H to build another Turing machine SH that decides the language SelfHalt. Given any
string w, the machine SH first verifies that w = 〈M 〉 for some Turing machine M (rejecting if
not), then writes the string ww = 〈M , M 〉 onto the tape, and finally passes control to H. But
SelfHalt is undecidable, so no such machine SH exists. We conclude that H does not exist
either.
Nearly identical arguments imply that the languages Accept, Reject, and Diverge are
undecidable.
2To simplify the presentation, I am implicitly assuming here that 〈M 〉 = 〈〈M 〉〉. Without this assumption, we need
a Turing machine that transforms an arbitrary string w ∈ Σ∗M into its encoding 〈w〉 ∈ Σ∗U ; building such a Turing
machine is straightforward.
3Many sources including Sipser and Wikipedia uses the shorter name A T M instead of Accept, but uses HALTT M
instead of Halt. I have no idea why Sipser thought four-letter names are okay, but six-letter names are not. The
subscript TM is just a reminder that these are languages of Turing machine encodings, as opposed to encodings of
DFAs or some other machine model.
8
Models of Computation Lecture 7: Undecidability [Fa’16]
Perhaps the most confusing aspect of reduction arguments is that the languages we want to
prove undecidable nearly (but not quite) always involve encodings of Turing machines, while at
the same time, the programs that we build to prove them undecidable are also Turing machines.
Our proof that Halt is undecidable involved three different machines:
• The hypothetical Turing machine H that decides Halt.
• The new Turing machine SH that decides SelfHalt, using H as a subroutine.
• The Turing machine M whose encoding is the input to H.
It is incredibly easy to get confused about which machines are playing each in the proof. Therefore,
it is absolutely vital that we give each machine in a reduction proof a unique and mnemonic
name, and then always refer to each machine by name. Never write, say, or even think “the
Turing machine” or “the state” or “the tape” or “the input” or (gods forbid) “it”. You also may
find it useful to think of the working programs we are trying to construct (H and SH in this
proof) as being written in a different language than the arbitrary source code that we want those
programs to analyze (〈M 〉 in this proof).
Proof: Suppose to the contrary that there is a Turing machine N A that decides NeverAccept.
Then by swapping the accept and reject states, we obtain a Turing machine N AR that decides
the complementary language Σ∗ \ NeverAccept.
To reach a contradiction, we construct a Turing machine A that decides Accept as follows.
Given the encoding 〈M , w〉 of an arbitrary machine M and an arbitrary string w as input, A writes
the encoding 〈Mw 〉 of a new Turing machine Mw that ignores its input, writes w onto the tape,
and then passes control to M . Finally, A passes the new encoding 〈Mw 〉 as input to N AR . The
following cartoon tries to illustrate the overall construction.
Before going any further, it may be helpful to list the various Turing machines that appear in
this construction.
9
Models of Computation Lecture 7: Undecidability [Fa’16]
Mw accept
x w M
reject
hang
A
NAR accept
NA
<M,w> Build <Mw>
<Mw>
reject
Now let M be an arbitrary Turing machine and w be an arbitrary string, and suppose we run
our new Turing machine A on the encoding 〈M , w〉. To complete the proof, we need to consider
two cases: Either M accepts w or M does not accept w.
• On the other hand, suppose M does not accept w, either rejecting or diverging instead.
10
Models of Computation Lecture 7: Undecidability [Fa’16]
In short, A decides the language Accept, which is impossible. We conclude that N A does not
exist.
Again, similar arguments imply that the languages NeverReject, NeverHalt, and Never-
Diverge are undecidable. In each case, the core of the argument is describing how to transform
the incoming machine-and-input encoding 〈M , w〉 into the encoding of an appropriate new
Turing machine 〈Mw 〉.
Now that we know that NeverAccept and its relatives are undecidable, we can use them as
the basis of further reduction proofs. Here is a typical example:
Theorem 14. The language DivergeSame := 〈M1 〉 〈M2 〉 Diverge(M1 ) = Diverge(M2 ) is
undecidable.
Proof: Suppose for the sake of argument that there is a Turing machine DS that decides
DivergeSame. Then we can build a Turing machine N D that decides NeverDiverge as follows.
Fix a Turing machine Y that accepts Σ∗ (for example, by defining δ(start, a) = (accept, ·, ·) for
all a ∈ Γ ). Given an arbitrary Turing machine encoding 〈M 〉 as input, N D writes the string
〈M 〉〈Y 〉 onto the tape and then passes control to DS. There are two cases to consider:
ÆÆÆ The following formulation is closer to the proof and may be (slightly) easier to use:
Rice’s Theorem. Let L be any set of languages that satisfies the following conditions:
• There is a Turing machine Y such that Accept(Y ) ∈ L.
• There is a Turing machine N such that Accept(N ) 6∈ L.
The language AcceptIn(L) := 〈M 〉 Accept(M ) ∈ L is undecidable.
Proof: Without loss of generality, suppose ∅ 6∈ L. (A symmetric argument establishes the theorem
in the opposite case ∅ ∈ L.) Fix an arbitrary Turing machine Y such that Accept(Y ) ∈ L.
Suppose to the contrary that there is a Turing machine AL that decides AcceptIn(L). To
derive a contradiction, we describe a Turing machine H that decides the halting language Halt,
using AL as a black-box subroutine. Given the encoding 〈M , w〉 of an arbitrary Turing machine M
and an arbitrary string w as input, H writes the encoding 〈WTF〉 of a new Turing machine WTF
that executes the following algorithm:
11
Models of Computation Lecture 7: Undecidability [Fa’16]
WTF(x):
run M on input w (and discard the result)
run Y on input x
– Then for all strings x, the machine WTF accepts x if and only if Y accepts x.
– So Accept(WTF) = Accept(Y ), by definition of Accept( · ).
– So Accept(WTF) ∈ L, by definition of Y .
– So AL accepts 〈WTF〉, because AL decides AcceptIn(L).
– So H accepts 〈M , w〉, by definition of H.
– Then for all strings x, the machine WTF does not halt on input x, and therefore does
not accept x.
– So Accept(WTF) = ∅, by definition of Accept(WTF).
– So Accept(WTF) 6∈ L, by our assumption that ∅ 6∈ L.
– So AL rejects 〈WTF〉, because AL decides AcceptIn(L).
– So H rejects 〈M , w〉, by definition of H.
In short, H decides the language Halt, which is impossible. We conclude that AL does not
exist.
The set L in the statement of Rice’s Theorem is often called a property of languages, rather
than a set, to avoid the inevitable confusion about sets of sets of finite sequences of characters. We
can also think of L as a decision problem about languages, where the languages are represented
by Turing machines that accept or decide them. Rice’s theorem states that the only properties
of languages that are decidable are the trivial properties “Does this Turing machine accept an
acceptable language?” (Answer: Yes, by definition.) and “Does this Turing machine accept
Discover?” (Answer: No, because Discover is a credit card, not a language.)
Rice’s Theorem makes it incredibly easy to prove that language properties are undecidable;
we only need to exhibit one acceptable language that has the property and another acceptable
language that does not. In fact, every proof using Rice’s theorem can use at least one of the
following Turing machines:
• MAccept accepts every string, by defining δ(start, a) = accept for every tape symbol a.
• MReject rejects every string, by defining δ(start, a) = reject for every tape symbol a.
• MDiverge diverges on every string, by defining δ(start, a) = (start, a, +1) for every tape
symbol a.
12
Models of Computation Lecture 7: Undecidability [Fa’16]
(a) Let L be the set of all languages that contain the empty string. Then AcceptIn(L) = {〈M 〉 |
M accepts given an empty initial tape}.
We can also use Rice’s theorem as a component in more complex undecidability proofs, where
the target language consists of more than just a single Turing machine encoding.
Theorem 16. The language L := 〈M , w〉 M accepts wk for every integer k ≥ 0 is undecid-
able.
Proof: Fix an arbitrary string w, and let L be the set of all languages that contain wk for all k.
Then Accept(MAccept ) = Σ∗ ∈ L and Accept(MReject ) = ∅ 6∈ L. Thus, even if the string w is
fixed in advance, no Turing machine can decide L.
Nearly identical reduction arguments imply the following variants of Rice’s theorem. (The
names of these theorems are not standard.)
⁴Yes, parts (e) and (f) have exactly the same proof.
13
Models of Computation Lecture 7: Undecidability [Fa’16]
Rice’s Rejection Theorem. Let L be any set of languages that satisfies the following conditions:
• There is a Turing machine Y such that Reject(Y ) ∈ L
• There is a Turing machine N such that Reject(N ) 6∈ L.
The language RejectIn(L) := 〈M 〉 Reject(M ) ∈ L is undecidable.
Rice’s Halting Theorem. Let L be any set of languages that satisfies the following conditions:
• There is a Turing machine Y such that Halt(Y ) ∈ L
• There is a Turing machine N such that Halt(N ) 6∈ L.
The language HaltIn(L) := 〈M 〉 Halt(M ) ∈ L is undecidable.
Rice’s Divergence Theorem. Let L be any set of languages that satisfies the following condi-
tions:
• There is a Turing machine Y such that Diverge(Y ) ∈ L
• There is a Turing machine N such that Diverge(N ) 6∈ L.
The language DivergeIn(L) := 〈M 〉 Diverge(M ) ∈ L is undecidable.
Rice’s Decision Theorem. Let L be any set of languages that satisfies the following conditions:
• There is a Turing machine Y that decides an language in L.
• There is a Turing machine N that decides an language not in L.
The language DecideIn(L) := 〈M 〉 M decides a language in L is undecidable.
As easy as it is to use Rice’s theorem and its variants, they cannot be used for all un-
decidability proofs; these theorems only apply to properties of languages. For example, the
language ThisIsSparta := {〈M 〉 | M accepts the string SPARTA after exactly 300 steps} is de-
cidable, even though there are Turing machines that accept the string SPARTA after exactly 300
steps and there are other Turing machines that do not.
More subtly, Rice’s theorem cannot be applied to self-referential languages like RevAccept :=
{〈M 〉 | M accepts 〈M 〉R }, because membership depends on details of the encoded machine and
not just the language that the encoded machine accepts. To be clear: RevAccept is undecidable;
you just can’t use Rice’s theorem to prove that fact.
?
7.12 The Rice-McNaughton-Myhill-Shapiro Theorem
The following subtle generalization of Rice’s theorem precisely characterizes which properties
of acceptable languages are acceptable. This result was partially proved by Henry Rice in 1953,
in the same paper that proved Rice’s Theorem; Robert McNaughton, John Myhill, and Norman
Shapiro completed the proof a few years later, each independently from the other two.⁵
14
Models of Computation Lecture 7: Undecidability [Fa’16]
(c) L is finitely acceptable: The language 〈L〉 | L ∈ L and L is finite is acceptable.⁶
I won’t give a complete proof of this theorem (in part because it requires techniques I haven’t
introduced), but the following lemma is arguably the most interesting component:
Lemma 17. Let L be a set of acceptable languages. If L is not monotone, then AcceptIn(L) is
unacceptable.
Proof: Suppose to the contrary that there is a Turing machine AIL that accepts AcceptIn(L).
Using this Turing machine as a black box, we describe a Turing machine SD that accepts the
unacceptable language SelfDiverge. Fix two Turing machines Y and N such that
Accept(Y ) ∈ L,
Accept(N ) 6∈ L,
and Accept(Y ) ⊆ Accept(N ).
Let w be the input to SD. After verifying that w = 〈M 〉 for some Turing machine M
(and rejecting otherwise), S D writes the encoding 〈WTF〉 or a new Turing machine WTF that
implements the following algorithm:
WTF(x):
write x to second tape
write 〈M 〉 to third tape
in parallel:
run Y on the first tape
run N on the second tape
run M on the third tape
if Y accepts x
accept
if N accepts x and M halts on 〈M 〉
accept
Finally, SD passes the new encoding 〈WTF〉 to AIL . There are two cases to consider:
In short, SD accepts SelfDiverge, which is impossible. We conclude that SD does not exist.
15
Models of Computation Lecture 7: Undecidability [Fa’16]
Proof: (a) The set of finite languages is not monotone: ∅ is finite; Σ∗ is not finite; both ∅
and Σ∗ are acceptable (in fact decidable); and ∅ ⊂ Σ∗ .
(b) The set of infinite acceptable languages is not compact: No finite subset of the infinite
acceptable language Σ∗ is infinite!
(c) The set of regular languages is not monotone: Consider the languages ∅ and {0n 1n | n ≥ 0}.
(d) The set of non-regular acceptable languages is not monotone: Consider the languages
{0n 1n | n ≥ 0} and Σ∗ .
(e) The set of decidable languages is not monotone: Consider the languages ∅ and SelfReject.
(f) The set of undecidable acceptable languages is not monotone: Consider the languages
SelfReject and Σ∗ .
(g) The set L = {L | L ∩ SelfDiverge 6= ∅} is not finitely acceptable. For any string w, deciding
whether {w} ∈ L is equivalent to deciding whether w ∈ SelfDiverge, which is impossible.
(h) If Accept(N ) 6= Σ∗ , then the set {Accept(N )} is not monotone. On the other hand, if
Accept(N ) = Σ∗ , then the set {Accept(N )} is not compact: No finite subset of Σ∗ is equal
to Σ∗ !
Theorem 19. The language NeverLeft := {〈M , w〉 | Given w as input, M never moves left} is
decidable.
Proof: Given the encoding 〈M , w〉, we simulate M with input w using our universal Turing
machine U, but with the following termination conditions. If M ever moves its head to the left,
then we reject. If M halts without moving its head to the left, then we accept. Finally, if M reads
more than |Q| blanks, where Q is the state set of M , then we accept. If the first two cases do not
apply, M only moves to the right; moreover, after reading the entire input string, M only reads
blanks. Thus, after reading |Q| blanks, it must repeat some state, and therefore loop forever
without moving to the left. The three cases are exhaustive.
Theorem 20. The language LeftThree := {〈M , w〉 | Given w as input, M eventually moves left
three times in a row} is undecidable.
Proof: Given 〈M 〉, we build a new Turing machine M 0 that accepts the same language as M and
moves left three times in a row if and only if it accepts, as follows. For each non-accepting state p
16
Models of Computation Lecture 7: Undecidability [Fa’16]
of M , the new machine M 0 has three states p1 , p2 , p3 , with the following transitions:
In other words, after each non-accepting transition, M 0 moves once to the right and then once to
the left. For each transition to accept, M 0 has a sequence of seven transitions: three steps to the
right, then three steps to the left, and then finally accept0 , all without modifying the tape. (The
three steps to the right ensure that M 0 does not fall off the left end of the tape.)
Finally, M 0 moves left three times in a row if and only if M accepts w. Thus, if we could
decide LeftThree, we could also decide Accept, which is impossible.
There is no hard and fast rule like Rice’s theorem to distinguish decidable behaviors from
undecidable behaviors, but I can offer two rules of thumb.
• If it is possible to simulate an arbitrary Turing machine while avoiding the target behavior,
then the behavior is not decidable. For example, there is no algorithm to determine whether
a given Turing machine reenters its start state, or revisits the left end of the tape, or writes
a blank.
• If a Turing machine with the target behavior is limited to a finite number of configurations,
or is guaranteed to force an infinite loop after a finite number of transitions, then the
behavior is likely to be decidable. For example, there are algorithms to determine whether
a given Turing machine ever leaves its start state, or reads its entire input string, or writes
a non-blank symbol over a blank.
Exercises
1. Let M be an arbitrary Turing machine.
(a) Describe a Turing machine M R such that
17
Models of Computation Lecture 7: Undecidability [Fa’16]
5. Let L be a non-empty proper subset of the set of acceptable languages. Prove that the
following languages are undecidable:
(a) RejectIn(L) := 〈M 〉 Reject(M ) ∈ L
(b) HaltIn(L) := 〈M 〉 Halt(M ) ∈ L
(c) DivergeIn(L) := 〈M 〉 Diverge(M ) ∈ L
6. For each of the following decision problems, either sketch an algorithm or prove that the
problem is undecidable. Recall that wR denotes the reversal of string w. For each problem,
the input is the encoding 〈M 〉 of a Turing machine M .
7. For each of the following decision problems, either sketch an algorithm or prove that the
problem is undecidable. Recall that wR denotes the reversal of string w. For each problem,
the input is an encoding 〈M , w〉 of a Turing machine M and its input string w.
18
Models of Computation Lecture 7: Undecidability [Fa’16]
8. Let M be a Turing machine, let w be an arbitrary input string, and let s and t be positive
integers integer. We say that M accepts w in space s if M accepts w after accessing at
most the first s cells on the tape, and M accepts w in time t if M accepts w after at most t
transitions.
9. Let L0 be an arbitrary language. For any integer i > 0, define the language
L i := 〈M 〉 M decides L i−1 .
For which integers i > 0 is L i decidable? Obviously the answer depends on the initial
language L0 ; give a complete characterization of all possible cases. Prove your answer is
correct. [Hint: This question is a lot easier than it looks!]
10. Argue that each of the following decision problems about programs in your favorite
programming language are undecidable.
19
Models of Computation Lecture 7: Undecidability [Fa’16]
? 11. Call a Turing machine conservative if it never writes over its input string. More formally, a
Turing machine is conservative if for every transition δ(p, a) = (q, b, ∆) where a ∈ Σ, we
have b = a; and for every transition δ(p, a) = (q, b, ∆) where a 6∈ Σ, we have b 6= Σ.
Together, these two results imply that every conservative Turing machine accepts the same
language as some DFA, but it is impossible to determine which DFA.
Æ
12. (a) Prove that it is undecidable whether a given C++ program is syntactically correct.
[Hint: Use templates!]
(b) Prove that it is undecidable whether a given ANSI C program is syntactically correct.
[Hint: Use the preprocessor!]
(c) Prove that it is undecidable whether a given Perl program is syntactically correct.
[Hint: Does that slash character / delimit a regular expression or represent division?]
Caveat lector: This note is not even a first draft, but more of a rough sketch, with many
topics still to be written and/or unwritten. But the semester is over, so it’s time to put it down.
Please send bug reports and suggestions to jeffe@illinois.edu.
In the next few pages, I will sketch a universal Turing machine U that uses the input alphabet
{0, 1, [, ], •, |} and a somewhat larger tape alphabet. However, I do not require that the Turing
machines that U simulates have similarly small alphabets, so we first need a method to encode
arbitrary input and tape alphabets.
Encodings
Let M = (Γ , , Σ, Q, start, accept, reject, δ) be an arbitrary Turing machine, with a single half-
infinite tape and a single read-write head. (I will consistently indicate the states and tape symbols
of M in slanted green to distinguish them from the upright red states and tape symbols of U.)
We encode each symbol a ∈ Γ as a unique string |a| of dlg(|Γ |)e bits. Thus, if Γ = {0, 1, $, x, },
we might use the following encoding:
〈0〉 = 001, 〈1〉 = 010, 〈$〉 = 011, 〈x〉 = 100, 〈〉 = 000.
The input string w is encoded by its sequence of symbol encodings, with separators • between
every pair of symbols and with brackets [ and ] around the whole string. For example, with this
encoding, the input string 001100 would be encoded on the input tape as
〈001100〉 = [001•001•010•010•001•001]
Similarly, we encode each state q ∈ Q as a distinct string 〈q〉 of dlg|Q|e bits. Without loss of
generality, we encode the start state with all 1s and the reject state with all 0s. For example, if
Q = {start, seek1, seek0, reset, verify, accept, reject}, we might use the following encoding:
We encode the machine M itself as the string 〈M 〉 = [〈reject〉•〈〉]〈δ〉, where 〈δ〉 is the
concatenation of substrings [〈p〉•〈a〉|〈q〉•〈b〉•〈∆〉] encoding each transition δ(p, a) = (q, b, ∆)
such that q 6= reject. We encode the actions ∆ = ±1 by defining 〈−1〉 := 0 and 〈+1〉 := 1.
Conveniently, every transition string has exactly the same length. For example, with the symbol
and state encodings described above, the transition δ(reset, $) = (start, $, +1) would be encoded
as
[100•011|001•011•1].
Our first example Turing machine for recognizing {0n 1n 0n | n ≥ 0} would be represented by
the following string (here broken into multiple lines for readability):
[000•000][[001•001|010•011•1][001•100|101•011•1]
[010•001|010•001•1][010•100|010•100•1]
[010•010|011•100•1][011•010|011•010•1]
[011•100|011•100•1][011•001|100•100•1]
[100•001|100•001•0][100•010|100•010•0]
[100•100|100•100•0][100•011|001•011•1]
[101•100|101•011•1][101•000|110•000•0]]
Finally, we encode any configuration of M on U’s work tape by alternating between encodings
of states and encodings of tape symbols. Thus, each tape cell is represented by the string
[〈q〉•〈a〉] indicating that (1) the cell contains symbol a; (2) if q 6= reject, then M ’s head is
located at this cell, and M is in state q; and (3) if q = reject, then M ’s head is located somewhere
else. Conveniently, each cell encoding uses exactly the same number of bits. We also surround
the entire tape encoding with brackets [ and ].
For example, with the encodings described above, the initial configuration (start, 001100
Î
, 0)
for our first example Turing machine would be encoded on U’s tape as follows.
Without loss of generality, we assume that the input to our universal Turing machine U is given
on a separate read-only input tape, as the encoding of an arbitrary Turing machine M followed
by an encoding of its input string x. Notice the substrings [[ and ]] each appear only only once
on the input tape, immediately before and after the encoded transition table, respectively. U also
has a read-write work tape, which is initially blank.
2
Models of Computation Lecture 8: Universal Models [Fa’14]
We start by initializing the work tape with the encoding 〈start, x, 0〉 of the initial configuration
of M with input x. First, we write [[〈start〉•. Then we copy the encoded input string 〈x〉 onto
the work tape, but we change the punctuation as follows:
The state encodings 〈start〉 and 〈reject〉 can be copied directly from the beginning of 〈M 〉
(replacing 0s for 1s for 〈start〉). Finally, we move the head back to the start of U’s tape.
At the start of each step of the simulation, U’s head is located at the start of the work tape.
We scan through the work tape to the unique encoded cell [〈p〉•〈a〉] such that p 6= reject.
Then we scan through the encoded transition function 〈δ〉 to find the unique encoded tuple
[〈p〉•〈a〉|〈q〉•〈b〉•〈∆〉] whose left half matches our the encoded tape cell. If there is no such
tuple, then U immediately halts and rejects. Otherwise, we copy the right half 〈q〉•〈b〉 of the
tuple to the work tape. Now if q = accept, then U immediately halts and accepts. (We don’t
bother to encode reject transformations, so we know that q 6= reject.) Otherwise, we transfer
the state encoding to either the next or previous encoded cell, as indicated by M ’s transition
function, and then continue with the next step of the simulation.
During the final state-copying phase, we ever read two right brackets ]], indicating that
we have reached the right end of the tape encoding, we replace the second right bracket with
[〈reject〉•〈〉]] (mostly copied from the beginning of the machine encoding 〈M 〉) and then
scan back to the left bracket we just wrote. This trick allows our universal machine to pretend
that its tape contains an infinite sequence of encoded blanks [〈reject〉•〈〉] instead of actual
blanks .
Example
[[000•011][000•011][000•100][010•010][000•100][000•001]]
Î
First U scans for the first encoded tape cell whose state is not reject. That is, U repeatedly
compares the first half of each encoded state cell on the work tape with the prefix [〈reject〉• of
the machine encoding 〈M 〉 on the input tape. U finds a match in the fourth encoded cell.
[[000•011][000•011][000•100][010•010][000•100][000•001]]
Î
Next, U scans the machine encoding 〈M 〉 for the substring [010•010 matching the cur-
rent encoded cell. U eventually finds a match in the left size of the the encoded transition
[010•010|011•100•1]. U copies the state-symbol pair 011•100 from the right half of this
encoded transition into the current encoded cell. (The underline indicates which symbols are
changed.)
[[000•011][000•011][000•100][011•100][000•100][000•001]]
Î
3
Models of Computation Lecture 8: Universal Models [Fa’14]
The encoded transition instructs U to move the current state encoding one cell to the right. (The
underline indicates which symbols are changed.)
[[000•011][000•011][000•100][000•100][011•100][000•001]]
Î
Finally, U scans left until it reads two left brackets [[; this returns the head to the left end of
the work tape to start the next step in the simulation. U’s tape now holds the encoding of M ’s
configuration (seek0, $$xxx0 Î
, 4), as required.
[[000•011][000•011][000•100][000•100][011•100][000•001]]
Î
ÆÆÆ Simulate a doubly-infinite tape with two stacks, one holding the tape contents to the left of
the head, the other holding the tape contents to the right of the head. For each transition
of a standard Turing machine M , the stack machine pops the top symbol off the (say) left
stack, changes its internal state according to the transition δ, and then either pushes a new
symbol onto the right stack, or pushes a new symbol onto the left stack and then moves the
top symbol from the right stack to the left stack.
4
Models of Computation Lecture 8: Universal Models [Fa’14]
8.4 FRACTRAN
ÆÆÆ FRACTRAN [Conway 1987]: A one-counter machine whose “program” is a sequence of rational
numbers. The counter is initially 1. At each iteration, multiply the counter by the first rational
number that yields an integer; if there is no such number, halt.
• Prove that for any computable function f : N → N, there is a FRACTRAN program that
transforms 2n+1 into 3 f (n)+1 , for all natural numbers n.
• Prove that every FRACTRAN program, given the integer 1 as input, either outputs 1 or
loops forever. It follows that there is no FRACTRAN program for the increment function
n 7→ n + 1.
5
Models of Computation Lecture 8: Universal Models [Fa’14]
• Identity: I x 7→ x
• Constant: K x y 7→ x
• Substitution: S x yz 7→ xz( yz)
Here, x, y, and z are variables representing unknown but arbitrary terms. “Computation” in
the combinator calculus is performed by repeatedly evaluating arbitrary (sub)terms with one of
these three structures, until all such (sub)terms are gone.
For example, the term S(K(SI))K x y (for any terms x and y) evaluates as follows:
Thus, we can define a new combinator R := S(K(SI))K that upon evaluation reverses the next
two terms: R x y 7→ y x.
6
Models of Computation Lecture 8: Universal Models [Fa’14]
ÆÆÆ Wikipedia sketches a direct undecidability proof. Is there a Turing-completeness proof that
avoids λ-calculus?
Exercises
1. A tag-Turing machine has two heads: one can only read, the other can only write. Initially,
the read head is located at the left end of the tape, and the write head is located at the
first blank after the input string. At each transition, the read head can either move one cell
to the right or stay put, but the write head must write a symbol to its current cell and move
one cell to the right. Neither head can ever move to the left.
Prove that any standard Turing machine can be simulated by a tag-Turing machine.
That is, given any standard Turing machine M , describe a tag-Turing machine M 0 that
accepts and rejects exactly the same input strings as M .
2. ? (a) Prove that any standard Turing machine can be simulated by a Turing machine with
only three states. [Hint: Use the tape to store an encoding of the state of the machine
yours is simulating.]
Æ
(b) Prove that any standard Turing machine can be simulated by a Turing machine with
only two states.
(a) Prove that any two-dimensional Turing machine can be simulated by a standard
Turing machine.
(b) Suppose further that we endow our two-dimensional Turing machine with the
following additional actions, in addition to moving the head:
• Insert row: Move all symbols on or above the row containing the head up one
row, leaving the head’s row blank.
• Insert column: Move all symbols on or to the right of the column containing the
head one column to the right, leaving the head’s column blank.
• Delete row: Move all symbols above the row containing the head down one row,
deleting the head’s row of symbols.
• Delete column: Move all symbols the right of the column containing the head
one column to the right, deleting the head’s column of symbols.
7
Models of Computation Lecture 8: Universal Models [Fa’14]
Show that any two-dimensional Turing machine that can add an delete rows can be
simulated by a standard Turing machine.
4. A binary-tree Turing machine uses an infinite binary tree as its tape; that is, every cell in
the tape has a left child and a right child. At each step, the head moves from its current
cell to its Parent, its Left child, or to its Right child. Thus, the transition function of such a
machine has the form δ : Q × Γ → Q × Γ × {P, L, R}. The input string is initially given along
the left spine of the tape.
Show that any binary-tree Turing machine can be simulated by a standard Turing
machine.
5. A stack-tape Turing machine uses an semi-infinite tape, where every cell is actually the
top of an independent stack. The behavior of the machine at each iteration is governed by
its internal state and the symbol at the top of the current cell’s stack. At each transition,
the head can optionally push a new symbol onto the stack, or pop the top symbol off the
stack. (If a stack is empty, its “top symbol” is a blank and popping has no effect.)
Show that any stack-tape Turing machine can be simulated by a standard Turing
machine. (Compare with Problem ??!)
6. A tape-stack Turing machine has two actions that modify its work tape, in addition to
simply writing individual cells: it can save the entire tape by pushing in onto a stack, and it
can restore the entire tape by popping it off the stack. Restoring a tape returns the content
of every cell to its content when the tape was saved. Saving and restoring the tape do not
change the machine’s state or the position of its head. If the machine attempts to “restore”
the tape when the stack is empty, the machine crashes.
Show that any tape-stack Turing machine can be simulated by a standard Turing
machine.
Caveat lector: This is a first draft; some topics still need to be written. Please send bug
reports and suggestions to jeffe@illinois.edu.
δ : Q × Γ → 2Q×Γ ×{−1,+1} .
That is, for each state p and tape symbol a, the output δ(p, a) of the transition function is a set
of triples of the form (q, b, ∆) ∈ Q × Γ × {−1, +1}. Whenever the machine finds itself in state p
reading symbol a, the machine chooses an arbitrary triple (q, b, ∆) ∈ δ(p, a), and then changes
its state to q, writes b to the tape, and moves the head by ∆. If the set δ(p, a) is empty, the
machine moves to the reject state and halts.
The set of all possible transition sequences of a nondeterministic Turing machine N on a
given input string w define a rooted tree, called a computation tree. The initial configuration
(start, w, 0) is the root of the computation tree, and the children of any configuration (q, x, i)
are the configurations that can be reached from (q, x, i) in one transition. In particular, any
configuration whose state is accept or reject is a leaf. For deterministic Turing machines, this
computation tree is just a single path, since there is at most one valid transition from every
configuration.
1
Models of Computation Lecture 9: Nondeterministic Turing Machines [Fa’16]
• N accepts w if and only if there is at least one sequence of valid transitions from the initial
configuration (start, w, 0) that leads to the accept state. Equivalently, N accepts w if the
computation tree contains at least one accept leaf.
• N rejects w if and only if every sequence of valid transitions from the initial configuration
(start, w, 0) leads to the reject state. Equivalently, N rejects w if every path through the
computation tree ends with a reject leaf.
In particular, N can accept w even when there are choices that allow the machine to run forever,
but rejection requires N to halt after only a finite number of transitions, no matter what choices
it makes along the way. Just as for deterministic Turing machines, it is possible that N neither
accepts nor rejects w.
Acceptance and rejection of languages are defined exactly as they are for deterministic
machines. A non-deterministic Turing machine N accepts a language L ⊆ Σ∗ if M accepts all
strings in L and nothing else; N rejects L if M rejects every string in L and nothing else; and
finally, N decides L if M accepts L and rejects Σ∗ \ L.
Proof: I’ll describe a deterministic machine M that performs a breadth-first search of the
computation tree of N . (The depth-first search performed by a standard recursive backtracking
algorithm won’t work here. If N ’s computation tree contains an infinite path, a depth-first search
would get stuck in that path without exploring the rest of the tree.)
2
Models of Computation Lecture 9: Nondeterministic Turing Machines [Fa’16]
At the beginning of each simulation round, M ’s tape contains a string of the form
· · · •• y1 q1 z1 • y2 q2 z2 • · · · • yk qk zk ••
· · · •• y1 q1 z1 • y2 q2 z2 • · · · • y r q r z r •• · · ·
w w
Suppose each transition set δN (q, a) has size at most r. Then after simulating t steps of N ,
the tape string of M encoding O(r t ) different configurations of N and therefore has length
L = O(t r t ) (not counting the initial blanks). If M begins each simulation phase by moving
the initial configuration from the beginning to the end of the tape string, which takes O(t 2 r t )
time, the time for the rest of the the simulation phase is negligible. Altogether, simulating all r t
possibilities for the the tth step of N requires O(t 2 r 2t ) time. We conclude that M can simulate
the first t steps of every computation path of N in O(t 2 r 2t ) time, as claimed.
The running time of this simulation is dominated by the time spent reading from one end of
the tape string and writing to the other. It is fairly easy to reduce the running time to O(t r t ) by
using either two tapes (a “read tape” containing N -configurations at time t and a “write tape”
containing N -configurations at time t + 1) or two independent heads on the same tape (one at
each end of the queue).
δN (q, a) = {δ M (q, a, ω) | ω ∈ Ω}
3
Models of Computation Lecture 9: Nondeterministic Turing Machines [Fa’16]
More generally, if every set δN (p, a) has size r, then we let Ω = {1, 2, . . . , r} and define δ M (q, a, i)
to be the ith element of δN (q, a) in some canonical order.
Now observe that N accepts a string w if and only if M accepts the pair (w, x) for some string
x ∈ Ω∗ , and N rejects w if and only if M rejects the pair (w, x) for all strings x ∈ Ω∗ .
The “advice” formulation of nondeterminism allows a different strategy for simulation by a
standard deterministic Turing machine, which is often called dovetailing. Consider all possible
advice strings x, in increasing order of length; listing these advice strings is equivalent to
repeatedly incrementing a base-r counter. For each advice string x, simulate M on input (w, x)
for exactly |x| transitions.
Dovetail M (w):
for t ← 1 to ∞
done ← True
for all strings x ∈ Ω t
if M accepts (w, x) in at most t steps
accept
if M (w, x) does not halt in at most t steps
done ← False
if done
reject
The most straightforward Turing-machine implementation of this algorithm requires three tapes:
A read-only input tape containing w, an advice tape containing x (which is also used as a timer
for the simulation), and the work tape. This simulation requires O(t r t ) time to simulate all
possibilities for t steps of the original non-deterministic machine N .
If we insist on using a standard Turing machine with a single tape and a single head, the
simulation becomes slightly more complex, but (unlike our earlier queue-based strategy) not
significantly slower. This standard machine S maintains a string of the form •w• x •z, where z
is the current work-tape string of M (or equivalently, of N ), with marks (on a second track)
indicating the current positions of the heads on M ’s work tape and M ’s advice tape. Simulating
a single transition of M now requires O(|x|) steps, because S needs to shuttle its single head
between these two marks. Thus, S requires O(t 2 r t ) time to simulate all possibilities for t
steps of the original non-deterministic machine N . This is significantly faster than the queue-
based simulation, because we don’t record (and therefore don’t have to repeatedly scan over)
intermediate configurations; recomputing everything from scratch is actually cheaper!
Proof: Let L ⊆ Σ∗ be an arbitrary language in NP, over some fixed alphabet Σ. There must be
an integer k and Turing machine M that satisfies the following conditions:
4
Models of Computation Lecture 9: Nondeterministic Turing Machines [Fa’16]
• For all strings w ∈ L, there is at least one string x ∈ Σ∗ such that M accepts the string w x.
• For all strings w 6∈ L and x ∈ Σ∗ , M rejects the string w x.
• For all strings w, x ∈ Σ∗ , M halts on input w x after at most max{1, |w|k } steps.
Now suppose we are given a string w ∈ Σ∗ . Let n = |w| and let N = max{1, |w|k }. We
construct a boolean formula Φw that is satisfiable if and only if w ∈ L, by following the execution
of M on input w x for some unknown advice string x. Without loss of generality, we can assume
that |x| = N − n − 1 (since we can extend any shorter string x with blanks.) Our formula Φw uses
the following boolean variables for all symbols a ∈ Γ , all states q ∈ Q, and all integers 0 ≤ t ≤ N
and 0 ≤ i ≤ N + 1.
Q 0,1,start = True
Q 0,1,q = False for all q 6= start
H0,i,q = False for all i 6= 1 and q ∈ Q
• Uniqueness: The variables T0,i,a with n+2 ≤ i ≤ N represent the unknown advice string x;
these are the “inputs” to Φw . We need some additional constraints ensure that for each i,
exactly one of these variables is True:
_ ^
T0, j,a ∧ T0, j,a ∨ T0, j,b
a∈Γ a6= b
_ ^
Tt,i,b = Q t−1,i,p ∧ Tt−1,i,a ∨ Q t−1,i,q ∧ Tt−1,i,b
δ(p,a)=(·,b,·) q∈Q
5
Models of Computation Lecture 9: Nondeterministic Turing Machines [Fa’16]
_
N _
N
z= Q t,i,accept
t=0 i=1
By definition, Φw is satisfiable if and only if some input values T0,i,a , all constraints are
satisfied, including acceptance. A straightforward induction argument implies that even without
the acceptance constraint, any assignment of values to the unknown variables T0,i,a that satisfies the
uniqueness constraints determines unique values for the other variables in Φw , which consistently
describe the execution of M . To satisfy the acceptance constraint, this execution of M must lead
to the accept state. Thus, Φw is satisfiable if and only if there is a string x ∈ Γ ∗ such that M
accepts the input w x. We conclude that Φw is satisfiable if and only if w ∈ L.
It remains only to argue that the reduction requires only polynomial time. For any input
string w of length n, the formula Φw has O(N 2 ) variables and O(N 2 ) constraints (where the
hidden constants depend on the machine M ). Every constraint except acceptance has constant
length, so altogether Φw has length O(N 2 ). Moreover, we can construct Φw in O(N 2 ) = O(n2k )
time.
In conclusion, if we could decide SAT for formulas of size M in O(M c ) time, then we could
decide membership in L in O(n2kc ) time, which implies that L ∈ P.
Exercises
1. Prove that the following problem is NP-hard, without using the Cook-Levin Theorem. Given
a string 〈M , w〉 that encodes a non-deterministic Turing machine M and a string w, does M
accept w in at most |w| transitions?