Theory of Computation Notes | B.Sc. (Computer Science) Semester 3 | Mumbai University | munotes

A search box that accepts patterns. You want to find every line in a file that begins with a capital letter and ends in a semicolon. The pattern language that does this is called a regular expression, and the whole of the fourth block of Module 1 is about it. The interesting part is not that it works. It is that there is a precise boundary to what patterns of this kind can express, and "lines with the same number of opening and closing brackets" is on the far side of it. You will prove that in chapter 37.

A compiler. Before your Java compiler can object to a missing bracket, it has to know what a correctly bracketed program looks like. The description it uses is a grammar, which is the third block of Module 1, and the machine that reads it is a pushdown automaton, which opens Module 2. When your compiler reports a syntax error, the thing that found it is one of the machines in this book.

A lock screen. A four digit PIN entry is a machine with a small number of states: how many digits have been typed, and whether they were right. Nothing else needs to be remembered. That is a finite automaton, and it is the second block of Module 1.

A marking scheme. Suppose a lecturer wants a program that reads a student's submitted program and reports whether it will ever loop for ever. Every student wants this to exist. It cannot. That is the halting problem, it is proved in chapter 74, and the proof takes half a page.

What the word computation is standing for

The word is doing a lot of work, so it is worth being careful about it early.

A problem here always means a question about an input, and we shall almost always arrange for the answer to be yes or no. "Is this number prime?" is a problem. "Is this bracket sequence balanced?" is a problem. "Sort this list" looks different, but it can be turned into a yes or no question, and reducing everything to yes or no is what makes a mathematical treatment possible.

An instance of a problem is one particular input. The number 91 is an instance of the primality problem, and the answer for that instance is no, because 91 is 7 times 13.

An algorithm is a finite list of unambiguous instructions that, followed exactly, produces the answer for every instance, and stops. Each of those words matters. Finite, so it can be written down. Unambiguous, so no judgement is needed at any step. Every instance, so it is not a method that works for the cases we tried. And stops, because a procedure that runs for ever has not answered anything.

Computation is what happens when a machine carries out an algorithm on an instance. This subject makes "machine" precise, four times over, each time a little stronger.

Why the models are so simple

The first thing a student notices about this paper is that the machines are absurdly primitive. A Turing machine has one tape, one head, and no arithmetic. That is not a historical accident or a simplification for teaching. It is the point, and there are two reasons for it.

The first is that a simple model can be reasoned about. You cannot prove anything about a machine whose description takes ten thousand pages. You can prove a great deal about a machine whose description takes five lines, and a proof about the simple machine is worth having only if the simple machine is as strong as the complicated one.

The second is that it turns out to be as strong. This is the single most surprising result in the subject, and chapter 72 is about it: every attempt anybody has made to define a more powerful machine, by adding tapes, heads, dimensions, randomness or guessing, has produced a machine that solves exactly the same set of problems. That is the Church Turing thesis, and it is what licenses the whole enterprise. When we prove that no Turing machine can solve a problem, we are entitled to say that no computer can.

Where the subject came from

Three dates are worth remembering, because they explain why the subject looks the way it does.

In 1936 Alan Turing published "On Computable Numbers, with an Application to the Entscheidungsproblem" in the Proceedings of the London Mathematical Society, pages 230 to 265. The paper's own first page records that it was received on 28 May 1936 and read on 12 November 1936. Turing was not designing a computer. He was answering a question David Hilbert had asked about mathematics, and the machine was a tool invented for the proof. The tool turned out to be more important than the answer.

In 1951 Stephen Kleene, working at RAND, wrote up finite automata and the expressions that describe them, in a research memorandum numbered RM-704 and titled "Representation of Events in Nerve Nets and Finite Automata". Its own summary dates the investigations it reports to August 1951. And in 1956 Noam Chomsky, studying human language rather than machines, wrote "Three Models for the Description of Language", which his own archive dates to September 1956. The classification of grammars in chapter 26 is from that paper.

So the four machines in this book were invented by a logician, an electrical engineer and a linguist, none of whom was trying to build a computer. That is worth knowing when the subject feels disconnected from programming. It was not derived from programming; programming arrived later and turned out to fit.

How this book is arranged, and why the order is MU's

The chapters follow the University's printed syllabus in her own order, under her own headings. That order is also a good teaching order, which is not always true of a syllabus, and it is worth seeing why before starting.

Module 1 builds the weakest machine first, the finite automaton, and pushes it until it breaks. Then it introduces grammars, which describe languages from the other direction, and shows that the weakest grammar describes exactly what the weakest machine accepts. Then it takes the next grammar up, the context free one, and Module 2 builds the machine that matches it. Then it does the same thing twice more. By the end there are four machines, four kinds of grammar, and a proof that they pair off.

What it does NOT mean

This is not a paper about programming languages. The word "language" in this subject means something much simpler: a set of strings. The language of a machine is just the collection of inputs it says yes to. It has no syntax, no semantics and no compiler.

A machine here is not a computer. It is a mathematical object, defined by a small number of sets and a function. Nothing is ever built. Asking how fast a Turing machine runs in megahertz is asking the wrong sort of question about the wrong sort of object.

"Cannot be computed" is not a statement about today's computers. It is not "no current machine can do this", nor "we have not found a method yet". It means no method exists, and never will, and that this has been proved.

Quick revision

• The theory of computation studies which problems a machine can solve, and at what cost in time and

space.

• Four questions: what is computable at all; what is computable quickly; how much machine a job

needs; and how we can be sure.

• A problem is a question about an input; an instance is one input; an algorithm is a finite,

unambiguous method that answers every instance and stops.

• A language, in this subject, is a set of strings, and the language of a machine is the set of

inputs it accepts.

• The models are deliberately primitive, because simple models can be proved things about, and

because they turn out to be as strong as complicated ones.

• Turing 1936, pages 230 to 265; Kleene's RAND memorandum RM-704 of 1951; Chomsky's

three models paper of 1956.

• MU examines this paper in one hour for 30 marks, in three questions of two answers each, so every

topic in this book has to be answerable in about ten minutes.

Test yourself

1. Define an algorithm, and say what each part of the definition rules out. A finite list of unambiguous instructions that, followed exactly, produces the correct answer for every instance of the problem and then stops. Finite rules out a method that cannot be written down; unambiguous rules out a step requiring judgement; every instance rules out a method that works only on the cases tried; and stopping rules out a procedure that runs for ever without answering.

2. Give one reason the machines in this subject are defined so simply. Because a proof can be carried out about a five line definition and cannot be carried out about a real processor, and because the simple machines turn out to solve exactly the same problems as any richer model anyone has proposed.

3. What does the word language mean in this paper? A set of strings over a fixed alphabet. Nothing more: no syntax rules beyond membership, and no meaning attached to the strings.

4. State the four questions the subject answers. What can be computed at all; what can be computed quickly; how powerful a machine a given job needs; and how we can be certain of the answers.

5. A student says a problem is uncomputable because no fast enough computer exists yet. Uncomputable means no algorithm exists at all, which is a proved mathematical statement about the problem and not about any machine. A problem that needs a faster computer is computable but expensive, which is a question for the complexity block of Module 2, not the computability block.

Careful. The empty set and the set containing the empty set are different. { } has no elements. { { } } has one element, which happens to itself be a set with no elements. The same distinction, with strings instead of sets, catches students in chapter 3.

Subset. A is a subset of B when every element of A is also an element of B. The empty set is a subset of every set, and every set is a subset of itself, both of which follow straight from the definition rather than being special cases. A is a proper subset of B when A is a subset of B and A is not equal to B.

Equality. Two sets are equal when each is a subset of the other. That sounds like a roundabout way to say the obvious, and it is in fact the most useful sentence in this chapter, because it is the shape of almost every proof in the book: to prove two languages are the same, prove each is contained in the other. Chapter 24 does it for a grammar, chapter 16 for two machines.

Cardinality. The number of elements, written with vertical bars. So the size of {0, 1} is 2. A set is finite when its cardinality is a whole number, and infinite otherwise. Chapter 7 is about the fact that there are two different sizes of infinite, which is the most consequential fact in the whole paper.

Disjoint. Two sets are disjoint when they have no element in common.

The operations

Six, and each one has a use in this book.

The complement needs a universe. "Everything not in A" is meaningless until we say what everything is. In this book the universe is almost always the set of all strings over a fixed alphabet, which chapter 3 calls Sigma star, and the complement of a language is every string the language does not contain. Forgetting to fix the universe is the commonest error in a closure proof.

The Cartesian product is how two machines are run at once. In chapter 38 we prove the regular languages are closed under intersection by building a machine whose states are pairs: one component tracks where the first machine would be, the other where the second would be. The set of those pairs is exactly the Cartesian product of the two state sets. The same construction is what the checker behind this book uses to decide whether two machines are equal.

The power set is how a nondeterministic machine is made deterministic. Chapter 16 builds, out of a machine that may be in several states at once, a machine whose single state records which set of old states we could be in. Its states are the subsets of the old state set, which is the power set, and that is where the construction gets its name.

Worked example

Let A = {0, 1} and B = {1, 2}, with the universe U = {0, 1, 2, 3}.

The size of A is 2 and the size of B is 2, so the size of A times B is 4, and in general the size of a Cartesian product is the product of the sizes. That is why the product machine of chapter 38 can have as many states as the two machines multiplied together.

Now the power set of A. A has two elements, so it has four subsets:

A set with n elements has exactly 2 to the n subsets, and this is worth proving rather than accepting, because the argument is used again in chapter 16. To build a subset, go through the n elements one at a time and make an independent yes or no decision about each. That is n decisions with 2 choices each, so 2 times 2 times ... n times, which is 2 to the n. The empty set comes from saying no n times and the whole set from saying yes n times, which is why both are subsets.

That number is also the reason the subset construction is expensive: a nondeterministic machine with n states becomes a deterministic machine with up to 2 to the n states, and chapter 14 shows a family of machines where it really is that bad.

The laws

These get used, mostly without being named, in the closure proofs of chapters 38 and 51. Each one holds for sets exactly as it holds for the logical connectives.

De Morgan's law is the one that earns marks, because it converts a union into an intersection and back. Chapter 38 uses it exactly once, and it is the whole of the proof: the regular languages are closed under complement and under union, and De Morgan turns those two facts into closure under intersection with no new construction at all.

What it does NOT mean

A set is not a list. It has no order and no repeats. If order matters you want a sequence or a tuple, written with round brackets: (0, 1) is not the same as (1, 0), and a string, which chapter 3 defines, is a sequence and not a set.

A subset is not an element. {0} is a subset of {0, 1}. It is not an element of {0, 1}. It IS an element of the power set of {0, 1}. Getting this wrong makes chapter 16 unreadable, because there the elements of the new machine's state set are subsets of the old machine's state set.

The empty set is not nothing. It is a set, it has a size, and a machine can accept the language it denotes.

Quick revision

• A set is an unordered collection of distinct elements, and the only question is membership.
• Written by listing, by a property with a colon read "such that", or by a generating rule.
• Subset: every element of one is an element of the other. Equal: each is a subset of the other, and

this is the shape of most proofs in the book.

• Cardinality is the number of elements; the empty set { } has none and is a subset of everything.
• Six operations: union, intersection, difference, complement, Cartesian product, power set.
• A set of n elements has 2 to the n subsets, which is why the subset construction of chapter 16 can

be exponential.

• The complement is meaningless without a stated universe; here the universe is Sigma star.
• De Morgan's law is what turns closure under complement and union into closure under intersection.

Test yourself

1. Write, by a property, the set of all strings of 0s and 1s of even length. { w : w is a string over {0, 1} and the length of w is even }. Note this set is infinite, and it contains the empty string, whose length is 0, which is even.

2. How many subsets does a set of 5 elements have, and why?

1. Each of the 5 elements is independently either in or out of a subset, giving 2 to the 5 choices.

3. Are { } and { { } } the same set? Give their sizes. No. { } has size 0. { { } } has size 1, its single element being the empty set.

4. A = {a, b}, B = {b, c}, universe {a, b, c, d}. Give A union B, A intersect B, A minus B and B'. {a, b, c}; {b}; {a}; {a, d}.

5. Using De Morgan's law, express A intersect B using only union and complement. A intersect B = (A' union B')'. This is the step chapter 38 uses to prove the regular languages are closed under intersection without building a new machine.

6. Why does this subject care about the Cartesian product? Because running two machines side by side on the same input is done by building one machine whose states are pairs of states, and the set of those pairs is the Cartesian product of the two state sets.

The empty string is the hardest of the three definitions for a beginner, because it feels like nothing. It is not nothing. It is a perfectly good string that a machine can be handed, and whether a machine accepts it is a separate question from everything else, which is exactly why it is the string students forget to test. In this book every set of test strings printed under a machine includes epsilon when the machine accepts it, and the checker runs it.

Operations on strings

Concatenation. Writing one string after another. If x is ab and y is ba then the concatenation of x and y is abba. It is written by juxtaposition, xy, and it is associative but not commutative: ab followed by ba is abba, and ba followed by ab is baab.

The empty string is the identity for concatenation, which is the formal reason it has to exist:

Powers. w to the k means w concatenated with itself k times, and w to the 0 is defined to be epsilon. So a to the 3 is aaa, and (ab) to the 2 is abab.

The definition of w to the 0 as epsilon is a convention, but not an arbitrary one: it is forced if the law w to the m followed by w to the n equals w to the (m plus n) is to hold for every m and n including zero.

Reversal. The string written backwards, written w to the R. The reversal of abb is bba, and the reversal of epsilon is epsilon. A string equal to its own reversal is a palindrome, and the language of palindromes is the witness language in chapters 56 and 57.

Prefix, suffix, substring. A prefix is any number of symbols from the front, a suffix any number from the back, and a substring any run of consecutive symbols from anywhere. For abc the prefixes are epsilon, a, ab, abc; the suffixes are epsilon, c, bc, abc; and the substrings add b and bc and so on. Note that epsilon and the whole string are always a prefix, a suffix and a substring of any string.

A proper prefix is a prefix other than the string itself.

Careful with substring and subsequence. A substring must be consecutive. ac is not a substring of abc, because b is in the way. It is a subsequence, which allows gaps. This book uses substring in the strict sense throughout.

Sigma star and Sigma plus

These two are used on almost every later page.

So Sigma plus is Sigma star with epsilon removed, and Sigma star is Sigma plus with epsilon put back.

Sigma star is infinite for any alphabet, because for each length there is at least one string and there is no longest length. But it is infinite in the tamest possible way: the strings can be listed in one endless sequence with none left out, first by length and then alphabetically within a length. Over {a, b} that listing begins

This ordering is called canonical order, and it matters twice. Chapter 7 uses it to show Sigma star is countable, which is the first half of the argument that some languages have no machine. And it is the order the checker behind this book uses when it compares two machines over every string up to a given length: it is exhaustive, so nothing can hide in a gap.

The number of strings of length exactly k over an alphabet of size n is n to the k. Over {a, b} there are 2 strings of length 1, 4 of length 2, 8 of length 3. So the number of strings of length at most k is 1 plus n plus n squared and so on, and for {a, b} with k equal to 3 that is 1 plus 2 plus 4 plus 8, which is 15.

The language

A language over Sigma is any subset of Sigma star. That is the whole definition, and it is worth pausing on how permissive it is. A language need not be describable, need not be interesting, and need not have a machine. It is just a set of strings.

Some examples over {a, b}:

The two that look the same and are not. { } is the language with no strings in it. {ε} is the language with exactly one string in it, that string being the empty one. A machine that accepts { } accepts nothing and says no to every input including the empty input. A machine that accepts {ε} says yes to the empty input and no to everything else. They are different machines, they differ on exactly one input, and mixing them up is the single commonest slip in the first two weeks of this paper. It is the same distinction as the empty set against the set containing the empty set, from chapter 2.

The operations on languages, briefly

Chapter 28 treats these properly. They are named here because the next few chapters use them.

Since a language is a set, all the set operations apply: union, intersection, difference, complement. Two more come from strings rather than sets. The concatenation of languages L and M is every string made by taking one string from L and one from M in that order. The Kleene closure of L, written L star, is every string made by concatenating any number of strings from L, including none at all, so L star always contains epsilon.

Worked example

Let Sigma = {0, 1}, x = 01 and y = 110.

Now a language. Let L be the set of strings over {0, 1} that begin with 0 and have length 3. Listing it is quick, because the first symbol is fixed and the other two are free, so there are 2 times 2 which is 4 strings:

And let M be the set of strings over {0, 1} of length at most 1, which is {ε, 0, 1}. Then the concatenation of L and M has 4 times 3 which is 12 strings if they are all different, and they are, because the pieces have different lengths or different last symbols. The three shortest are 000, 001 and 010 themselves, obtained by taking epsilon from M.

What it does NOT mean

A language is not a programming language. It has no grammar rules of its own, no meaning and no compiler. The word is borrowed from linguistics because Chomsky's work arrived through linguistics.

A string is not a set. Order matters and repeats count, so ab is not ba and aa is not a.

The empty string is not the empty language. One is a string, the other is a set of strings. See the paragraph above on { } against {ε}.

Sigma star is not the same as "all languages". Sigma star is a set of strings. The set of all languages over Sigma is the power set of Sigma star, which is a much bigger object, and chapter 7 shows exactly how much bigger.

Quick revision

• Alphabet Sigma: a finite non empty set of symbols.
• String: a finite sequence of symbols from Sigma. Length counts repeats. The empty string is

epsilon, of length 0.

• Concatenation is associative, not commutative, with epsilon as its identity. w to the 0 is epsilon.
• Reversal, prefix, suffix, substring (consecutive) and subsequence (gaps allowed).
• Sigma star: all strings. Sigma plus: all non empty strings. Both infinite, and Sigma star is

countable in canonical order.

• Strings of length exactly k over an alphabet of size n: n to the k.
• Language: any subset of Sigma star.
• { } and {ε} are different languages, and the machines that accept them differ on one input.

Test yourself

1. Over {a, b}, how many strings have length exactly 4, and how many have length at most 4? 2 to the 4, which is 16, of length exactly 4. At most 4 gives 1 plus 2 plus 4 plus 8 plus 16, which is 31.

2. Give all the prefixes and all the suffixes of abb. Prefixes: ε, a, ab, abb. Suffixes: ε, b, bb, abb.

3. Is ac a substring of abc? Is it a subsequence? Not a substring, because a substring must be consecutive and b lies between them. It is a subsequence.

4. Write the language of strings over {0, 1} of length 2 that contain at least one 1. {01, 10, 11}. Note 00 is excluded and the language is finite with three members.

5. What is the difference between { } and {ε}, and how would a machine show it? { } contains no strings, so its machine rejects every input including the empty one; it has no final state reachable. {ε} contains exactly the empty string, so its machine accepts the empty input and rejects everything else; its start state is final and no other reachable state is.

6. Simplify x to the 0 followed by x to the 2, where x is ab. x to the 0 is epsilon, and epsilon is the identity for concatenation, so the result is x to the 2, which is abab.

Symmetric. Whenever a is related to b, b is related to a. "Has the same length as" is symmetric. "Is less than" is not.

Antisymmetric. If a is related to b and b to a, then a and b are the same element. "Is less than or equal to" is antisymmetric. This one is here for completeness; it belongs to orderings rather than to equivalences and this book does not use it again.

Transitive. Whenever a is related to b and b to c, a is related to c. "Is less than" is transitive. "Is the parent of" is not.

A useful check on all four is that a relation can fail a property because of a single pair. To show a relation is not transitive it is enough to produce one a, b, c where the first two links hold and the third does not. To show it is transitive you must argue about all of them, which is why proofs go one way and counterexamples the other.

The equivalence relation

A relation is an equivalence relation when it is reflexive, symmetric and transitive, all three.

The three together say, in ordinary words, that the relation behaves the way equality behaves. Every thing is like itself. If one thing is like a second the second is like the first. And likeness passes along a chain.

Examples over strings, which is where this book uses them:

Equivalence classes and the partition

This is the part that does the work in chapters 20 and 21.

Given an equivalence relation R on A and an element a of A, the equivalence class of a is the set of everything related to a. It is written with square brackets:

Three facts follow, and each is a one line proof from one of the three properties.

Every element is in its own class, because R is reflexive, so no element is left out.

Two classes are either identical or disjoint. Suppose some element x lies in both [a] and [b]. Then x R a and x R b. By symmetry a R x, and then by transitivity a R b, and from there every element of [a] is in [b] and conversely. So they are the same class. There is no such thing as two classes that partly overlap.

So the classes cut A into pieces with nothing left over and nothing counted twice. A family of non empty, pairwise disjoint sets whose union is the whole of A is called a partition of A. So every equivalence relation gives a partition, and going the other way, every partition gives an equivalence relation, namely "is in the same block as".

The number of classes is called the index of the relation. It may be finite even when A is infinite, and that single sentence is the whole content of the Myhill Nerode theorem in chapter 21: a language is regular exactly when a certain equivalence relation on the infinite set Sigma star has finitely many classes, and the number of classes is the number of states in the smallest machine.

Worked example

Let A be the set of strings over {a, b}, and let x R y mean "x and y have the same number of a, counted modulo 3", that is, the two counts leave the same remainder on division by 3.

Is it an equivalence relation? Reflexive, because any count leaves the same remainder as itself. Symmetric, because sameness of remainder does not depend on order. Transitive, because if the first and second agree, and the second and third agree, the first and third agree. So yes.

Its classes. The remainder can be 0, 1 or 2, so there are exactly three classes, whatever the strings look like:

So an infinite set has been cut into three blocks. That is an index of 3.

Now notice what the table is. It is a machine. Reading a b keeps you in your block. Reading an a moves you on one block, from [ε] to [a] to [aa] and back to [ε]. Three blocks, three states, and the block you are in is everything you need to remember. Chapter 13 builds exactly this machine, and chapter 21 proves that this is not a coincidence but a theorem.

Closures: reflexive, transitive, and the star

One more piece of notation, needed in chapter 23 for derivations.

Given a relation R that is missing a property, the closure of R with respect to that property is the smallest relation containing R that has it.

The reflexive closure adds the pair (a, a) for every a and nothing else. The transitive closure, written R plus, adds a pair (a, c) whenever R has a chain from a to c of one or more steps. The reflexive transitive closure, written R star, is the transitive closure with the reflexive pairs added, so it holds (a, c) whenever there is a chain of zero or more steps from a to c.

The zero step case is why R star relates every element to itself. This is exactly the notation a grammar uses: one arrow means one step of derivation, and the starred arrow means any number of steps including none, so a sentential form always derives itself.

Worked, on A = {1, 2, 3} with R = {(1,2), (2,3)}:

The pair (1,3) appears in R plus because there is a two step chain from 1 to 3. It is not in R itself.

What it does NOT mean

An equivalence relation is not equality. It behaves like equality but it identifies things that are genuinely different: two states of a machine can be equivalent without being the same state, and that is the whole point of minimising.

Transitive does not mean reflexive. "Is less than" is transitive and not reflexive. The three properties are independent, and an examination answer that says a relation is an equivalence because it is transitive has proved a third of what was asked.

A partition's blocks are never empty and never overlap. A "partition" with an empty block, or with two blocks sharing an element, is not a partition, and the corresponding relation is not an equivalence.

The index can be finite when the set is infinite. This is not a paradox and it is the single most useful fact in the chapter.

Quick revision

• A relation on A is any subset of A times A, that is, any set of ordered pairs. a R b means (a, b)

is in it.

• Reflexive: a R a always. Symmetric: a R b gives b R a. Transitive: a R b and b R c give a R c.
• Equivalence relation: all three of reflexive, symmetric and transitive.
• The class [a] is everything related to a. Classes are non empty, pairwise disjoint, and cover A, so

they partition A. The number of them is the index.

• Every partition gives an equivalence relation and every equivalence relation gives a partition.
• An infinite set can have an equivalence relation of finite index, and that is what makes a finite

machine possible for an infinite language.

• R star, the reflexive transitive closure, relates a to c when there is a chain of zero or more

steps, and is the notation a derivation uses.

Test yourself

1. Is "has the same last symbol as" an equivalence relation on Sigma star? Justify. No. It fails reflexivity for the empty string, which has no last symbol, so the pair (ε, ε) is not in the relation. On Sigma plus, where every string has a last symbol, it is an equivalence relation.

2. Give the equivalence classes of "same length modulo 2" on strings over {a}. Two classes: {ε, aa, aaaa, ...} and {a, aaa, aaaaa, ...}. The index is 2.

3. State the three properties and give a relation with exactly two of them. Reflexive, symmetric, transitive. "Is less than or equal to" on numbers is reflexive and transitive but not symmetric.

4. What is the index of a relation, and why does this subject care? The number of its equivalence classes. It matters because chapter 21 proves a language is regular exactly when a certain relation on Sigma star has finite index, and the index is then the number of states in the minimal machine.

5. For R = {(1,2), (2,1)} on {1, 2, 3}, give R star. {(1,1), (2,2), (3,3), (1,2), (2,1)}. The reflexive pairs are added for all three elements, and the two step chains from 1 to 1 and from 2 to 2 are already covered by those.

6. Why can two equivalence classes never partly overlap? If x lies in both [a] and [b] then x R a and x R b, so by symmetry and transitivity a R b, and the two classes contain exactly the same elements. Overlap therefore forces identity.

One to one, onto, and both

Three properties a function may have. All three are asked directly in examinations, and two of them are used in this book's proofs.

One to one, also called injective: different inputs always give different answers. Equivalently, if f(x) equals f(y) then x equals y. The function that doubles a whole number is one to one. The function that gives the length of a string is not, because ab and ba both give 2.

Onto, also called surjective: every element of the codomain is reached, so the range is the whole codomain. Length, from strings over {a} to whole numbers, is onto, because every number is the length of some string of a's. Doubling, from whole numbers to whole numbers, is not onto, because 3 is not double anything.

Bijective: both one to one and onto. A bijection pairs the two sets off exactly, one element of A for one element of B with nothing left over on either side.

Bijections are how the two sizes of infinity in chapter 7 are defined. A set is countable when there is a bijection between it and the whole numbers, that is, when its elements can be listed in one endless sequence with none repeated and none missed.

Composition

If f goes from A to B and g goes from B to C, then applying f and then g is a function from A to C, written g after f, with (g after f)(a) equal to g(f(a)).

Note the order: the one written on the right is applied first. It is written that way so that the notation matches the nesting of the brackets, and it catches students every time.

Composition is how the extended transition function of chapter 11 works. Running a machine on a string of length 5 is the transition function composed with itself five times, and the reason a machine's behaviour on a whole string is well defined is that composing functions gives a function.

Worked example

Let f be the function from strings over {a, b} to whole numbers that returns the number of a in the string.

Is it a function? Yes. Every string has a definite number of a in it, so there is at least one answer, and a string has only one count, so there is at most one.

Domain, codomain, range. The domain is all strings over {a, b}. The codomain is the whole numbers. The range is also the whole numbers, because for any n the string a to the n has exactly n of them.

One to one? No. f(ab) and f(ba) are both 1, and ab is not ba.

Onto? Yes, by the reason just given.

Now a transition function, which is the one that matters. Take the three state machine that counts a modulo 3 from chapter 4. Its transition function delta has domain {q0, q1, q2} times {a, b} and codomain {q0, q1, q2}:

Accepts: ε, b, aaa, bbb, aaab

Rejects: a, aa, ab, aab

Every cell of C1 is filled, so delta is total, and every cell holds exactly one state, so it is a function rather than a relation. Six pairs in the domain, six entries in the table. That correspondence is worth noticing: a transition table is nothing but a function written out in full, and its number of cells is the size of the domain, which is the number of states multiplied by the number of symbols.

Is delta one to one? No, and it does not need to be: delta(q0, b) and delta(q1, a) are different inputs, and in this machine delta(q0, b) is q0 while delta(q1, a) is q2, but delta(q0, b) and delta(q0, b) aside, plenty of pairs collide in other machines. Nothing in the definition of an automaton requires the transition function to be one to one, and a machine whose transitions are one to one is a special and rather rare object.

What it does NOT mean

The codomain is not the range. The codomain is declared when the function is declared; the range is discovered by looking at what comes out. A function is onto exactly when they coincide.

A function is not required to be one to one. Most functions in this book are not.

A partial function is not a broken function. It is a perfectly respectable object and it is what a machine with missing moves has. What is not allowed, ever, is two answers for one input: that is a relation, and a machine whose transitions do that is nondeterministic, which is chapter 14.

f(a) is an element, f is a function. Writing "the function f(x)" is sloppy and it leads to confusion later when the same letter is used for a function on strings and a function on symbols.

Quick revision

• A function from A to B pairs each element of A with exactly one element of B: at least one, at most

one.

• Domain A; codomain B; range is the part of B actually reached, and is a subset of the codomain.
• Total: every element of the domain has an answer. Partial: some may not, which is a machine with

missing moves, completed by adding a dead state.

• One to one: different inputs, different answers. Onto: every element of the codomain is reached.

Bijective: both, and bijections define countability.

• Composition g after f applies f first. The extended transition function is composition repeated.
• A transition table is a function written out in full; it has one cell per pair of state and symbol.

Test yourself

1. Give the domain, codomain and range of the transition function of a DFA with 4 states over {0, 1}. Domain: the 4 states times {0, 1}, so 8 pairs. Codomain: the 4 states. The range is whichever states actually appear in the table, which may be fewer than 4.

2. Is the reversal function on strings one to one? Onto? Bijective? All three. Two different strings have different reversals, every string is the reversal of something, namely its own reversal, and so reversal is a bijection from Sigma star to itself.

3. A machine is drawn with no move from state q on symbol b. Is its transition function total? What do you do about it? It is partial. Add a dead state that is not final, send the missing move there, and give the dead state a move to itself on every symbol. The language accepted does not change.

4. Explain why a transition function may not be a relation that gives two answers. Because a function must give at most one answer per input. A transition that offers two next states is a relation, and a machine built on one is nondeterministic, which is a different definition with a set as its codomain.

5. If f has 8 pairs in its domain and 4 elements in its codomain, can f be one to one? No. Eight inputs cannot have eight distinct answers among four possible answers, so at least two inputs must share one. This is the pigeonhole principle of chapter 6.

Three: proof by contradiction

Assume the statement is false, derive something impossible, and conclude the statement is true.

This is the technique the two most important results in the paper use, so it deserves the most attention. The halting problem in chapter 74 is a proof by contradiction, and so is every application of the pumping lemma in chapter 37.

Statement. There is no largest whole number.

Proof. Suppose there were. Call it N. Then N plus 1 is a whole number and is larger than N, which contradicts N being the largest. So there is no largest whole number.

The shape, in four lines, which is worth learning as a template:

1. Suppose, for contradiction, that the statement is false.
2. Write out exactly what that assumption gives you.
3. Derive two things that cannot both hold.
4. Conclude that the assumption was wrong, so the statement is true.

Step 2 is where students lose marks. "Suppose the language is regular" is not enough; the next line has to say what being regular gives you, namely a machine with some definite finite number of states, and it is that number the rest of the argument attacks.

Four: proof by induction

Used to prove a statement about every whole number, or about every string, by proving it for the smallest case and then proving that each case carries the next one.

The two parts.

Base case. Prove the statement for the starting value, usually 0 or 1, or for the empty string.

Inductive step. Assume the statement holds for some value n, which is called the inductive hypothesis, and prove it holds for n plus 1.

Once both are done, the statement holds for every value from the base upwards, because the base gives the first, the step carries the first to the second, the second to the third, and so on without end.

Statement. The number of strings of length exactly k over an alphabet of size 2 is 2 to the k.

Base case. For k equal to 0 there is exactly one string of length 0, the empty string, and 2 to the 0 is 1. True.

Inductive step. Assume there are 2 to the k strings of length k. A string of length k plus 1 is a string of length k with one more symbol on the end, and there are 2 choices for that symbol. Different choices give different strings, and every string of length k plus 1 arises this way exactly once. So there are 2 to the k multiplied by 2, which is 2 to the (k plus 1). True.

Therefore the statement holds for every k.

Induction on strings. Very often in this book the induction is not over numbers but over the length of a string. The base case is the empty string and the step assumes the claim for w and proves it for w with one more symbol. Chapter 11 defines the extended transition function exactly this way, and chapter 16 proves the subset construction correct exactly this way. It is the same principle: the strings of each length are built from the strings one shorter.

Five: the pigeonhole principle

If n items are put into m boxes and n is greater than m, then some box holds at least two items.

It is obvious, it needs no proof, and it is the engine of the most examined theorem in Module 1.

Why it matters here. A machine with m states, run on a string of length m or more, visits at least m plus 1 states along the way, counting the one it starts in. There are only m states to be visited. So some state is visited twice. That is the entire content of the pumping lemma, and chapter 36 does nothing but write it out carefully and see what follows.

Worked, on a machine. A machine has 3 states. Feed it the string aaaa, of length 4. The run passes through 5 states in total: where it starts, and where it is after each of the 4 symbols. Five visits, three states, so some state occurs twice. Between the two occurrences the machine has read a non empty piece of the string and come back to where it was, which means that piece can be repeated any number of times without the machine noticing. Hence "pumping".

Putting two together: proving a language is not regular

Here is the combination that earns marks in the examination, using three of the five techniques at once. The full treatment is chapter 37; this is the skeleton.

To prove that the language of strings a to the n followed by b to the n is not regular:

1. Contradiction: suppose it is regular.
2. Then some machine accepts it, with some definite number of states, call it m.
3. Pigeonhole: feed the machine a to the m followed by b to the m. While reading the a part it

passes through more states than it has, so it repeats one.

1. So a non empty block of a can be repeated without the machine noticing, giving a string with more a

than b that the machine still accepts.

1. That string is not in the language, so the machine does not accept the language after all.
2. Contradiction, so no such machine exists, so the language is not regular.

Notice that step 2 says "some definite number", not "a large number". The proof must work whatever m is, which is why the string chosen in step 3 is written in terms of m rather than as a particular string.

Distinctions

What it does NOT mean

A proof is not a worked example. Showing a machine accepts three strings proves that it accepts three strings. It does not prove the machine is correct, and an examination answer that offers examples where a proof was asked for has answered a different question.

Contraposition is not the inverse. "If not P then not Q" is not equivalent to "if P then Q". See the trap above.

A counterexample is not a proof, except of a negative. One counterexample disproves a universal claim completely. No number of confirming instances proves one.

Induction does not prove the base case by assuming it. The base case must be checked outright. An induction whose base case is skipped can prove false statements, which is why examiners mark it separately.

Quick revision

• Direct: assume the hypothesis, reason to the conclusion.
• Contraposition: prove "if not Q then not P", which is equivalent. The inverse is not.
• Contradiction: assume the negation, write out what it gives, derive an impossibility. Used for the

halting problem and every pumping lemma argument.

• Induction: base case, then assume for n and prove for n plus 1. Often over string length, with the

empty string as the base.

• Pigeonhole: more items than boxes forces a repeat. A machine with m states run on a string of length

m or more must revisit a state, and that is the pumping lemma.

• A proof is needed because a machine must be right on infinitely many inputs, and because negative

results are claims about every possible machine.

Test yourself

1. Give the contrapositive of "if L is regular then L satisfies the pumping lemma". If L does not satisfy the pumping lemma then L is not regular. This is the form in which the lemma is actually used.

2. Why must the base case of an induction be proved separately? Because the inductive step only shows that each case carries the next. Without a first case that is known outright, the chain has nothing to start from, and a step can be perfectly valid while the statement is false for every value.

3. A machine has 5 states. What does the pigeonhole principle tell you about its run on a string of length 6? The run visits 7 states counting the start, among only 5 distinct states, so at least one state is visited twice, and the portion of input read between the two visits can be repeated without changing where the machine ends up.

4. Prove by contradiction that the empty string is in every language of the form L star. Suppose some L star did not contain the empty string. L star is the set of concatenations of zero or more strings from L, and the concatenation of zero strings is the empty string by definition. So the empty string is in L star, contradicting the supposition.

5. Name the technique each of these needs: showing a construction is correct for all inputs; showing a language is not context free; showing two regular expressions denote the same language. Induction, usually on string length; contradiction with the pumping lemma for context free languages; either a direct two way containment argument or, in this book, an exact machine comparison.

6. State the pigeonhole principle and say what the boxes are when it is applied to a finite automaton. If more items than boxes are distributed among the boxes, some box holds two or more. Applied to an automaton, the boxes are the states and the items are the points in time during a run.

The set of all machines is countable

This is the step that makes the argument bite, and it is worth doing carefully.

A machine of any of the kinds in this book is a finite object: a finite set of states, a finite alphabet, and a finite table of transitions. A finite object can be written down as a string over some fixed finite alphabet. That is not a trick; it is what chapter 73 does explicitly, encoding a whole Turing machine as a single string so that another machine can read it.

Once each machine is a string, the set of machines is a subset of Sigma star for that encoding alphabet. And a subset of a countable set is countable: list the whole set and cross out what is not in the subset, and what remains is still a list.

So the machines can be listed: a first machine, a second machine, a third, with every machine somewhere in the list.

The same argument applies to programs in any programming language, since a program is a finite string of characters. There are countably many programs. Every program that has ever been written or ever will be written, in every language, is somewhere in one list.

The set of all languages is uncountable

Now the other side, and this is Cantor's diagonal argument.

A language over Sigma is any subset of Sigma star. So the set of all languages is the power set of Sigma star. Chapter 2 counted the subsets of a finite set; this is the infinite case, and the answer is different in kind.

Claim. The set of all languages over Sigma is not countable.

Proof by contradiction. Suppose it were countable. Then the languages could be listed, L1, L2, L3 and so on, with every language somewhere in the list. Also list the strings in canonical order, w1, w2, w3 and so on, which chapter 3 says we can do.

Now build a table. The row for language Li and the column for string wj holds 1 if wj is in Li and 0 if it is not. Every language is a row, because every language is in the list, and every string is a column.

Now define a new language D by walking down the diagonal and flipping every entry: put wj into D exactly when the entry for Lj and wj is 0. For the table above the diagonal reads 1, 0, 0, 1, so D contains w2 and w3 and not w1 and not w4.

D is a language over Sigma, because it is a set of strings over Sigma. So D must be somewhere in the list, say D is Lk.

Ask whether wk is in D. By the definition of D, wk is in D exactly when the table entry for Lk and wk is 0, that is, exactly when wk is not in Lk. But D is Lk, so that reads: wk is in Lk exactly when wk is not in Lk. That cannot be.

So the assumption was wrong, and the languages cannot be listed. The set of all languages is uncountable.

The conclusion, in one sentence

Countably many machines. Uncountably many languages. Each machine accepts exactly one language. So the machines cannot cover the languages, and almost every language has no machine at all.

"Almost every" is not loose here. The languages with machines form a countable subset of an uncountable set, which is as small as a subset can be while still being infinite.

What this does and does not tell you

It is a counting argument, and counting arguments have a characteristic strength and a characteristic weakness.

The strength. It settles the general question at once, and with almost no work. There is no need to examine what machines can do in order to know that they cannot do everything.

The weakness. It is not constructive. It proves that undecidable languages exist without naming one. If you ask "which language has no machine?", this argument answers "one of the uncountably many that are not in the list", which is no answer at all.

That is exactly why chapters 74 to 77 are needed. The halting problem is a named problem, with a plain English statement anyone can understand, and it is proved undecidable by the same diagonal technique applied to a particular construction rather than to a table. Naming one is much harder than counting them, and it is the naming that made Turing's paper famous.

Worked example: a small diagonal, in full

Work over the alphabet {a}, so the strings in canonical order are

Suppose somebody offers this as the beginning of a complete list of all languages over {a}:

The diagonal entries are the ones where the row number and the column number agree: 1 for L1 and ε, 1 for L2 and a, 0 for L3 and aa, 1 for L4 and aaa. Flipping gives 0, 0, 1, 0, so

and D is not L1, because they disagree on ε; not L2, because they disagree on a; not L3, because they disagree on aa; and not L4, because they disagree on aaa. Whatever the rest of the list holds, D disagrees with the k-th language on the k-th string, so it is nowhere in the list.

That is the whole argument, and the reason it works is that the diagonal is guaranteed to meet every row exactly once.

Distinctions

What it does NOT mean

It does not say the languages we care about have no machine. Almost all languages are undescribable, but the languages anybody wants to describe are, by definition, describable, so they are in the small countable part. This is not a reason to despair.

It does not name a single undecidable language. That needs chapter 74.

It does not depend on the machine model. It works for finite automata, for Turing machines, for Java programs and for anything else that can be written down finitely. That robustness is the point, and it is what connects this chapter to the Church Turing thesis in chapter 72.

A proper subset of an infinite set can be the same size. The even numbers are countable, exactly as the whole numbers are. Size for infinite sets means "there is a bijection", not "is contained in".

Quick revision

• Countable: the elements can be put in one endless list with nothing missed. Uncountable: no list

exists, and that can be proved.

• Sigma star is countable, in canonical order, first by length and then alphabetically.
• Every machine and every program is a finite object, so it can be written as a string, so there are

countably many of them.

• The set of all languages is the power set of Sigma star and is uncountable, by Cantor's diagonal

argument: from any proposed list build D disagreeing with the k-th language on the k-th string.

• Countably many machines against uncountably many languages, so almost every language has no machine.
• The argument is not constructive: it proves such languages exist and names none, which is why the

halting problem is proved separately.

Test yourself

1. Define countable, and show the set of even whole numbers is countable. A set is countable when its elements can be listed in one infinite sequence with none repeated and none omitted, equivalently when there is a bijection with the natural numbers. The evens are listed 0, 2, 4, 6 and so on; the function taking n to 2n is a bijection from the natural numbers to the evens.

2. Why are there only countably many Turing machines? Each is a finite object and can be written as a finite string over a fixed finite alphabet. The set of all finite strings over a finite alphabet is countable, and a subset of a countable set is countable.

3. Carry out one step of the diagonal argument: the list begins L1 with ε in it, L2 without a in it, L3 with aa in it. Is ε in D? Is a? Is aa? The diagonal entry for L1 and ε is 1, so ε is not in D. For L2 and a it is 0, so a is in D. For L3 and aa it is 1, so aa is not in D.

4. Why does the diagonal argument not name an undecidable language? Because the language it produces is defined in terms of the supposed list, which does not exist. The argument shows a contradiction follows from assuming the list, and a contradiction yields no object.

5. A student concludes from this chapter that most useful problems are unsolvable. Are they right? No. The conclusion is that most languages, taken from the whole uncountable collection, have no machine. A language somebody has described is describable, so it lies in the countable part, and whether it has a machine is a separate question answered by the specific results of Module 2.

6. Which two facts, put together, give the conclusion of this chapter? That there are countably many machines, because each is a finite object encodable as a string, and that there are uncountably many languages, because the power set of a countable infinite set cannot be listed.

What each part rules out

The definition is as much about what a machine cannot do as about what it can, and the restrictions are the interesting part.

It cannot count without bound. The memory is the state, and there are finitely many states. A machine can count a to three and remember the answer modulo three, as chapter 4 showed, because that needs three states. It cannot count a to an arbitrary number and compare with the b count, because that would need one state per possible count. Chapter 37 turns this observation into a proof.

It cannot go back. The input is read once, left to right, one symbol per move. There is no rewinding and no looking ahead. Everything about the part already read must have been summarised into the current state, or it is gone.

It cannot write. There is no scratch paper. The pushdown automaton of chapter 52 adds a stack and the Turing machine of chapter 62 adds a writable tape, and each addition buys exactly the extra power you would expect.

It has no clock and no cost. A move takes one move. This model says nothing about time in seconds, and questions about its speed belong to the complexity block of Module 2.

Three machines you have already used

The definition is abstract, so it is worth seeing that it describes ordinary things.

A turnstile. Two states: locked and unlocked. Two inputs: a coin and a push. From locked, a coin gives unlocked and a push gives locked. From unlocked, a push gives locked and a coin gives unlocked. Five parts, all present, and a complete description of the object.

A lift with three floors. States: which floor it is on. Inputs: the buttons. What it does next depends only on where it is and which button was pressed.

A four digit PIN pad. States: how many correct digits have been entered so far, plus one state for having got it wrong. Final state: all four correct. Notice what is NOT remembered: which digits were typed. Once a digit is known to be right, the fact that it was a 7 is not needed again, and a machine that remembered it would have more states for no gain. Deciding what need not be remembered is the whole skill of chapter 13.

The three ways an automaton is written down

All three appear throughout this book and a student must be able to convert between any two of them. Chapter 10 does the conversions properly; they are named here because the next chapter uses all three.

The quintuple, as above, with delta given by a list of equations.

The transition table, which is delta written out as a grid: one row per state, one column per symbol, the next state in the cell. The start state and the final states are marked in the margin.

The transition diagram, a drawing with a circle per state, an arrow per transition labelled with its symbol, an arrow from nowhere into the start state, and a double circle round each final state.

Worked example

Build the turnstile formally. Call the states L for locked and U for unlocked, and the alphabet {c, p} for coin and push. Let L be the initial state, and let U be the only final state, so the machine accepts exactly those input sequences that leave the turnstile unlocked.

and delta given by four equations, one for each combination:

Four equations, because there are two states and two symbols and the function must be defined on every pair. As a table:

Accepts: c, cc, pc, ppc, cpc

Rejects: ε, p, cp, pp, cpp

Read those lists back against the object: the machine ends unlocked exactly when the last symbol was a coin. The empty input is rejected because the turnstile starts locked, and every input ending in a push is rejected because a push always locks it.

And now the language, which is the point of the whole exercise. The machine accepts a string exactly when its last symbol is c, so

where R1 is the regular expression for that description:

(c + p)* c

That equality is not asserted here; the checker decides it exactly, by building both machines and comparing them over every string there is.

Distinctions

What it does NOT mean

An automaton is not a program. It has no variables, no arithmetic and no subroutines. Its entire memory is which of finitely many states it is in.

Final does not mean last. A final state is one that accepts if the input happens to run out there. The machine may pass through final states in the middle of a run and end up rejecting, and it may pass through non final states and end up accepting. Only the state at the end matters.

A machine need not stop at a final state. There is no halting here. The machine reads until the input is finished, and then the answer is read off.

An automaton does not produce output. It answers yes or no. The Mealy and Moore machines of chapter 18 are the variant that writes as it goes, and they are a different definition.

Quick revision

• An automaton is a quintuple: states Q, alphabet Sigma, transition rule delta, initial state q0, final

states F.

• Q is finite, and it is the machine's entire memory. That restriction causes every negative result in

Module 1.

• delta takes a state and a symbol and gives a state; it is the machine's program.
• Exactly one initial state; F may be empty or all of Q.
• The input is read once, left to right, one symbol per move; no rewinding, no writing, no counting

without bound.

• Three representations: quintuple, transition table, transition diagram.
• Accepting depends only on the state when the input runs out.

Test yourself

1. List the five parts of an automaton and say what each is for. A finite set of states, which is the whole memory; an input alphabet, the symbols it will see; a transition rule, which is its program; one initial state, where it starts; and a set of final states, which decide acceptance when the input ends.

2. Why must Q be finite, and what does that stop the machine doing? Because the machine's memory is which state it is in, and a machine with infinitely many states would have unbounded memory. It stops the machine from counting without bound, which is why no finite automaton can check that two counts agree.

3. A machine has 3 states and an alphabet of 2 symbols. How many equations does delta need? Six, one for each pair of state and symbol, because delta must be defined on the whole of Q times Sigma.

4. Can a machine have no final states? What language does it accept? Yes. It accepts the empty language, because acceptance requires ending in a final state and there are none.

5. A student says a machine accepted the string because it visited a final state after the second symbol. Correct them. Only the state reached when the whole input has been read decides acceptance. Visiting a final state part way through means nothing, and the string is accepted only if the final symbol leaves the machine in a final state.

6. Describe a four digit PIN pad as an automaton, and say what it deliberately does not remember. States: the number of correct digits entered so far, from zero to four, plus a failure state. Initial state: zero correct. Final state: four correct. It does not remember which digits were typed, because once a digit is known to be correct its identity is never needed again.

The input is accepted if the state at that moment is in F, and rejected otherwise. The run always stops, after exactly as many moves as the input has symbols, so a DFA always gives an answer, and always in a predictable number of steps. That is a property no later machine in this book has, and it is worth noticing now so that its loss in chapter 64 is visible.

The language of a machine

The language accepted by M, written L(M), is the set of all strings M accepts:

Three points about this definition catch students.

It is a set of strings, so it is a language in the sense of chapter 3. It is determined entirely by the machine, so a machine has exactly one language. And the same language can be accepted by many different machines, which is why chapter 20 asks which of them is smallest.

A language is called regular when some DFA accepts it. That is the definition, and the whole of Module 1 from here to chapter 40 is an investigation of which languages are regular and which are not.

Worked example: the first machine, built from the definition

The problem. Over the alphabet {0, 1}, accept exactly those strings that end in 1.

What must be remembered? Only whether the symbol just read was a 1. Nothing else about the past can matter, because whether a longer string ends in 1 depends only on its last symbol. So two states suffice: one meaning "the last symbol was not a 1, or there have been no symbols", and one meaning "the last symbol was a 1".

The five parts.

and delta by four equations:

As a table, with the start and final markings in the margin:

Every cell is filled and every cell holds one state, so delta is a total function and this is a DFA.

Accepts: 1, 01, 11, 001, 101, 0101

Rejects: ε, 0, 10, 00, 110, 1010

The empty string is rejected because the machine starts in q0, which is not final. That is the case students forget, and it is the case the checker always runs.

And the language, proved rather than described. The regular expression for "ends in 1" is:

(0 + 1)* 1

The checker decides that equality exactly: it builds a deterministic machine from each side, forms the product, and searches for any string on which the two disagree. There is none, so the machine is correct on all of the infinitely many strings, not just on the eleven listed above.

A trace, step by step

Running the machine on 0101, written as the state and then what is left to read:

q0 0101
q0 101
q1 01
q0 1
q1 ε

Five configurations for four symbols, because the run includes where it started. The last state is q1, which is final, so 0101 is accepted. The checker re-executes this trace against the table above and fails if any single step is wrong.

Distinctions

What it does NOT mean

Deterministic does not mean simple, small or fast. It means the next state is always uniquely determined. A DFA can have a thousand states.

A DFA does not stop when it reaches a final state. It reads the whole input. Only the state at the end counts.

A missing transition is not a rejection rule in a DFA. It is an incomplete definition. Complete it with a dead state.

Regular is a property of a language, not of a machine. Every DFA's language is regular. Asking whether a machine is regular is a category error; ask whether a language is.

Quick revision

• A DFA is (Q, Sigma, delta, q0, F) with delta a total function from Q times Sigma to Q.
• Determinism: exactly one next state for every state and symbol. No blanks, no double entries.
• It reads the input once, left to right, one symbol per move, and always stops after as many moves as

there are symbols.

• Accepts if the state when the input runs out is in F.
• L(M) is the set of strings M accepts. A language is regular when some DFA accepts it.
• An incomplete table is completed by a dead state, which is not final and returns to itself on every

symbol.

• The empty string is accepted exactly when q0 is in F.

Test yourself

1. State the definition of a DFA, naming all five parts and the constraint on delta. A quintuple (Q, Sigma, delta, q0, F): Q a finite set of states, Sigma a finite input alphabet, delta a total function from Q times Sigma to Q, q0 in Q the initial state, and F a subset of Q of final states. The constraint is that delta is total and single valued, so the next state is always uniquely determined.

2. When does a DFA accept the empty string? Exactly when its initial state is a final state, since no moves are made and the run ends where it began.

3. A table for a 3 state machine over {a, b} has 5 filled cells. Is it a DFA? No. It needs 6, one per state and symbol. Add a dead state and send the missing move to it.

4. Build a DFA accepting strings over {a, b} that begin with a. Three states: the start, a state meaning the first symbol was a, and a dead state. From the start, a goes to the accepting state and b to the dead state. The accepting state goes to itself on both symbols; the dead state goes to itself on both. Only the second state is final.

5. How many runs does a DFA have on a given string, and why does that matter? Exactly one, because delta gives exactly one next state at every step. It matters because acceptance is then unambiguous with no search, which is what makes a DFA the machine you implement in practice.

6. Two different DFAs accept the same language. Is that possible, and what does chapter 20 ask about it? Yes, and there are infinitely many such machines for any regular language. Chapter 20 asks which is smallest, and chapter 21 proves the smallest is unique up to the naming of its states.

The remaining columns are the input symbols, one each, and the cell holds the next state.

The first column carries the markers: start for the initial state, final for an accepting state, start final for a state that is both, and nothing at all for an ordinary state.

Reading that table off as equations gives six of them, which is the three states times the two symbols:

Accepts: ab, aab, bab, abab

Rejects: ε, a, b, ba, abb

What does D1 do? It accepts a string exactly when the string ends in ab. Reading b from q0 keeps you nowhere; reading a moves you to q1, meaning "an a has just been read"; reading b from q1 reaches q2, the accepting state, meaning "ab has just been read". And from q2, reading a starts a fresh a, while reading b takes you back to the beginning, because bb ends in neither a nor ab.

(a + b)* a b

The transition diagram

The drawing has four conventions and no more.

A circle for each state, labelled with its name.

An arrow from nowhere into the initial state, so it can be told from the others.

A double circle round each final state.

An arrow from q to r labelled a whenever delta(q, a) is r. Where two symbols lead from the same state to the same state, one arrow carries both labels separated by a comma, so an arrow labelled "a, b" means both.

A loop is an arrow from a state to itself, and it is how a machine ignores a symbol.

The three conversions

Table to equations. Read each cell: the row's state, the column's symbol, the cell's state. Count them at the end: rows times symbol columns.

Equations to table. Draw a grid with one row per state and one column per symbol, and fill each cell from the matching equation. Any cell you cannot fill means an equation is missing, and the machine is not a DFA until it is supplied or a dead state is added.

Table to diagram, and back. One circle per row. One arrow per non empty cell, from the row's state to the cell's state, labelled with the column's symbol. Mark the row labelled start with an incoming arrow from nowhere and every row labelled final with a double circle. Going back, read each arrow as a cell, and check at the end that every state has exactly one outgoing arrow for each symbol.

The properties a transition function must have

MU's label is "Transitions and Its properties", and these are the properties.

Totality. delta is defined for every state and every symbol. In a drawing: every circle has one outgoing arrow for each symbol of the alphabet. A machine failing this is incompletely specified, and chapter 5 gives the dead state remedy.

Single valuedness. delta gives one state, never two. In a drawing: no state has two arrows with the same label leaving it. A machine failing this is nondeterministic, which is chapter 14.

Closure within Q. Every value delta returns is a state of the machine. A cell naming a state not in the table is a mistake, and the checker behind this book rejects it outright.

No dependence on anything else. delta depends on the current state and the current symbol, and on nothing else: not on how the machine got there, not on how many symbols have been read, not on what comes later. This is the property that makes the machine finite state, and it is the one a beginner violates when designing: a rule like "if we have seen three a already, then go to q2" is not a transition unless "have seen three a" is itself recorded in a state.

Determinism of the whole run. Because delta is total and single valued, a string determines exactly one sequence of states. That is what chapter 11 formalises.

Worked example: all three representations of one machine

The problem. Over {0, 1}, accept strings containing an even number of 0.

What to remember. Only the parity of the count of 0 so far, which is two possibilities. Two states: even and odd.

Equations.

Table.

Accepts: ε, 1, 00, 11, 001, 0011

Rejects: 0, 01, 10, 000, 0001

Diagram, in words, because the drawing is the same information. Two circles, E and O. E is double circled and has an incoming arrow from nowhere. An arrow from E to O labelled 0, and one from O to E labelled 0. A loop on E labelled 1, and a loop on O labelled 1.

Note that the start state is also final, which is correct: the empty string contains zero 0, and zero is even.

1* (0 1* 0 1*)*

That regular expression says: any number of 1, then any number of blocks, each block being a 0, some 1, another 0, some 1. Every block contributes exactly two 0, so the total is even. The equality is decided exactly by the checker rather than argued here.

Distinctions

What it does NOT mean

A transition is not a step in a program. It has no condition beyond the current symbol and no memory beyond the current state.

A loop is not a delay. An arrow from a state to itself means the symbol is consumed and the state does not change. One symbol is still read.

Two arrows with the same label from one state is not shorthand. It is nondeterminism, and in a DFA it is an error.

An unreachable state is not an error. A machine may have states no input can reach. It is wasteful, and chapter 20 removes them, but the machine is still well defined and still a DFA.

Quick revision

• delta maps Q times Sigma to Q. The number of equations is states times symbols, and a short count

means a case was left out.

• Three representations: equations, table, diagram, and a student must convert between any two.
• This book's table: the corner names the machine, the left column carries start and final, an empty

divider column draws the double rule, and the remaining columns are the symbols.

• Diagram: circle per state, arrow from nowhere into the start, double circle for final, labelled

arrow per transition, loop for a symbol that changes nothing.

• The properties: total, single valued, values inside Q, dependent on nothing but the current state and

symbol, and hence determining exactly one run per string.

• A missing cell means not a DFA; two entries in a cell means nondeterministic.

Test yourself

1. A DFA has 4 states over {a, b, c}. How many cells does its table have, and how many equations does delta need? Twelve of each: four states times three symbols. A table with eleven filled cells is not a DFA.

2. What does a loop labelled b on state q mean? That delta(q, b) is q: the symbol b is read and consumed, and the machine stays in q.

3. Which property fails if a state has two arrows labelled a leaving it? Which fails if it has none? Single valuedness fails in the first case, making the machine nondeterministic. Totality fails in the second, making the machine incompletely specified.

4. Convert these equations into a table: delta(p, 0) = p, delta(p, 1) = q, delta(q, 0) = q, delta(q, 1) = p, with p initial and q final. Two rows. The row for p is marked start and holds p under 0 and q under 1. The row for q is marked final and holds q under 0 and p under 1.

5. Why is a table preferred to a diagram for checking a machine? Because an omission shows up as a blank cell, whereas a diagram with a missing arrow looks complete, and because a table can be read and executed by a program while a drawing cannot.

6. Explain why "go to q2 if three a have been seen" is not a legal transition. Because a transition may depend only on the current state and the current symbol. The number of a seen so far is history, and it can only influence the machine if it has already been recorded by being in a particular state.

So you may compute delta hat either way and get the same answer. Proofs use the first form; runs use the second.

Worked example

Take D3, which accepts strings over {a, b} in which every a is immediately followed by a b.

Accepts: ε, b, ab, bab, abab, bb

Rejects: a, aa, aab, aba, baa

State q2 is the dead state: once two a have been seen in a row, no continuation can repair the string, so the machine sits in q2 for ever and q2 is not final. State q1 means "an a has just been read and is still waiting for its b".

Now compute delta hat(q0, abb) by the definition, peeling from the right.

Six lines, and the innermost one is the base case. The answer q0 is final, so abb is accepted, which matches the list above.

The same computation peeling from the left is shorter to write and is what a run looks like:

q0 abb
q1 bb
q0 b
q0 ε

The checker re-executes that trace against the table and fails if any single step disagrees.

Why the definition is worth the trouble

Three later results are statements about delta hat, and none of them could be stated without it.

Acceptance. Chapter 12 defines L(M) as the set of w with delta hat(q0, w) in F. Without delta hat there is no way to say it.

Correctness proofs. To prove a machine accepts what you claim, you prove a statement of the form "delta hat(q0, w) is q1 exactly when w has such and such a property", and you prove it by induction on the length of w. The base case is the empty string and the step adds one symbol, which is exactly the shape of the definition above. Chapter 12 works one of these in full.

The subset construction. Chapter 16's whole proof is one identity between the extended transition function of the nondeterministic machine and that of the deterministic one it builds.

The one property that makes the machine finite state

There is a single fact about delta hat that all of Module 1's negative results rest on, and it is easiest to state here.

In words: to read x then y, read x, and then read y from wherever that left you. Nothing else about x survives. The state after x is the complete summary of x as far as the rest of the run is concerned.

That is why a machine "cannot count": if two different strings x and z lead to the same state, then every continuation treats them identically, so if xy is accepted then zy must be accepted too. Chapter 21 turns this into the Myhill Nerode theorem, and chapter 36 turns it into the pumping lemma. Both are this one identity with the pigeonhole principle applied.

Distinctions

What it does NOT mean

delta hat is not a new machine. It is a function computed from delta, and it adds no power. Two machines with the same delta have the same delta hat.

delta hat(q, epsilon) is not undefined. It is q. Forgetting this is what makes students get the empty string wrong.

The right hand peeling is not the order of a run. It is the order that makes the induction work. The two orders agree, and the identity above says so.

Many books write delta for both. Most textbooks drop the hat once the definition has been given and rely on the reader to see from the argument which is meant. This book keeps them apart wherever a proof depends on it.

Quick revision

• delta takes one symbol; delta hat takes a string, and maps Q times Sigma star to Q.
• delta hat(q, epsilon) = q, and delta hat(q, wa) = delta(delta hat(q, w), a). Base case plus one

symbol, which is induction on length.

• Peeling from the right is for proofs; peeling from the left is a run; the two agree.
• Acceptance, correctness proofs and the subset construction are all statements about delta hat.
• The key identity is delta hat(q, xy) = delta hat(delta hat(q, x), y): the state after x is the whole

of what the machine remembers about x.

• That identity is the source of both the Myhill Nerode theorem and the pumping lemma.

Test yourself

1. Write the two lines that define delta hat. delta hat(q, epsilon) = q, and delta hat(q, wa) = delta(delta hat(q, w), a) for any string w and symbol a.

2. Why can delta not be applied to a string directly? Because delta is declared as a function on Q times Sigma, so its second argument must be a single symbol. A string of length 2 is not in its domain.

3. For D3 above, compute delta hat(q0, ba) and say whether ba is accepted. delta hat(q0, b) is q0; then delta(q0, a) is q1. So delta hat(q0, ba) is q1, which is not final, so ba is rejected. That is right: the a at the end has no b after it.

4. State the identity that says the state after a prefix summarises that prefix, and say what it implies. delta hat(q, xy) = delta hat(delta hat(q, x), y). It implies that if two strings lead to the same state, then no continuation can distinguish them, which is the source of the pumping lemma and the Myhill Nerode theorem.

5. In a correctness proof by induction on string length, what is the base case? The empty string, where delta hat(q0, epsilon) is q0, so the claim must be checked for the start state and the empty string outright.

6. Does introducing delta hat make the machine more powerful? No. It is defined entirely from delta and the table, and it introduces no new behaviour; it only lets the behaviour already there be spoken about.

Now the three strings, each written as a run.

q0 1001
q0 001
q1 01
q1 1
q2 ε

Ends in q2, which is final, so 1001 is accepted.

q0 010
q1 10
q2 0
q1 ε

Ends in q1, which is not final, so 010 is rejected.

q0 11
q0 1
q0 ε

Ends in q0, which is not final, so 11 is rejected. Note that in the first run the machine passed through the final state q2 and then left it and came back; and in the second it passed through q2 in the middle and ended elsewhere. Only the last state counts.

Every one of those three runs is re-executed by the checker against the table, step by step, so a wrong step in any of them would stop this book being built.

The language accepted, written down

(0 + 1)* 0 1

and the checker decides that equality exactly, over every string there is, by comparing the two machines rather than by testing examples.

Proving a machine correct, by induction

This is the part the papers do not ask for and the part that makes the difference between a student who can check a machine and one who can trust a machine they built.

Claim. For E1, and for every string w over {0, 1}:

1. delta hat(q0, w) is q2 exactly when w ends in 01;
2. delta hat(q0, w) is q1 exactly when w ends in 0;
3. delta hat(q0, w) is q0 otherwise, that is, when w is empty or ends in 1 but not 01.

Proof, by induction on the length of w.

Base case. w is the empty string. delta hat(q0, epsilon) is q0 by the first line of chapter 11's definition. The empty string does not end in 01 and does not end in 0, so case 3 applies and says the state should be q0. It is.

Inductive step. Assume the claim holds for w, and consider w followed by one symbol a. There are six combinations of the state after w and the symbol a, and the table gives each one.

Take the fourth row as the one that carries the argument. The state after w is q1, so by the inductive hypothesis w ends in 0. Then a is 1, so wa ends in 01, and the claim says the new state should be q2. The table says delta(q1, 1) is q2. They agree.

The second row needs one extra word. The state after w is q0, so by hypothesis w is empty or ends in 1 without ending in 01. Adding a 1 gives a string ending in 1, and its last two symbols are either just the single 1, or 11, neither of which is 01. So case 3 applies and the state should be q0, which is what the table gives.

All six rows agree, so the claim holds for wa. By induction it holds for every string.

Therefore delta hat(q0, w) is in F, that is, is q2, exactly when w ends in 01. So L(E1) is the set of strings ending in 01, which is what was asked for.

That is what a correctness proof looks like, and its length is six table rows and two paragraphs. A student who can write this can be sure of a machine they designed; a student who can only test it cannot.

Acceptance by the empty string, and the two smallest languages

Two machines worth having in mind, because chapter 39 uses both and because they are the boundary cases of every construction.

A machine accepting nothing at all. One state, marked start and not final, with a loop on every symbol. It accepts the empty language { }.

A machine accepting only the empty string. Two states: the start state, which is final, and a dead state which is not. Every symbol from the start state goes to the dead state, and the dead state loops to itself.

Accepts: ε

Rejects: a, b, aa, ab, ba, bb, aba

That machine accepts {epsilon}, the language with one string in it. The machine that accepts { } is the same table with the final marking removed, and the two differ on exactly one input, which is the distinction chapter 3 warned about.

Distinctions

What it does NOT mean

A machine does not stop when it accepts. There is no halting in a DFA. It reads to the end of the input and the answer is read off the last state.

Visiting a final state proves nothing about the whole string. In the 1001 run above the machine was in q2 only at the end; in the 010 run it was in q2 in the middle and rejected. Both are normal.

A table of accepted strings is not a proof of correctness. It proves the machine handles those strings. The infinitely many others need an argument.

Regular is a property of the language. A language is regular when some DFA accepts it. Every DFA's language is regular by definition, so "is this machine regular" is not a question.

Quick revision

• M accepts w when delta hat(q0, w) is in F: the state after reading the whole string, from the start

state, must be final.

• L(M), also written T(M), is the set of all strings M accepts. A language is regular when some DFA

accepts it.

• To find acceptability: start at q0, follow one cell per symbol, and look at the last state.
• Only the last state matters. Passing through a final state on the way means nothing.
• Correctness is proved by induction on string length: state what each state means, check the empty

string, then check every combination of state and symbol against the table.

• The empty string is accepted exactly when q0 is final. { } and {epsilon} are accepted by machines

differing only in that marking.

Test yourself

1. State the condition for M to accept w, using the right function. delta hat(q0, w) is in F. delta alone will not do, because w is a string.

2. E1 above: is 0101 accepted? Trace it. q0 on 0 gives q1; q1 on 1 gives q2; q2 on 0 gives q1; q1 on 1 gives q2. The last state is q2, which is final, so 0101 is accepted, and indeed it ends in 01.

3. A machine passes through a final state after two of five symbols and ends in a non final state. Is the string accepted? No. Acceptance depends only on the state after the whole string has been read.

4. Describe the machine accepting the empty language, and the one accepting only the empty string. For the empty language: one state, start, not final, looping on every symbol. For {epsilon}: the same machine with the start state marked final, plus a non final dead state that every symbol from the start state leads to and that loops to itself.

5. Why is a proof by induction needed when the machine has been tested on twenty strings? Because the language is infinite and twenty strings say nothing about the rest. The induction covers every string by proving what each state means for every prefix.

6. In a correctness proof, how many combinations must the inductive step check? One for each state and each symbol, so the number of states multiplied by the size of the alphabet, which is exactly the number of cells in the transition table.

The three patterns that cover most exercises

Before the machines, three observations that turn most questions into one of three shapes.

Counting modulo something needs that many states. "An even number of a", "a length divisible by 3", "a number of 1 that leaves remainder 2 on division by 4" all need one state per remainder, and no more. The reason is that the remainder is all you need: adding one symbol changes the remainder in a way that depends only on the old remainder.

Remembering the last few symbols needs one state per possibility. "Ends in ab", "contains aba", "does not contain bb" need a state for each relevant recent history, and the trick is to keep the history as short as possible: for "ends in ab" the states are nothing useful, just seen a, just seen ab.

An irreparable condition needs a dead state. "Every a is followed by a b" can be broken by a prefix, and once broken nothing repairs it. That needs one non final state that loops to itself on everything.

Machine 1: strings over {a, b} ending in ab

MU's own question. What must be remembered: how much of the pattern ab is currently complete at the right hand end. Three conditions, so three states.

s0 means the string so far ends in neither a nor ab. s1 means it ends in a. s2 means it ends in ab.

The two cells students get wrong are in the bottom row. From s2, reading a takes you to s1, not to s0, because that a is itself the beginning of a possible new ab. And from s1, reading a keeps you in s1, because aa still ends in a.

Accepts: ab, aab, bab, abab, bbab

Rejects: ε, a, b, ba, aba, abb

(a + b)* a b

Machine 2: strings over {a, b} containing aba

What must be remembered: how much of aba is complete at the right hand end, and once the whole pattern has been seen, that it has been seen, which is permanent.

p0: no useful suffix. p1: ends in a. p2: ends in ab. p3: aba has been seen somewhere, and nothing can undo that, so p3 loops to itself on both symbols.

The subtle cell is p2 on b: abb ends in neither a nor ab, so it goes back to p0. And p2 on a completes aba and reaches p3.

Accepts: aba, aabab, babaa, ababa, bbabab

Rejects: ε, ab, abb, aab, bbb, babb

(a + b)* a b a (a + b)*

Machine 3: an even number of a and an even number of b

What must be remembered: the parity of each count. Two independent facts each with two values, so four states, and the state set is the Cartesian product of chapter 2.

The name records the two parities: ee means both even, oe means the a count is odd and the b count even, and so on. Reading an a flips the first letter; reading a b flips the second. The start state is final because zero is even.

Accepts: ε, aa, bb, abab, aabb, baab

Rejects: a, b, ab, ba, aab, abb

(a a + b b + (a b + b a)(a a + b b)*(a b + b a))*

Machine 4: strings over {0, 1} whose value as a binary number is divisible by 3

What must be remembered: the remainder of the number read so far on division by 3, which is three conditions. This is the machine worth understanding, because it shows that "remember a remainder" is enough for a task that looks arithmetical.

Appending a bit b to a binary number n gives 2n plus b. So if n leaves remainder r, then 2n plus b leaves the remainder of 2r plus b. That rule fills the table with no thought at all.

From r0 reading 0 gives remainder 0, and reading 1 gives 1. From r1 reading 0 gives 2 times 1 plus 0 which is 2, and reading 1 gives 3, whose remainder is 0. From r2 reading 0 gives 4, whose remainder is 1, and reading 1 gives 5, whose remainder is 2.

Accepts: ε, 0, 11, 110, 1001, 1100

Rejects: 1, 10, 100, 101, 111

110 is 6, which is divisible by 3. 1001 is 9. 1100 is 12. And 111 is 7, which is not. The empty string is accepted because the machine starts in r0; a book may prefer to exclude it, and doing so needs one extra state, which is left to the exercises.

Machine 5: strings over {a, b} in which every a is immediately followed by a b

What must be remembered: whether an a is currently waiting for its b, and whether the condition has already been broken beyond repair. Three states, the third of them dead.

t0: nothing outstanding, and the string so far is legal. t1: an a has just been read and needs a b next. t2: dead, because either two a came in a row or the string ended just after an a.

Note that t1 is not final. That is the whole content of "immediately followed": a string ending in a is not in the language, because the a never got its b.

Accepts: ε, b, ab, bb, abb, abab

Rejects: a, aa, ba, aab, aba

(b + a b)*

Machine 6: strings over {a, b} of length exactly 3

What must be remembered: how many symbols have been read, up to 4, where 4 means "too many". Five states, and this is the shape every "exactly n" question takes.

Each state counts, and n4 is the dead state for anything longer. Both symbols behave identically, because only the length matters.

Accepts: aaa, aab, abb, bbb, bab

Rejects: ε, a, ab, aaaa, bbbb

(a + b)(a + b)(a + b)

Machine 7: strings over {a, b} whose third symbol from the left is a

What must be remembered: how many symbols have been read while it still matters, and then the answer for ever. Five states.

The first two symbols are read and ignored. The third decides: a reaches y, which is final and absorbing, and b reaches z, which is not final and absorbing. Strings shorter than 3 have no third symbol and are rejected, which is why m0, m1 and m2 are not final.

Accepts: aaa, bba, aba, bbab, abaaa

Rejects: ε, a, ab, aab, bbb, abb

(a + b)(a + b) a (a + b)*

Machine 8: strings over {a, b} that do not contain bb

What must be remembered: whether the previous symbol was a b, and whether bb has already occurred, which is fatal. Three states.

u0: legal so far and the last symbol was not b. u1: legal so far and the last symbol was b. u2: dead. Both u0 and u1 are final, because a legal string may end in b as long as it does not end in bb.

Accepts: ε, a, b, ab, ba, aba, abab

Rejects: bb, abb, bba, abba, babb

(a + b a)* (b + ε)

What every one of those eight has in common

The state set is a list of conditions, and the names say which. No machine above has a state whose meaning could not be written in a short phrase, and that is not a coincidence: a state with no meaning is a state you do not need or a design that has not been thought through.

Every cell is filled. Count them: three states times two symbols is six cells in machine 1, four times two is eight in machine 3, five times two is ten in machines 6 and 7.

The empty string is decided on purpose. In machines 3, 4, 5, 6 and 8 the answer for the empty string was a deliberate decision about whether the start state is final, and in each case it followed from the description rather than from habit.

Each one was checked, not trusted. The accepted and rejected strings under each machine are run, and each machine is compared with a regular expression for the same language over every string there is. That is the difference between a machine that looks right and one that is right.

Distinctions

What it does NOT mean

More states is not safer. A machine with spare states is harder to check and chapter 20 will remove them anyway. The discipline of asking "what is the least I must remember" is what produces a correct machine, not a generous state count.

A dead state is not optional in a DFA. If your drawing has a missing arrow, the table has a blank cell, and the machine is not a DFA until the dead state is added.

The start state being final is not a special case. It is the ordinary question of whether the empty string is in the language, answered like any other.

Testing is not designing. The eight machines above were designed from the meanings of their states and then tested. Designing by testing produces a machine that passes the tests you thought of.

Quick revision

• Five steps: decide what must be remembered; one state per condition, with its meaning written down;

fill every cell; mark the final states, checking the empty string on purpose; test the boundaries and then prove it.

• Cells equals states times symbols. A short count means a case was missed.
• Counting modulo k needs k states. A pattern of length n at the end needs n plus 1. A condition that

can be broken permanently needs a dead state.

• Two independent conditions need the product of their state counts, and the state names should record

both.

• A state whose meaning cannot be stated in a phrase is a sign the design is not finished.

Test yourself

1. Design a DFA over {a, b} accepting strings that begin with a and end with b. Four states: the start; a state meaning the first symbol was a and the last was not b; a final state meaning the first was a and the last was b; and a dead state for a string beginning with b. From the start, a goes to the second state and b to the dead state. In the second state, a stays and b goes to the final state. In the final state, a returns to the second and b stays.

2. How many states does a DFA need to accept strings over {0, 1} whose length is divisible by 4? Four, one per remainder, arranged in a cycle, with the remainder zero state both start and final.

3. In machine 1, why does s2 on a go to s1 rather than s0? Because the a just read may be the a of a later ab, so the machine must record that the string now ends in a. Going to s0 would lose that and would reject aba b, which ends in ab.

4. Why are both u0 and u1 final in machine 8? Because a string with no bb may end in a or in a single b. Only two consecutive b are fatal, so ending in one b is legal.

5. A student's machine for "contains aba" sends the state meaning "ends in ab" back to the start on reading b. Is that right? Yes. After ab, reading b gives a string ending in abb, which has no useful suffix towards aba, so the machine must return to the state meaning no progress.

6. What is the first question to ask when designing any DFA? What is the least I need to know about the prefix read so far in order to deal correctly with anything that might come next.

The extended transition function for an NFA

The two line definition of chapter 11 needs one change, because the answer is now a set.

In words: to read one more symbol, take the set of states you might be in, and collect together everything reachable from any of them on that symbol.

And acceptance:

If the set ever becomes empty it stays empty, because the union over no states is empty. So a machine whose every run has died rejects everything after that point, which is correct.

Why nondeterminism is worth having

Two reasons, and the second is the one that matters in this paper.

It is easier to design with. Some languages have an obvious nondeterministic machine and an awkward deterministic one. "Contains aba" is the standard example: nondeterministically the machine loops at the start doing nothing, then when it feels like it reads aba and loops at the end. Deterministically it has to track how much of aba is currently complete, which is what machine 2 of chapter 13 does, and that takes real thought.

It is what the constructions produce. Chapter 34 turns a regular expression into a machine, and the machine it produces is nondeterministic, with empty moves, because that is the only way to glue two machines together without knowing anything about them. If nondeterminism were not allowed, that construction would not exist. The same is true of the constructions in chapters 33 and 38.

Machine 1: contains aba, nondeterministically

Three states, and compare it with the four state deterministic machine of chapter 13.

Read it as a description rather than as a program. In n0 the machine either stays where it is, ignoring the symbol, or begins the pattern. In n1 it needs a b. In n2 it needs an a, which finishes the pattern and reaches n3, from which nothing can go wrong.

The cell for n0 on a holds two states, which is what makes this an NFA. The cells for n1 on a and n2 on b hold a dash, meaning no move: a run that is looking for a b and gets an a is simply over.

Accepts: aba, aabab, babaa, ababa, bbabab

Rejects: ε, ab, abb, aab, bbb, babb

(a + b)* a b a (a + b)*

And it accepts the same language as the deterministic machine of chapter 13, which is what chapter 16 will prove must always be possible.

Machine 2: the exponential case

Here is the family that shows the subset construction of chapter 16 really can be as expensive as its bound.

Consider the language of strings over {a, b} whose fourth symbol from the right hand end is an a. Nondeterministically this is easy: loop at the start, then read an a, then read three more symbols of any kind, and stop.

Five states, and k4 has no moves at all, which is correct: if anything follows, that run dies, because then the a was not the fourth from the end.

Accepts: abbb, aaaa, babbb, babab, aabbb

Rejects: ε, a, ab, abb, bbbb, bbbba

(a + b)* a (a + b)(a + b)(a + b)

A deterministic machine for this language has to remember the last four symbols, because until the input ends it cannot know which symbol will turn out to be fourth from the end. Four symbols with two possibilities each is sixteen conditions, so the minimal DFA has sixteen states. The NFA has five, and the general pattern is n plus 1 against 2 to the n. Chapter 16's exponential bound is therefore not pessimism: it is achieved.

Machine 3: an incomplete machine is an NFA

This is worth stating, because students meet it without noticing.

Every cell holds at most one state, so nothing is being chosen anywhere, and yet this is not a DFA, because two cells are empty and a DFA's delta must be total. It is an NFA in which every set has size zero or one.

Such a machine is sometimes called incompletely specified, and turning it into a DFA needs no subset construction at all: just add the dead state of chapter 5.

Accepts: a, ab, abb, abbb

Rejects: ε, b, ba, aa, aab

a b*

Worked example: running an NFA by hand

Take N1 and the string abab. Keep track of the set of states, which is the only way to do this without backtracking.

The final set contains n3, which is final, so abab is accepted. And it should be: abab contains aba as its first three symbols.

That table is the whole technique, and it is worth noticing what has just happened. The sets of states in the left hand column behave exactly like the states of a deterministic machine: each row is determined by the row above and the symbol read. That observation, and nothing more, is the subset construction of chapter 16.

Distinctions

What it does NOT mean

An NFA is not more powerful than a DFA. Chapter 16 proves they accept exactly the same class of languages. Nondeterminism buys convenience and smaller machines, never new languages. This is the result students find hardest to believe, and it is worth holding on to, because the corresponding statement is FALSE for pushdown automata in chapter 57, and false as far as anybody knows for the linear bounded automaton in chapter 61.

A dash in a cell is not a rejection. It kills one run. Other runs continue, and the string is still accepted if one of them succeeds.

An NFA does not backtrack. Backtracking is one way to implement a search for an accepting run. The definition mentions nothing of the kind, and the set of states method above never backtracks.

Nondeterminism is not probability. There are no likelihoods anywhere. A run either exists or does not.

Quick revision

• An NFA is (Q, Sigma, delta, q0, F) with delta mapping Q times Sigma to the power set of Q, so a cell

may hold several states or none.

• Accepts w when delta hat(q0, w) contains at least one final state: some run succeeds.
• delta hat(q, epsilon) is {q}, and one more symbol takes the union of the moves from every state in the

current set.

• Nondeterminism is a definition of acceptance, not guessing, not parallelism, not probability. The

working picture is that the machine is in a set of states at once.

• It is easier to design with, and the constructions of chapters 33, 34 and 38 produce it.
• An incompletely specified machine is an NFA whose sets all have size at most one; add a dead state to

make it a DFA.

• NFA and DFA accept exactly the same languages, but an NFA can be exponentially smaller, and the

fourth from the right example achieves the bound.

Test yourself

1. Give the one difference between the definitions of a DFA and an NFA. The codomain of delta. For a DFA it is Q, so there is exactly one next state. For an NFA it is the power set of Q, so there may be several or none.

2. What does an empty cell mean in an NFA, and what does it mean in a DFA? In an NFA it means that run has no continuation and dies, while other runs are unaffected. In a DFA it means the definition is incomplete, and the machine is not a DFA until a dead state is added.

3. Run N1 on the string bab and say whether it is accepted. Start {n0}. On b: {n0}. On a: {n0, n1}. On b: {n0, n2}. The final set has no final state in it, so bab is rejected, which is right because bab does not contain aba.

4. Why is nondeterminism not the same as guessing? Because nothing in the machine makes any choice. Acceptance is defined as the existence of a successful run among all the runs the transition relation permits, which is a property of a graph and needs no agent.

5. Name a language whose NFA is much smaller than its smallest DFA, and give both sizes. Strings over {a, b} whose fourth symbol from the right is an a. The NFA has 5 states; the minimal DFA has 16, because it must remember the last four symbols.

6. If an NFA's cells all hold exactly one state, what is it? A DFA, written with sets of size one. Determinism is the special case where every set is a singleton and none is empty.

The closure of a set of states is the union of the closures of its members.

Computing it: the algorithm

This is asked as a procedure, so it is worth setting out as one.

1. Start with the answer containing q alone.
2. Pick any state p in the answer whose epsilon moves have not yet been followed.
3. Add every state in the epsilon cell of p to the answer.
4. Repeat from step 2 until nothing new is added.

It terminates because there are finitely many states and the answer only grows.

Worked example

Take P1, a machine with three empty moves.

Now the closures, one state at a time, each by the algorithm.

The closure of p is the one that needs the algorithm rather than one glance: t is two empty moves away, through r, and a student who only looks at the epsilon cell of p gets three states instead of four.

Every one of those five sets contains its own state, which is the check to run before writing anything down.

What the closure is for

Two uses, both immediate.

Running the machine. The set of states the machine could be in after reading a prefix must be closed under empty moves, because an empty move can always be taken. So a run keeps the closure at every step:

1. Begin in the closure of the start state, not in the start state alone.
2. To read a symbol a, take the current set, follow every a arrow, then take the closure of the result.
3. Accept if the final set contains a final state.

Step 1 is the step that is forgotten, and it matters whenever the start state can reach a final state by empty moves, which is exactly the case where the machine accepts the empty string.

Removing the moves and building a DFA. Chapters 16 and 17 both use the closure, and in both it appears at exactly the two points named above: the start set, and after each symbol.

Worked example: running P1

Run P1 on the input a, keeping closures throughout.

Start: the closure of p, which is {p, q, r, t}. Note that this set already contains t, which is final, so P1 accepts the empty string without reading anything.

Read a. Follow a arrows from each of p, q, r, t: p on a gives p, q on a gives s, r and t have none. That gives {p, s}. Now take the closure: the closure of p is {p, q, r, t} and the closure of s is {s}, so the set is {p,q,r,s,t}.

That contains t, so a is accepted.

Accepts: ε, a, aa, b, bb, ab

Rejects: ba, abba, bab

The claim lists are executed by the checker, which computes closures exactly as above. And to see what P1's language actually is:

a* (b* + a b*)

which is the reading the drawing gives: any number of a at the start, and then either sit in r reading b, or take one a into s and read b there.

The two smallest empty move machines, and why they matter

These are the building blocks of chapter 34, so they are worth meeting on their own.

A machine for the empty string, with one empty move and no symbols read:

Accepts: ε

Rejects: a, aa

A machine for the union of two things, where the start state has an empty move into each of two sub machines. Here the two sub machines accept a and b respectively:

Accepts: a, b

Rejects: ε, ab, ba, aa

a + b

Notice what the empty moves have bought: the two sub machines were not touched at all. Their tables are unchanged and a new start state was added with two empty arrows. That is the whole technique of chapter 34, and it only works because an arrow can consume nothing.

Distinctions

What it does NOT mean

Epsilon is not a symbol of the alphabet. It labels an arrow. No input string ever contains it, and writing it into Sigma is an error that breaks the definition.

The closure is not just the epsilon cell. It is the transitive closure: follow empty arrows as far as they go. Two steps, three steps, any number.

The closure of q is never empty. It always contains q. A closure computed as the empty set is an arithmetic mistake.

An empty move is not a free pass. It does not skip a symbol of the input; it moves between states without reading. The input still has to be read in full by symbol moves.

Empty moves add no power. They make constructions possible and machines smaller to write. Chapter 17 removes them all.

Quick revision

• An epsilon-NFA lets delta take epsilon as well as the symbols of Sigma, so a state may change without

reading input.

• Epsilon is not in Sigma and never appears in an input string.
• The epsilon closure of q is every state reachable by zero or more empty moves, and it always contains

q itself.

• Algorithm: start with q, repeatedly add the epsilon cell of anything in the answer, stop when nothing

new appears.

• Running the machine: begin at the closure of the start state, and after each symbol take the closure

of the result.

• The machine accepts the empty string exactly when the closure of the start state contains a final

state.

• Empty moves exist because the constructions of chapters 33, 34 and 38 need to glue machines together

without looking inside them. They add no power.

Test yourself

1. Define the epsilon closure of a state. The set of all states reachable from it by a sequence of zero or more epsilon transitions. Because zero is allowed, the state itself is always a member.

2. A machine has an epsilon arrow from p to q and from q to r, and none other. Give the closures of p, q and r. Closure of p is {p, q, r}; closure of q is {q, r}; closure of r is {r}.

3. When does an epsilon-NFA accept the empty string? Exactly when the epsilon closure of its start state contains a final state, since no symbols are read.

4. What are the two places a closure is taken when running such a machine? At the start, to get the initial set, and after following the arrows for each input symbol.

5. Why are empty moves useful if they add no power? Because they allow two machines to be joined without examining their tables, which is what makes the construction from a regular expression to an automaton short and uniform.

6. A student computes the closure of a state as the empty set. What has gone wrong? They have forgotten that zero steps count, so the state itself is always in its own closure. No closure is ever empty.

Final states. Every subset S that contains at least one member of F. Not the subsets contained in F: at least one member, because an NFA accepts when some run succeeds.

That last point is the commonest error in the construction, and it is worth a sentence of its own. A subset like {q1, q3} where only q3 is final IS a final state of M', because the run that ended in q3 is a successful run.

Building only what is needed

The construction as stated builds 2 to the n states, and almost all of them are usually unreachable. The practical version, and the one the examination expects, builds outward from the start.

1. Write down the start set {q0} as the first row.
2. Take any row not yet expanded, and for each symbol compute the new set.
3. Any set that has not appeared before becomes a new row.
4. Stop when every row has been expanded.
5. Mark as final every row whose set contains a final state of M.

This is a reachability search, and it terminates because there are finitely many subsets. It usually produces far fewer than 2 to the n rows, and for the family in chapter 14 it produces exactly 2 to the n, which is why the bound cannot be improved.

With empty moves

If M has empty moves, the construction changes in exactly the two places chapter 15 identified.

The start state is the epsilon closure of {q0}, not {q0}.

The transition is the epsilon closure of the union, not the union.

Everything else is unchanged. A machine with no empty moves has closures equal to the states themselves, so the two versions agree, and it is safe to learn only the second.

Worked example 1: the aba machine

Convert N1 from chapter 14. Its table again, so this chapter stands alone:

Accepts: aba, ababa

Rejects: ε, ab, bb

Now build outward. The start set is {n0}.

Six sets appeared, out of the sixteen subsets of a four state machine. Working through row three as the one that shows the method: from {n0, n2} on a, n0 gives {n0, n1} and n2 gives {n3}, so the union is {n0, n1, n3}; and on b, n0 gives {n0} and n2 gives nothing, so the union is {n0}.

The final states are the three sets containing n3: {n0, n1, n3}, {n0, n2, n3} and {n0, n3}.

Relabel the six sets A to F in the order above and the DFA is:

Accepts: aba, aabab, babaa, ababa, bbabab

Rejects: ε, ab, abb, aab, bbb, babb

The equality is decided exactly, over every string there is, by comparing the two machines. So the construction has not merely been carried out; the result has been proved right.

Six states, and chapter 13's hand designed machine for the same language had four. The subset construction is not obliged to give the smallest machine, and chapter 20 is how to shrink it.

Worked example 2: with empty moves

Convert P1 from chapter 15, which has three empty moves.

Accepts: ε, a, b

Rejects: ba, bab

The closures were computed in chapter 15: the closure of p is {p, q, r, t}, of r is {r, t}, and each of q, s, t is its own closure.

Start state: the closure of {p}, which is {p, q, r, t}. Call it S1.

S1 on a. The a moves: p gives p, q gives s, and r, t give nothing. Union {p, s}. Closure: {p, q, r, t} union {s}, which is {p,q,r,s,t}. Call it S2.

S1 on b. The b moves: r gives r, and the others give nothing. Union {r}. Closure {r, t}. Call it S3.

S2 on a. The a moves from p, q, r, s, t: p gives p, q gives s. Union {p, s}, closure S2 again.

S2 on b. r gives r, s gives s. Union {r, s}, closure {r, s, t}. Call it S4.

S3 on a. Neither r nor t has an a move, so the union is empty, and the closure of the empty set is empty. That is the dead state, which must be included to make the machine total.

S3 on b. r gives r. Closure {r, t}, which is S3.

S4 on a. No a moves from r, s, t, so dead.

S4 on b. r gives r and s gives s. Union {r, s}, closure S4.

The final sets are those containing t: S1, S2, S3 and S4, all four of them. So:

Accepts: ε, a, aa, b, bb, ab

Rejects: ba, abba, bab

Two things to notice. The empty set turned up as a state and had to be kept, because a DFA needs a total transition function; it is the dead state under another name. And S1 is both start and final, so the machine accepts the empty string, which is right because the closure of p contains the final state t.

The proof

MU asks for the equivalence to be proved, so here it is in full. It is an induction on the length of the string, of exactly the shape chapter 6 described, and the whole content is one identity.

Claim. For every string w over Sigma,

that is, the single state M' reaches on w is precisely the set of states M could reach on w.

Base case. w is the empty string. The left side is delta hat prime({q0}, epsilon), which is {q0} by chapter 11's definition applied to M'. The right side is delta hat(q0, epsilon), which is {q0} by chapter 14's definition applied to M. They agree.

Inductive step. Assume the identity for w, and take one more symbol a. Then

The first line is the definition of the extended function for M'. The second uses the inductive hypothesis. The third is the definition of delta prime, which is what the construction set it to be. The fourth is the definition of the extended function for M. So the identity holds for wa, and by induction for every string.

Finishing. M' accepts w exactly when delta hat prime({q0}, w) is a final state of M', which by the construction means exactly when that set contains a member of F. By the claim that set is delta hat(q0, w), so M' accepts w exactly when delta hat(q0, w) contains a member of F, which is exactly when M accepts w. Hence L(M') equals L(M).

And the converse direction needs no work at all. Every DFA is an NFA in which every cell holds a set of size one, so a language accepted by a DFA is accepted by an NFA trivially. The two inclusions together give the theorem.

The cost

M with n states gives M' with at most 2 to the n, and chapter 14's family shows the bound is reached: the language whose k-th symbol from the right is an a has an NFA with k plus 1 states and a minimal DFA with 2 to the k.

That is why the conversion is done once, when a pattern is compiled, and not on every input.

Distinctions

What it does NOT mean

The construction does not give the smallest DFA. Example 1 gave six states where four suffice. Chapter 20 minimises.

A final state of M' is not a subset of F. It is a subset meeting F. Requiring containment would give a machine accepting a different, smaller language.

The empty set is a legitimate state. It is the dead state, and leaving it out makes the transition function partial and the machine not a DFA.

Equivalence of the two models is not a general law. It is a theorem about finite automata. For pushdown automata it is false, and for the linear bounded automaton of chapter 61 it is an open question.

The exponential blow up is not always suffered. Most machines convert to something small. The bound is worst case and is achieved only by families built for the purpose.

Quick revision

• Theorem: for every NFA there is a DFA accepting the same language, so nondeterminism adds no power to

a finite automaton.

• Construction: states are subsets of Q; start is {q0}, or its epsilon closure; the cell for S on a is

the union of the a moves of the members of S, closed under epsilon moves; final states are the subsets meeting F in at least one element.

• Build only the reachable subsets, outward from the start, and include the empty set as the dead state.
• Proof: by induction on string length, delta hat prime({q0}, w) equals delta hat(q0, w); acceptance

then matches by the definition of the final states.

• The converse is trivial: a DFA is an NFA with singleton cells.
• Cost: up to 2 to the n states, and the bound is achieved by the k-th from the right family.
• The subset machine need not be minimal.

Test yourself

1. State the four parts of the subset construction. States are the subsets of Q; the start state is the epsilon closure of {q0}; the transition for S on a is the epsilon closure of the union of delta(p, a) over p in S; a subset is final when it contains at least one final state of the NFA.

2. An NFA has 4 states, one of them final. How many states could the DFA have, and how many of them could be final? Up to 16. Of those, 8 contain the final state, so up to 8 are final.

3. Why must final states of M' be subsets meeting F rather than subsets of F? Because the NFA accepts when at least one run succeeds. A set containing one final state and three non final ones represents a successful run and must accept.

4. What is the empty set doing in the constructed machine? It is the state reached when every run has died, and it is the dead state: not final, and mapping to itself on every symbol. Including it is what makes the transition function total.

5. Give the base case and the inductive step of the equivalence proof. Base: on the empty string both sides are {q0}. Step: assuming the identity for w, the definition of delta prime and of the extended functions turn delta hat prime({q0}, wa) into the union of delta(p, a) over p in delta hat(q0, w), which is delta hat(q0, wa).

6. Does the theorem hold for pushdown automata? No. A nondeterministic pushdown automaton is strictly more powerful than a deterministic one, and the language of even length palindromes is the witness, which chapter 57 works through.

Accepts: ε, a, b, ab, aa

Rejects: ba, bab, abba

The closures, from chapter 15:

The new a column.

For p: the closure is {p, q, r, t}; a moves from those give p (from p) and s (from q), so {p, s}; the closure of that is {p, q, r, t} union {s}, which is {p,q,r,s,t}.

For q: the closure is {q}; a from q gives s; the closure of {s} is {s}.

For r: the closure is {r, t}; neither has an a move; so the empty set.

For s: the closure is {s}; no a move; empty.

For t: the closure is {t}; no a move; empty.

The new b column.

For p: the closure is {p, q, r, t}; b moves give r (from r); the closure of {r} is {r, t}.

For q: closure {q}; no b move; empty.

For r: closure {r, t}; b from r gives r; closure {r, t}.

For s: closure {s}; b from s gives s; closure {s}.

For t: closure {t}; no b move; empty.

The new final states. t is final already. The closure of p contains t, so p becomes final. The closure of r contains t, so r becomes final. The closures of q and s do not, so they do not.

Putting it together, with the epsilon column gone:

Accepts: ε, a, b, ab, aa, bb

Rejects: ba, bab, abba

The checker decides that equality exactly, so the removal has not merely been carried out, it has been proved to preserve the language.

Notice that p is now marked final, which it was not before. That is the step 2 correction, and without it the new machine would reject the empty string while the old one accepts it.

Method 2: the direct method

Sometimes quicker by hand, and it gives the same answer.

Instead of computing closures, look at each empty arrow in turn and push it through:

1. For each empty arrow from p to q, copy every outgoing symbol move of q onto p as well.
2. If q is final, mark p final.
3. Repeat until nothing changes, because a copied move may itself need pushing through another empty

arrow.

1. Delete the empty arrows.

Applied to R1: the arrows are p to q, p to r, and r to t.

Pushing r to t first, because t's moves are what r must gain: t has no moves, so nothing is copied, but t is final, so r becomes final.

Pushing p to r: copy r's b move, which is r, onto p, so p gains b to r. And r is now final, so p becomes final.

Pushing p to q: copy q's a move, which is s, onto p, so p gains a to s.

The result has p with a to {p, s} and b to {r}, q with a to s, r with b to r, and p, r, t final. That is the same machine as R2 with some redundant states in the cells collapsed, and the checker confirms the language is the same.

The two methods differ only in bookkeeping. Method 1 computes the whole closure once per state; method 2 propagates one arrow at a time and has to be iterated. Method 1 is safer under examination conditions because it cannot be stopped too early.

The proof that the language is unchanged

Claim. For every non empty string w, delta hat prime(q0, w) equals the epsilon closure of delta hat(q0, w).

Sketch, by induction on the length of w. For a string of length one, the definition of delta prime is exactly the right hand side. For a longer string wa, the inductive hypothesis gives the set after w as a closed set, and delta prime applied to a closed set then follows a moves and closes again, which is what delta hat does on the original machine. So the two agree.

The empty string is the case the claim excludes, and it is handled by the new final states. On the empty string delta hat prime(q0, epsilon) is {q0}, while delta hat(q0, epsilon) is the closure of q0. The two differ whenever q0 has empty moves. But the second part of the construction made q0 final exactly when its closure contains a final state, so the two machines still agree about whether the empty string is accepted.

That is why the final state adjustment is not a tidying up detail: it is the whole of the empty string case of the proof.

Distinctions

What it does NOT mean

Removing empty moves does not make the machine deterministic. The result is still an NFA: cells may hold several states. Determinism needs chapter 16 as well.

It does not reduce the number of states. The state set is unchanged. Only the arrows and the final markings change.

The final state adjustment is not optional. Skipping it breaks the machine on the empty string, and on every string that ends where an empty move would have led to acceptance.

The new machine may have more arrows. That is normal: the work an empty move used to do is now distributed among the symbol moves.

Quick revision

• Every epsilon-NFA has an equivalent NFA without empty moves, with the same states and the same start

state.

• New move: delta'(q, a) is the closure of the union of the a moves from the closure of q. Compute from

the inside out.

• New final states: the old ones, plus every state whose closure contains an old final state. This is the

step that preserves acceptance of the empty string.

• Method 2, equivalently: for each empty arrow from p to q, copy q's symbol moves onto p and make p final

if q is, and repeat until nothing changes.

• The state set does not change; the arrows and the final markings do.
• The result is an NFA, not a DFA; chapter 16 is still needed for determinism.

Test yourself

1. Give the formula for the new transition. delta'(q, a) is the epsilon closure of the union of delta(p, a) taken over every p in the epsilon closure of q.

2. Which states become final that were not, and why? Every state whose epsilon closure contains an old final state, because in the old machine a run could reach that final state from there for free, and in the new machine there are no free moves to reach it with.

3. A machine has an empty arrow from the start state to a final state. What must the new machine do? Make the start state final, so that the empty string is still accepted.

4. After removing empty moves, is the machine deterministic? No. It is an NFA with no epsilon column; cells may still hold several states. The subset construction is a separate step.

5. Does removing empty moves change the number of states? No. The state set and the start state are unchanged; only the transitions and the final markings differ.

6. Why must method 2 be repeated until nothing changes? Because pushing one empty arrow through can create a move that must itself be pushed through another empty arrow. A single pass can stop before the machine is correct.

So on the empty input a Moore machine writes one symbol and a Mealy machine writes nothing. That single sentence is worth more marks in this topic than anything else in the chapter, and it is why a converted machine's output is never quite the same string as the original's.

A Moore machine, worked

The task. Read a string over {a, b} and emit 1 whenever the string read so far ends in an even number of a, and 0 otherwise. Two states, one per parity.

This book writes a Moore machine as a transition table with one extra column, headed Output, holding the symbol the state emits.

State e means an even number of a so far and emits 1; state o means odd and emits 0.

Read the third line: on input aa the machine emits 1 for the start state e, then moves to o and emits 0, then moves back to e and emits 1. Three symbols for two of input, as the rule says. Every one of those five output strings is produced by executing the table, so a mistyped digit would stop this book being built.

A Mealy machine, worked

The task. Read a string over {0, 1} and emit, for each symbol, a 1 if that symbol differs from the one before it and a 0 if it is the same. The first symbol has nothing before it, and we choose to treat it as differing, so it emits 1.

Two states are needed, recording what the last symbol was. This book writes a Mealy machine with a pair of columns per input symbol: one for the next state, one for the output.

State init means nothing has been read; z means the last symbol was 0; u means the last symbol was 1.

The first line is the trap made visible: on the empty input a Mealy machine writes nothing at all.

Line four: reading 0110, the first 0 emits 1 and moves to z; the 1 differs so emits 1 and moves to u; the second 1 is the same so emits 0 and stays in u; the 0 differs so emits 1 and moves to z. Output 1101, four symbols for four of input.

Three differences, and the fourth that is not a difference

The last row is the one to remember. Chapter 19 converts either into the other, so neither can do anything the other cannot. The choice between them is a matter of convenience and of how many states you are willing to have, exactly as the choice between a DFA and an NFA was.

Why Moore often needs more states. A Moore machine's output is fixed by the state, so if the same condition must sometimes emit one symbol and sometimes another, the condition has to be split into two states. A Mealy machine reads the symbol before emitting and so can decide without splitting. Chapter 19 makes this precise: converting a Mealy machine to a Moore machine can multiply the states by the size of the output alphabet.

Where they are used

In hardware description. A Moore machine's output is stable for a whole clock period because it does not depend on the input, which matters when the output drives something. A Mealy machine reacts within the period, which is faster but can glitch. Every textbook of digital design has this comparison, and it is the practical reason both models exist.

In encoders and protocol machines. Anything that reads a stream and writes a stream.

Not in this book after chapter 19. MU's syllabus places Mealy and Moore machines here and does not return to them, and the rest of Module 1 is about acceptors. So the two conversion procedures of chapter 19 are what the examination actually asks for, and that is where the work is.

What it does NOT mean

These machines do not accept languages. They have no final states. A question asking which strings a Mealy machine accepts has misunderstood the definition.

The output alphabet is not the input alphabet. It is a separate set, Delta, and it may be different.

Moore is not slower or weaker. The two are equally powerful, and chapter 19 proves it by construction in both directions.

A Moore machine's extra output symbol is not an error. It is the symbol of the start state, emitted before any input is read, and it is required by the definition.

Neither is nondeterministic here. Both definitions above use a transition function, so both are deterministic. Nondeterministic transducers exist and are outside this syllabus.

Quick revision

• A Moore machine is (Q, Sigma, Delta, delta, lambda, q0) with lambda from Q to Delta: output per state.
• A Mealy machine is the same with lambda from Q times Sigma to Delta: output per state and symbol.
• Neither has final states; neither accepts a language; each computes a function from strings to strings.
• Moore emits n plus 1 symbols on an input of length n, Mealy emits n. On the empty input Moore writes one

symbol and Mealy writes none.

• In a diagram, a Moore output is written in the state circle and a Mealy output on the arrow.
• The two are equally powerful, and chapter 19 converts each into the other.
• Moore often needs more states, because one state cannot emit two different symbols.

Test yourself

1. Give the one difference between the definitions, and the consequence for output length. lambda maps Q to Delta for Moore and Q times Sigma to Delta for Mealy. So Moore emits a symbol for the start state before reading anything, giving n plus 1 symbols on an input of length n, while Mealy emits n.

2. What does a Mealy machine output on the empty input, and what does a Moore machine? Mealy outputs nothing at all. Moore outputs one symbol, the output of its start state.

3. Do these machines have final states? What follows? No. It follows that they do not accept languages; they define functions from input strings to output strings, and asking what they accept is a category error.

4. For S1 above, what is the output on bb, and why? The machine starts in e and emits 1; b keeps it in e and emits 1; b again keeps it in e and emits 1. So 111, three symbols for two of input, and every symbol is 1 because zero a is an even number of a.

5. Why might a Moore machine need more states than a Mealy machine for the same task? Because its output is determined by the state alone, so a condition that must emit different symbols depending on the symbol just read has to be split into several states.

6. Which is more powerful? Neither. Chapter 19 gives constructions in both directions, so each can simulate the other, and the choice between them is about convenience and state count.

Check the equivalence. T1 on abab gave 10011. The output of T1's initial state is 1. T2 on abab gave 0011. And 1 followed by 0011 is 10011. They agree, and on the empty input T1 gives 1 while 1 followed by T2's empty output is also 1.

Both output strings are produced by running the two tables, so the check above is not a claim about what should happen; it is a comparison of two executions.

Mealy to Moore

This direction is the one examinations set, and it is harder, because a Moore machine's output is tied to its state and a Mealy machine's state may need to emit different symbols on different arrows. The remedy is to split.

The procedure.

1. For each state q of the Mealy machine, look at every output symbol that appears on an arrow into q.

Make one copy of q for each such symbol, named q with that symbol attached, and give that copy the symbol as its Moore output.

1. If no arrow enters q at all, and q is the initial state, make a single copy of it and give it any output

symbol; the convention is to use the first symbol of Delta, and the examiner will accept a stated choice.

1. Transitions. From the copy of q labelled with symbol b, on reading a, go to the copy of delta(q, a)

labelled with the Mealy output lambda(q, a). Note which machine each part comes from: the destination state is the Mealy destination, and the label on it is the Mealy output of the arrow just taken.

1. The initial state of the Moore machine is the copy of q0 made in step 2, or, if arrows do enter q0, the

copy carrying the chosen initial output.

1. There are no final states in either machine, so nothing is carried over.

The state count can grow. A Mealy machine with n states and an output alphabet of size k becomes a Moore machine with at most n times k states, because each state may need one copy per output symbol. In practice many copies are unreachable and are dropped.

Worked: converting S2

S2 from chapter 18, the machine that emits 1 when a symbol differs from its predecessor:

Step 1: which outputs enter each state?

Arrows into z carry: 1 (from init on 0), 0 (from z on 0), 1 (from u on 0). So z needs copies for 0 and 1.

Arrows into u carry: 1 (from init on 1), 1 (from z on 1), 0 (from u on 1). So u needs copies for 0 and 1.

No arrow enters init, so by step 2 it gets a single copy. Its output is a free choice; take 0 and say so.

That gives five states: init, z0, z1, u0, u1, where the digit is the state's Moore output.

Step 3: the transitions. From any copy of a state, reading a symbol, go to the copy of the Mealy destination labelled with the Mealy output.

From init on 0: Mealy goes to z with output 1, so go to z1. From init on 1: to u with output 1, so u1.

From either copy of z on 0: Mealy goes to z with output 0, so z0. On 1: to u with output 1, so u1.

From either copy of u on 0: Mealy goes to z with output 1, so z1. On 1: to u with output 0, so u0.

Check the equivalence. T3 on 0110 wrote 1101. T4's initial output is 0. And T4 on 0110 wrote 01101, which is 0 followed by 1101. They agree. The same holds for 0101: 1111 against 0 followed by 1111.

Five states where the Mealy machine had three, which is the growth the procedure warns about, and here it is three plus two rather than three times two because init needed only one copy.

Both conversions on one page

Why the constructions work

Moore to Mealy. In the Moore machine, the symbol emitted at step i of a run is the output of the state reached after i symbols. In the Mealy machine as constructed, the symbol emitted at step i is the output written on the arrow taken at step i, which the construction set to the output of the state that arrow leads to, which is the same state. So the two agree at every step from step one onwards, and step zero is the initial output, which is the prefixed symbol.

Mealy to Moore. In the Moore machine as constructed, the copy the machine sits in after i symbols is labelled with the Mealy output of the arrow taken at step i. So the Moore output at step i, for i at least one, is exactly the Mealy output at step i. At step zero the Moore machine emits the label of the initial copy, which is the prefixed symbol. The transitions are faithful because the destination state of each Moore arrow is the Mealy destination, with only the label added, so the run visits the same Mealy states in the same order.

Both arguments are inductions on the length of the input, and both have the same shape as chapter 16's: assume the two runs agree after i symbols, then read one more.

What it does NOT mean

The two outputs are not equal as strings. The Moore output is one symbol longer, and the equivalence is stated with that symbol prefixed. An answer claiming the outputs are identical has not understood the definitions.

Mealy to Moore does not always multiply the states. It multiplies in the worst case. Here three became five, not six, because the initial state needed only one copy, and unreachable copies are always dropped.

The freely chosen initial output is not arbitrary in the answer. It is a free choice, but it must be stated, because the equivalence is only meaningful once the prefixed symbol is named.

Moore to Mealy does not lose information. The state outputs are recoverable, since every arrow into a state carries that state's output.

Quick revision

• Equivalence for these machines: the Moore output equals the initial state's output followed by the Mealy

output, for every input.

• Moore to Mealy: keep everything, and label each arrow with the output of the state it leads to. The state

count does not change. The initial output cannot be moved and is prefixed.

• Mealy to Moore: split each state into one copy per output symbol appearing on an arrow into it; from a

copy of q on a, go to the copy of delta(q, a) labelled lambda(q, a); the initial state's output is a free stated choice when no arrow enters it.

• Mealy to Moore can need up to n times the size of Delta states; unreachable copies are dropped.
• Both constructions are proved by induction on input length, the two runs being shown to agree step by

step.

Test yourself

1. State what equivalence means for a Moore and a Mealy machine. For every input string, the Moore output equals the output of the Moore machine's initial state followed by the Mealy output. The two are never equal as strings, because the Moore output is one symbol longer.

2. Convert this Moore machine to a Mealy machine: states p and q, p start with output 0 and q with output 1, p on a goes to q and on b to p, q on a goes to q and on b to p. Same two states. The arrow p on a leads to q, so it carries 1. The arrow p on b leads to p, so it carries

1. The arrow q on a leads to q, so 1. The arrow q on b leads to p, so 0. The state outputs are deleted, and

the initial 0 is prefixed.

3. How many states can a Mealy machine with 4 states and an output alphabet of 3 symbols need after conversion? Up to 12, one copy of each state per output symbol, less however many copies turn out to be unreachable.

4. In the Mealy to Moore construction, where does the label on the destination copy come from? From the Mealy output of the arrow being taken, not from the destination state and not from the source.

5. Why is the initial state sometimes given a freely chosen output? Because a Moore machine must emit a symbol for its initial state, and if no arrow enters that state there is no Mealy output to take the symbol from. The choice must be stated, since it is the symbol the equivalence prefixes.

6. Does either conversion change what the machine can compute? No. Both directions exist, so the two models compute exactly the same functions from strings to strings, and the conversions are about convenience and state count.

The method builds up by the length of the distinguishing string, which is why it is called k-equivalence.

Definition. p and q are k-equivalent when, for every string w of length at most k, the machine accepts w from p exactly when it accepts w from q.

0-equivalence is the first partition: every string of length at most 0 is the empty string, and the empty string is accepted from p exactly when p is final. So the states split into two blocks, the final ones and the non final ones.

The refinement step. Given the k-equivalent blocks, p and q are (k plus 1)-equivalent when they are k-equivalent and, for every symbol a, the states delta(p, a) and delta(q, a) lie in the same k-equivalent block. In words: they agree now, and every symbol takes them to places that agree.

Stopping. Keep refining. Each round either splits a block or changes nothing, and when a round changes nothing the partition is final and the process stops. It must terminate, because a partition of a finite set can only be refined finitely often.

The answer. The blocks are the states of the minimal machine. A block is final if its members are final, which is well defined because 0-equivalence never puts a final state with a non final one. The transition from a block on a symbol is the block containing delta(p, a) for any p in it, which is well defined because that is exactly what the refinement guaranteed.

Worked example 1: eight states down to five

Start with W1, over {0, 1}.

Accepts: 01, 10, 011, 101, 0111, 1011

Rejects: ε, 0, 1, 00, 11, 010, 111

Step one: reachability. Mark A. From A: B and F. From B: G and C. From F: C and G. From G: G and E. From C: A and C. From E: H and F. From H: G and C. Marked: A, B, C, E, F, G, H. D is never marked, so D is unreachable and its row goes. Seven states remain.

Notice that D's cells name C and G, both of which are reachable by other routes, so deleting D changes nothing about them.

Step two: 0-equivalence. The final states are {C} and the non final ones are {A, B, E, F, G, H}. Two blocks.

Refining to 1-equivalence. For each state in the big block, record which block each symbol leads to, writing 1 for the final block and 2 for the non final one.

Three patterns appear among these six: (2, 2) for A, E and G; (2, 1) for B and H; (1, 2) for F. So the big block splits into {A, E, G}, {B, H} and {F}, and with {C} that is four blocks.

Refining to 2-equivalence. Repeat with the four blocks, numbering them 1 = {C}, 2 = {A, E, G}, 3 = {B, H}, 4 = {F}.

Within {A, E, G}: A gives (3, 4), E gives (3, 4), G gives (2, 2). So G separates from A and E, and the block splits into {A, E} and {G}. Within {B, H}: both give (2, 1), so they stay together. The blocks are now {C}, {A, E}, {G}, {B, H}, {F}: five of them.

Refining again. With five blocks, numbering 1 = {C}, 2 = {A, E}, 3 = {G}, 4 = {B, H}, 5 = {F}: A gives (4, 5) and E gives (4, 5), so {A, E} holds; B gives (3, 1) and H gives (3, 1), so {B, H} holds. Nothing splits, so the partition is final.

The minimal machine, five states, naming each block after its first member:

Reading the last row: G on 1 goes to E in the original, and E now lives in the block called A, so it goes to A.

Accepts: 01, 10, 011, 101, 0111, 1011

Rejects: ε, 0, 1, 00, 11, 010, 111

That single line is the whole claim of this example, and the checker proves both halves of it: that the two machines accept exactly the same language, decided exactly by product construction, and that five is the minimum, decided by minimising W1 independently and counting.

Eight states down to five: one unreachable, and two merges.

Worked example 2: the subset construction's waste removed

Chapter 16 converted the aba machine and got six states, where the hand designed machine of chapter 13 had four. Here is the six state machine again.

Accepts: aba, aabab, ababa

Rejects: ε, ab, abb, aab

0-equivalence: finals {D, E, F}, non finals {A, B, C}.

1-equivalence. Among the finals: D on a gives D (final block), on b gives E (final block), so (F, F) writing F for the final block. E on a gives D (F), on b gives F (F), so (F, F). F likewise (F, F). No split. Among the non finals: A gives B (N) and A (N), so (N, N). B gives B (N) and C (N), so (N, N). C gives D (F) and A (N), so (F, N). So C separates: {A, B} and {C}.

2-equivalence. Blocks 1 = {D, E, F}, 2 = {A, B}, 3 = {C}. A gives B (2) and A (2). B gives B (2) and C (3). So A and B separate. Blocks: {D, E, F}, {A}, {B}, {C}: four.

3-equivalence. Among {D, E, F}: D gives D (1) and E (1); E gives D (1) and F (1); F gives D (1) and F (1). All (1, 1), no split. Nothing else can split. Four blocks, and the process stops.

Accepts: aba, aabab, ababa, bbabab

Rejects: ε, ab, abb, aab, bbb

Four states, which is exactly the size of the machine designed by hand in chapter 13, and comparing the two tables shows they are the same machine with the states renamed. That is not luck; chapter 21 proves it had to happen.

Worked example 3: a machine that is already minimal

Worth doing, because a student must be able to say so rather than keep refining.

Accepts: a, aa, ba, aba

Rejects: ε, b, ab, bb

0-equivalence gives {p} and {q}, two blocks, and with two states there is nothing to refine. Both states are reachable. So the machine is minimal.

That claim is not a tautology to the checker: it minimises W5 and requires the answer to have the same number of states, so a machine wrongly called minimal would fail.

Distinctions

What it does NOT mean

Minimising does not change the language. That is the whole point, and every claim in this chapter is checked for it.

Two states with the same row are not the only mergeable pair. In example 1, A and E have different rows (B and F against H and F) and merge anyway, because B and H turn out to be equivalent themselves. Comparing rows by eye finds some merges and misses others; the refinement finds all of them.

A final and a non final state are never equivalent. The empty string distinguishes them, which is exactly what 0-equivalence records.

The dead state does not disappear. If the machine needs a state from which nothing is accepted, the minimal machine has exactly one such state. Minimal means fewest states, not no waste of a human kind.

Minimising an NFA is a different and harder problem. Everything here is about DFAs. The minimal NFA for a language need not be unique, and finding it is far harder than this refinement. MU's label is about the DFA case.

Quick revision

• Two states are equivalent when no string is accepted from one and rejected from the other. Such a string

is a distinguishing string.

• Minimise in two steps, in this order: delete unreachable states, then merge indistinguishable ones.
• 0-equivalence splits finals from non finals. Refine: p and q stay together when they are k-equivalent

and every symbol takes them into the same k-equivalent block.

• Stop when a round changes nothing. Termination is guaranteed because a finite partition refines finitely

often.

• The blocks are the states of the minimal machine; a block is final if its members are; the transition

from a block is the block containing the transition of any member.

• The minimal DFA is unique up to state names, which chapter 21 proves, and that is what makes it

canonical.

• Two states with different rows may still merge. Comparing rows by eye is not the method.

Test yourself

1. Give the two things minimisation removes, and the order. Unreachable states first, by a reachability search, deleted outright. Then indistinguishable states, by k-equivalence refinement, merged. Skipping the first makes the answer too big.

2. What partition is 0-equivalence, and why? The final states against the non final states, because the only string of length 0 is the empty string, and it is accepted from a state exactly when that state is final.

3. State the refinement condition. p and q are (k plus 1)-equivalent when they are k-equivalent and, for every symbol a, delta(p, a) and delta(q, a) lie in the same k-equivalent block.

4. How do you know the process stops? Because each round either splits a block or changes nothing, and a partition of a finite set of states can only be refined a finite number of times.

5. Two states have identical rows in the table. Are they necessarily equivalent? And if their rows differ, are they necessarily distinguishable? Identical rows with the same final status do make them equivalent. Different rows do not make them distinguishable: in this chapter's first example A and E have different rows and merge, because the states their rows name are themselves equivalent.

6. Why does the uniqueness of the minimal DFA matter? Because it makes the minimal machine a property of the language rather than of a construction, which is what allows two machines to be compared by minimising both, and what makes the equivalence problem of chapter 39 decidable.

The first half: a regular language has finite index

Suppose L is regular, so some DFA M with n states accepts it.

If delta hat(q0, x) equals delta hat(q0, y), then x and y are L-equivalent. The reason is the identity of chapter 11: delta hat(q0, xz) equals delta hat from the state reached after x on z, and the same for y, so if those states are the same then both end in the same state on every z, and so agree about acceptance.

So the map sending a string x to the state delta hat(q0, x) is constant on L-equivalence classes, and therefore there are at most as many classes as there are states. At most n classes: finite.

The second half: finite index gives a machine

Suppose the relation has finitely many classes. Build a machine whose states are the classes.

States: the L-equivalence classes. Start state: the class of the empty string. Transition: from the class of x on symbol a, go to the class of xa. This is well defined and it is the only thing that needs checking: if x and y are L-equivalent, then xa and ya are L-equivalent, because any z distinguishing xa from ya would make az a distinguishing extension of x and y. Final states: the classes whose members are in L. Well defined because the empty string is a legal z, so two L-equivalent strings are both in L or both out.

Then, by induction on the length of w, the machine reaches the class of w on input w, so it accepts w exactly when the class of w is final, which is exactly when w is in L. So L is regular, and the machine has one state per class.

Putting the halves together gives the theorem, and one more thing: the machine just built has exactly index-many states, and the first half showed no machine can have fewer. So it is minimal, and it was constructed from the language alone with no reference to any machine. That is the uniqueness chapter 20 promised: any minimal DFA for L must have index-many states, and merging its states by the relation gives this same machine, so all minimal DFAs for L are the same up to the names of their states.

Worked example 1: a regular language, and its index

Let L be the strings over {a, b} that end in ab. Chapter 13's machine has three states, so the index should be 3, and here are the three classes with the reasoning.

The only thing that matters about a string, for deciding whether anything appended to it ends in ab, is how much of ab it currently ends with. So the candidate classes are:

Three, and no more: every string falls into one of the three, because it either ends in ab, or ends in a without ending in ab, or neither.

Three, and no fewer: each pair is distinguished by an explicit z, which is what a proof requires.

So the index is exactly 3, the language is regular, and the minimal DFA has 3 states. Here it is, being the machine of chapter 13 with its states renamed after the classes:

Accepts: ab, aab, bab, abab

Rejects: ε, a, b, ba, aba, abb

The claim is checked, so the machine really does have the smallest possible number of states, which the index argument predicted.

Worked example 2: a language proved NOT regular

Let L be the set of strings a to the n followed by b to the n, for n at least 0. So L holds epsilon, ab, aabb, aaabbb and so on.

Claim. L is not regular.

Proof by Myhill Nerode. Consider the infinitely many strings

that is, a to the i for every i at least 0. Take any two of them with different exponents, say a to the i and a to the j with i less than j. Then the extension

distinguishes them: a to the i followed by b to the i is in L, while a to the j followed by b to the i is not, because j is not i.

So no two of these strings are L-equivalent, and there are infinitely many of them, so there are infinitely many classes. The index is infinite, and by the theorem L is not regular.

That is the whole proof. Compare it with the pumping lemma proof of the same fact in chapter 37, which needs a supposed machine, a pigeonhole argument and a case analysis. This one needs an infinite family and one distinguishing extension.

The shape to remember, because every such proof has it:

1. Name an infinite family of strings, indexed by a number.
2. Take any two of them with different indices.
3. Produce one z, written in terms of the indices, that is accepted after one and not after the other.
4. Conclude that there are infinitely many classes, so the language is not regular.

Step 3 is the whole work, and step 1 is where the thinking goes: the family has to be chosen so that a distinguishing extension exists.

Worked example 3: a second language, for the pattern

Let L be the set of palindromes over {a, b}, that is, strings equal to their own reversal.

Family: a to the i followed by b, for i at least 1. So ab, aab, aaab, and so on.

Take two, with i less than j. Distinguishing extension: z equal to a to the i. Then a to the i, then b, then a to the i is a palindrome, because it reads the same both ways. But a to the j, then b, then a to the i is not, because it has j of a at the front and i at the back and j is not i.

Infinitely many classes, so the palindromes are not regular. Chapter 56 builds a pushdown automaton for this language, which is the machine that can do it.

Worked example 4: a language that IS regular, proved so

The theorem works in this direction too, which the pumping lemma cannot do.

Let L be the strings over {0, 1} whose value as a binary number is divisible by 3, as in chapter 13's machine 4.

Claim. The index is at most 3, so L is regular.

Proof. If x and y have the same remainder on division by 3 when read as binary numbers, then for any z the numbers xz and yz have the same remainder as each other, because appending a bit b takes a number n to 2n plus b, and that operation depends only on n's remainder. So xz is in L exactly when yz is, and x and y are L-equivalent. There are only three remainders, so there are at most three classes, and the index is finite. By the theorem, L is regular.

And it is exactly 3, because 0, 1 and 10 have remainders 0, 1 and 2 and so lie in three different classes, each pair being distinguished: 0 and 1 by the empty extension, 1 and 10 by the extension 1, since 11 is 3 and is divisible by 3 while 101 is 5 and is not.

Distinctions

What it does NOT mean

It is not about equal strings. Two L-equivalent strings can look nothing alike: aab and bbbab are in the same class for the ends-in-ab language.

Finite index is not the same as a finite language. The ends-in-ab language is infinite and has index 3.

The classes are not the language and its complement. They are classes of Sigma star under the relation, and there are as many as the minimal machine has states, some of them classes of strings not in L at all.

Producing one distinguishing extension is not enough on its own. You need infinitely many pairwise distinguishable strings. One pair proves two classes, which proves nothing.

The theorem does not give an algorithm for the index of an arbitrary language. It characterises regularity; identifying the classes still takes an argument.

Quick revision

• x and y are L-equivalent when, for every z, xz is in L exactly when yz is. Such a z that separates them

is a distinguishing extension.

• It is an equivalence relation on Sigma star, and the number of classes is its index.
• Myhill Nerode: L is regular if and only if the index is finite, and then the index is the number of states

of the minimal DFA.

• Half one: strings reaching the same state are L-equivalent, so classes are at most states.
• Half two: build a machine whose states are the classes, start at the class of epsilon, move from the class

of x on a to the class of xa, and make final the classes inside L.

• Hence the minimal DFA is unique up to state names, which is what chapter 20 relied on.
• To prove a language not regular: name an infinite family, and for any two members give one z that

separates them.

• Unlike the pumping lemma it is an if and only if, so it can also prove a language regular.

Test yourself

1. Define the Myhill Nerode relation, and say what a distinguishing extension is. x is L-equivalent to y when for every string z, xz is in L exactly when yz is in L. A distinguishing extension is a z for which the two disagree, which proves the strings are in different classes.

2. State the theorem, both halves, and the extra fact about counting. L is regular if and only if the relation has finitely many classes, and when it does, the number of classes equals the number of states of the minimal DFA for L.

3. Prove that the language of strings over {a, b} with equally many a and b is not regular. Take the family a to the i for i at least 0. For i less than j, the extension b to the i is accepted after a to the i and not after a to the j, since the second has j of a and i of b. So there are infinitely many classes and the language is not regular.

4. The ends-in-ab language has index 3. Name the three classes and one extension separating each pair. The class of strings ending in neither a nor ab, of strings ending in a but not ab, and of strings ending in ab. The extension b separates the first from the second; the empty string separates the first from the third and the second from the third.

5. Why can the pumping lemma not prove a language regular, while this theorem can? Because the pumping lemma is a one way implication: regular languages pump, so failing to pump proves irregularity, but pumping successfully proves nothing. Myhill Nerode is an equivalence, so finite index proves regularity outright.

6. A student gives one pair of distinguishable strings and concludes the language is not regular. What is missing? Infinitely many pairwise distinguishable strings. One pair shows only that the index is at least 2, which every non trivial language satisfies.

The vertical bar means "or". Several rules with the same left hand side may be written on one line:

is two productions, S to aSb and S to ab. It is an abbreviation and nothing more.

Epsilon is a legal right hand side. A rule whose right hand side is the empty string is written with the epsilon symbol, and it means the variable may be deleted:

Such a rule is called a null production or an epsilon production, and chapter 46 is about removing them where possible.

Spaces are optional. MU writes S->0S1 and this book does too. Writing S -> 0 S 1 means exactly the same. Where a variable has a name longer than one letter the spaces stop being optional, and this book then uses them.

The first grammar, worked

Take:

S->aSb | ε

Accepts: ε, ab, aabb, aaabbb

Rejects: a, b, ba, aab, abb, abab

Its four parts. V is {S}. T is {a, b}. P is the two productions. The start symbol is S.

What it produces. Begin with S, the start symbol. Apply the first rule: aSb. Apply it again: aaSbb. Again: aaaSbbb. At any point apply the second rule instead, which deletes the S and leaves a finished string. So the strings are

that is, a to the n followed by b to the n for every n at least 0. And that is the language chapter 21 proved is not regular. So a grammar this small describes something no finite automaton can accept, which is the first sign that grammars will reach further than machines of chapter 9. Module 2 builds the machine that matches.

The vocabulary of a derivation

Three words are needed and are defined properly in chapter 23. They are named here because they appear in every later definition.

A sentential form is any string of variables and terminals that a derivation can reach. S is one, aSb is one, and aabb is one. A sentential form with no variables left in it is called a sentence or a terminal string, and it is finished: no rule can apply to it, because every left hand side contains a variable.

Derives is what one step of rewriting does, and it is written with a single arrow. Derives in any number of steps, including none, is written with a starred arrow, which is the reflexive transitive closure of chapter 4.

The language generated

Two conditions, and students drop the first. The string must consist of terminals only: a derivation that has reached aSb has not produced a member of the language, because S is still there. And it must be reachable from the start symbol, not from some other variable.

Chapter 24 treats this properly, including how to prove that a grammar generates the language you claim.

Grammars are not restricted to context free ones

This matters, because MU's Chomsky classification in chapter 26 needs the general definition and most books quietly give the context free one.

In the general definition, a production is alpha to beta where alpha is any string containing at least one variable, and beta is any string at all. So a rule may have several symbols on the left:

is a perfectly legal production of a general grammar. It says that the three symbol sequence aSb may be replaced by bSa, and it can only be applied where all three occur together in that order.

A grammar in which every left hand side is a single variable is called context free, and that is the kind chapter 41 onwards is about. The name says why: a rule like S to aSb may be applied to any S no matter what surrounds it, so the context does not matter. A rule like aSb to bSa is context sensitive: the S may only be rewritten when it has an a before it and a b after it.

Most of this book's grammars are context free. The general form is what makes the four types of chapter 26 four different things.

A worked grammar with two variables

Something less symmetrical, to show the variables working.

S->0A | 1S | ε
A->0S | 1A

V is {S, A}, T is {0, 1}, and the start symbol is S.

What does it do? Read the variables as conditions, exactly as the states of a machine were read in chapter

1. S means an even number of 0 has been produced so far; A means an odd number. Producing a 0 switches, so S

sends you to A and A sends you back to S; producing a 1 does not, so each variable keeps itself. Only S can finish, because only S has the epsilon rule.

So the language is the strings over {0, 1} with an even number of 0. And here is the machine for the same language, from chapter 10:

Accepts: ε, 1, 00, 11, 001, 0011

Rejects: 0, 01, 10, 000, 0001

The checker decides that equality by running the machine and the grammar against each other over every string up to its bound, so the reading of the variables just given is not a claim to be taken on trust.

Notice how closely the grammar copies the machine: one variable per state, one production per transition, and an epsilon rule on the variable for the final state. That correspondence is exactly what chapter 30 formalises, and it is why the smallest class of grammars matches the smallest class of machines.

Distinctions

What it does NOT mean

The arrow is not an equation. S->aSb does not say S equals aSb. It says S may be replaced by aSb, in that direction only, as many times as you like or not at all.

A grammar does not read anything. It has no input. Asking what a grammar accepts is loose talk for what it generates, and the distinction matters when a question asks you to convert one into a machine.

A variable is not a state. The resemblance in the worked example above is real and useful, and it is a theorem rather than a definition. In the grammars of chapter 41 onwards a variable stands for a whole sub structure, not for a condition.

The empty string is not "nothing". A rule to epsilon deletes a variable and leaves a legitimate string, possibly empty. Chapter 3 said the same thing about strings.

V and T must be disjoint. A symbol that is both a variable and a terminal makes the definition of a finished string meaningless.

Quick revision

• A grammar is G = (V, T, P, S): variables, terminals, productions, start symbol. V and T are disjoint.
• A production alpha to beta may be applied wherever alpha occurs; the left hand side must contain at least

one variable.

• The vertical bar abbreviates several productions with the same left hand side.
• A right hand side may be epsilon, which deletes the variable. That is a null production.
• A sentential form is anything a derivation can reach; one with no variables is a finished terminal string.
• L(G) is the set of terminal strings derivable from S in any number of steps. Both conditions matter.
• Context free means every left hand side is a single variable. The general definition allows more, and

chapter 26 needs it.

• A grammar generates and a machine recognises. S->aSb | ε generates a language no finite automaton can

accept.

Test yourself

1. Give the four parts of a grammar and the condition on a production. V the variables, T the terminals with V and T disjoint, P the productions, and S in V the start symbol. Each production is alpha to beta with alpha containing at least one variable.

2. What language does S->aS | a generate? One or more a. Every derivation applies the first rule some number of times and then must finish with the second, so at least one a is produced and there is no upper limit.

3. What is the difference between a sentential form and a sentence? A sentential form may still contain variables; a sentence contains only terminals and is therefore finished, because every production's left hand side holds a variable.

4. Why must the two conditions in the definition of L(G) both be stated? Because a derivation from S may stop at a form that still contains variables, and that form is not in the language; and because a string derivable from some other variable need not be derivable from S.

5. Is aSb->bSa a legal production? What does allowing it mean? Legal in a general grammar, because its left hand side contains a variable. Allowing it means the grammar is not context free: the S may be rewritten only when an a precedes and a b follows it.

6. Write a grammar for the strings over {a, b} that begin with a. S->aA, A->aA | bA | ε. The first rule forces the initial a and A then generates anything at all, including the empty continuation.

This is the reflexive transitive closure of chapter 4, and the notation is the same.

How to set a derivation out

One form per line, starting with the start symbol and ending with the finished string. Each line is one step. It is worth writing which production was used at each step where the grammar has several, and any examiner will accept it and most will expect it.

Take the grammar of chapter 22:

S->aSb | ε

Accepts: ε, ab, aabb, aaabbb

Rejects: a, b, ba, aab, abab

A derivation of aabb:

S
aSb
aaSbb
aabb

Four lines, so three steps: the first rule twice and then the second rule to delete the S. That is the whole derivation, and the checker re-derives it, so if the second line read aSSb the book would not build.

A grammar with a choice at every step

Here is one where the derivations are more interesting, because there is more than one variable to rewrite.

S->AB
A->aA | a
B->bB | b

Accepts: ab, aab, abb, aabb, aaabbb

Rejects: ε, a, b, ba, bab

This grammar makes one or more a followed by one or more b. Note the difference from B1: there is no matching here, because A and B grow independently, so aab and abb are both in the language while neither is in B1's.

A derivation of aabb, rewriting the leftmost variable every time:

S
AB
aAB
aaB
aabB
aabb

Six lines, five steps. Look at line three: the form is aAB, there are two variables in it, and the leftmost is A, so the leftmost discipline rewrites A. The checker proves not only that each step is legal but that the leftmost occurrence was the one chosen, so a derivation labelled leftmost that is not one fails the build.

And the same string derived rewriting the rightmost variable every time:

S
AB
AbB
Abb
aAbb
aabb

The same six lines in a different order, and the same string at the end. Chapter 43 is about what these two have in common, which turns out to be the derivation tree.

The trap: one occurrence at a time

Take a grammar with a variable appearing twice on a right hand side.

S->SbS | a

Accepts: a, aba, ababa, abababa

Rejects: ε, b, ab, ba, abab, aa

A correct derivation of ababa:

S
SbS
abS
abSbS
ababS
ababa

Six lines, five steps. The second line has two copies of S. Step two rewrites the leftmost of them, and the other is copied over untouched. A student who rewrites both in one line has written something that is not a derivation, and the checker refuses it.

Note also that this grammar is ambiguous, which chapter 44 is about: ababa has more than one derivation tree, and the checker can produce two of them.

A general grammar, where the left hand side is longer

Chapter 22 said a production's left hand side may be more than one symbol, and a derivation then has one extra thing to look for: the occurrence must match the whole left hand side in order.

S->aSBc | abc
cB->Bc
bB->bb

Accepts: abc, aabbcc, aaabbbccc

Rejects: ε, a, ab, abcc, aabc, aabbc

This is a context sensitive grammar, and it generates a to the n, b to the n, c to the n. A derivation of aabbcc:

S
aSBc
aabcBc
aabBcc
aabbcc

Five lines, four steps. Step one applies the first rule. Step two applies S to abc inside the form aSBc, leaving the B and the c where they were. Step three applies cB to Bc, which needs a c immediately followed by a B, and the form aabcBc has one. Step four applies bB to bb, which needs a b immediately followed by a B.

The B is doing the work of a courier. It is created on the right of the S, and each application of the first rule creates one more, so the number of B always equals the number of a. Then cB to Bc lets a B walk left past a c, and bB to bb turns it into a b when it reaches the b block. So the count of b ends up equal to the count of a, and the count of c was equal from the start. That is the standard way a context sensitive grammar counts three things at once, and it is worth seeing once, because chapter 26 classifies grammars by exactly this sort of rule and chapter 60 builds the machine for them.

Reading a grammar you are given

MU's 2018 paper sets this directly: "If G = ({S}, {0, 1}, {S->0S1, S->epsilon}, S), find L(G)".

The method is to derive the shortest few strings and look for the pattern, then check the pattern by argument rather than by more examples.

S->0S1 | ε

Accepts: ε, 01, 0011, 000111

Rejects: 0, 1, 10, 001, 011, 0101

Shortest first. Applying the second rule immediately gives epsilon. Applying the first rule once and then the second gives 01. Twice then the second gives 0011. So the pattern is 0 to the n followed by 1 to the n.

And the argument: the only way to finish is the epsilon rule, which must be applied to the single S, and every application of the first rule adds exactly one 0 on the left of the S and one 1 on the right. So the counts are equal by construction, and the 0 all precede the 1 because nothing ever moves a symbol. Chapter 24 sets out how to write that argument as a proof.

Distinctions

What it does NOT mean

A derivation is not a proof that the grammar is correct. It shows one string is in the language. Chapter 24 is about the other direction.

A step does not rewrite every occurrence. One occurrence, one production, everything else copied.

The starred arrow is not "many steps". It is zero or more, and the zero case is used in every induction.

A derivation does not have to be leftmost. Any order of rewriting is a derivation. Leftmost and rightmost are disciplines imposed for a purpose, which chapter 42 explains.

Two derivations of the same string are not automatically a sign of ambiguity. The grammar B2 above has a leftmost and a rightmost derivation of aabb and is not ambiguous. Ambiguity is about two derivation trees, which chapter 44 defines precisely.

Quick revision

• One step: find a production's left hand side in the form, replace that one occurrence by the right hand

side, copy everything else. Written with a single arrow.

• Zero or more steps: written with a starred arrow, the reflexive transitive closure, so every form derives

itself.

• A derivation is written one form per line, from S to a terminal string, one step per line.
• Leftmost rewrites the leftmost variable at every step; rightmost the rightmost. Each tree has exactly one

of each.

• A variable appearing twice in a form is rewritten one copy at a time.
• In a general grammar the whole left hand side must occur, in order, for the rule to apply.
• To find what a grammar generates: derive the shortest strings, spot the pattern, then argue it.

Test yourself

1. Give the definition of one step of derivation. If alpha to beta is a production and the current form is gamma alpha delta, then the next form may be gamma beta delta: one occurrence of one left hand side is replaced, and the surroundings are unchanged.

2. Why is the starred arrow reflexive? Because it allows zero steps, and a chain of zero steps leads from any form to itself. That case is what the base case of every induction over derivations uses.

3. For S->SbS | a, give a leftmost derivation of aba. S, then SbS, then abS, then aba. Three steps: the first rule, then the second applied to the leftmost S, then the second applied to the remaining S.

4. A student writes S, then SbS, then aba in two steps. What is wrong? The second step rewrites both copies of S at once, which is two applications of a production and therefore two steps. A derivation must show each one.

5. In the grammar S->aSBc | abc, cB->Bc, bB->bb, why can cB->Bc not be applied to the form aSBc? Because the rule needs a c immediately followed by a B, and in aSBc the B is preceded by S and followed by c. The whole left hand side must occur, in order, for a production to apply.

6. What is the difference between a derivation and a derivation tree? A derivation is an ordered sequence of rewriting steps, so the same tree gives many derivations differing only in the order the variables were taken. A tree records which production was used on which symbol and forgets the order, which is why ambiguity is defined on trees and not on derivations.

S
0S1
00S11
0011

Step 2. The pattern is 0 to the n followed by 1 to the n, for n at least 0.

Step 3. The grammar has one variable and two rules. The only way to finish is the epsilon rule, and it applies to the single S. Every application of the first rule adds exactly one 0 immediately to the left of the S and one 1 immediately to the right. So at every stage the form is 0 to the k, then S, then 1 to the k, and nothing can disturb that because there is only ever one S and nothing moves symbols. When the epsilon rule is used the S vanishes and 0 to the k followed by 1 to the k is left.

So:

That step 3 argument is the first containment, done informally. Below it is done properly.

The proof, both halves, on C1

Write A for the claimed set, the strings 0 to the n followed by 1 to the n for n at least 0.

Half one: L(C1) is contained in A

The technique is to find an invariant: a property every sentential form reachable from S has.

Claim. Every sentential form derivable from S is either 0 to the k, S, 1 to the k for some k at least 0, or 0 to the k followed by 1 to the k for some k at least 0.

Proof by induction on the number of steps.

Base case, zero steps. The form is S, which is 0 to the 0, S, 1 to the 0. True.

Inductive step. Suppose the form after i steps has the claimed shape. If it has no S in it, no production applies, and there is no i plus 1 step to consider. If it is 0 to the k, S, 1 to the k, then exactly one production can be applied, to the S, and there are two choices:

• The first rule replaces S by 0S1, giving 0 to the (k plus 1), S, 1 to the (k plus 1). Still the first

shape.

• The epsilon rule deletes S, giving 0 to the k followed by 1 to the k. The second shape.

Either way the claim holds after i plus 1 steps.

Finishing. A string of L(C1) is a terminal string, so it has no S, so by the claim it is 0 to the k followed by 1 to the k for some k. That is a member of A.

Half two: A is contained in L(C1)

Proof by induction on n.

Base case, n equal to 0. The string is epsilon, and S derives epsilon in one step by the second rule.

Inductive step. Suppose 0 to the n followed by 1 to the n is derivable from S, by some derivation. Then

so putting a 0 in front and a 1 behind every form of that derivation gives a derivation of 0 to the (n plus

1. followed by 1 to the (n plus 1). This works because a derivation step is unaffected by what surrounds the

occurrence rewritten, which is exactly the gamma and delta of chapter 23's definition.

Therefore every member of A is derivable, and with half one, L(C1) equals A.

That is what a complete answer looks like. It is two inductions, each about half a page, and the pattern is the same in every such proof: half one finds an invariant over forms, half two builds a derivation from the string.

A second worked pair: a grammar that is too generous

Here is the failure mode half one catches, made concrete.

Suppose a student is asked for a grammar for the strings over {a, b} with equally many a and b, and writes:

S->aSb | bSa | ε

Accepts: ε, ab, ba, abab, aabb

Rejects: a, b, aab, abb, baab, abba, aabbb

Is it right? Every rule adds one a and one b, so half one goes through: every string it makes has equally many of each. So the grammar is not too generous.

But it is too mean, and the claim lists above already show it: baab and abba both have two a and two b, so both belong in the language, and this grammar rejects both.

Take baab and see why. It begins with b, so its derivation must begin with the rule b S a, giving the form b S a with the final a already placed. The middle must then derive aa. But every rule of this grammar adds one a and one b, so S can only ever derive a string with equal counts, and aa has two a and no b. The same argument kills abba, whose first rule must be a S b, leaving the middle to derive bb.

S->aSb | bSa | SS | ε

Accepts: ε, ab, ba, baab, abba, abab, aabb, aabbab

Rejects: a, b, aab, abb, aba, aabbb

Adding the rule S->SS repairs it, because it allows a balanced string to be split into two balanced pieces placed side by side: baab is ba followed by ab, and abba is ab followed by ba. The checker runs both grammars, so the difference between them is demonstrated rather than asserted: C2 rejects baab and abba, and C3 accepts both.

And the repaired grammar is now ambiguous, which chapter 44 will explain is the price of the SS rule.

The other direction: a grammar that is too generous

S->aS | Sb | ε

Accepts: ε, a, b, ab, aab, abb, aabb

Rejects: ba, bab, aba

A student might offer this for "n a followed by n b". It is not: it accepts a, which has one a and no b, and it accepts aab. The rules add a on the left and b on the right independently, with nothing forcing the counts to agree. Half one of the proof fails immediately, because the invariant "the counts are equal" does not survive the first rule.

Its actual language is a star followed by b star, which is a perfectly good regular language and not the one asked for. That is why the first half of the proof is worth doing: the grammar looks plausible and is wrong.

Distinctions

What it does NOT mean

A list of derivable strings is not L(G). L(G) is usually infinite, and a list is evidence about a pattern rather than the answer.

A sentential form is not in L(G) unless it is terminal. 0S1 is derivable from S and is not in the language.

A string derivable from some variable is not in L(G) unless it is derivable from S. In C3 above, strings derivable from S happen to be all of them because there is one variable, but in a grammar with several variables this catches people.

Half one alone is not a proof. Nor is half two. A grammar can pass either and fail the other, and the two worked failures above are one of each.

Examples are not a proof. They are how you find the pattern, which is step 1 of a different task.

Quick revision

• L(G) is every terminal string derivable from S in zero or more steps. Both conditions matter.
• To find L(G): derive the shortest strings, state the pattern in words, then justify it from the

productions.

• To prove L(G) equals A: two containments. L(G) inside A by an invariant over sentential forms, proved by

induction on the number of steps. A inside L(G) by constructing a derivation of an arbitrary member, usually by induction on its length.

• A grammar that is too generous fails half one; a grammar that is too mean fails half two.
• A derivation step is unaffected by its surroundings, which is what lets half two wrap a derivation in extra

symbols.

Test yourself

1. Give the definition of L(G). The set of strings w over the terminals such that S derives w in zero or more steps. The string must be terminal and must come from S.

2. What are the two halves of a correctness proof, and what does each catch? That everything derivable is in the claimed set, which catches a grammar producing too much; and that everything in the claimed set is derivable, which catches a grammar producing too little.

3. Find L(G) for S->aSa | bSb | a | b. The odd length palindromes over {a, b}. Each of the first two rules adds the same symbol at both ends, and the only ways to finish leave a single a or b in the middle, so the string reads the same both ways and has odd length.

4. Is S->aS | Sb | ε a grammar for n a followed by n b? Why not? No. The two rules act independently, so nothing forces the counts to agree, and it derives a, b and aab. Its language is a star followed by b star.

5. Why is S->aSb | bSa | ε not a grammar for equal counts of a and b? Because it cannot derive baab, or abba. Every derivation places a matching pair at the two ends, so the middle must itself have equal counts, and the middle of baab is aa. Adding S->SS repairs it, since baab splits as ba followed by ab.

6. In half two of the proof for S->0S1 | ε, what justifies wrapping a whole derivation in a 0 and a 1? That a derivation step depends only on the occurrence rewritten and copies its surroundings unchanged, so adding the same symbols to both ends of every form in a derivation leaves every step legal.

Step 2. The two halves are independent: adding an a does not require adding a b.

Step 3. Two variables. A produces the a block, B produces the b block.

S->AB
A->aA | ε
B->bB | ε

Accepts: ε, a, b, ab, aab, abb, aabbb

Rejects: ba, aba, bab, abab

This language is regular, so there is a machine, and the two can be compared exactly:

a* b*

Grammar 2: n a followed by n b

Step 1. Equal numbers, all a before all b.

Step 2. The recursion is the difference from grammar 1: a longer string is obtained by adding an a at the front and a b at the back, together. Shortest string: epsilon.

Step 3. One variable does, because the two additions happen in one rule.

S->aSb | ε

Accepts: ε, ab, aabb, aaabbb

Rejects: a, b, ba, aab, abb, abab

Compare D1 and D2 as written: one extra variable in D1 and one fewer in D2, and that is the whole difference between a regular language and one that is not.

Grammar 3: equal numbers of a and b, in any order

Step 1. The counts agree; the order does not matter. So ab, ba, abba, baab, aabb are all in.

Step 2. Two recursions, and this is the case chapter 24 got wrong first. A longer string is obtained either by wrapping a shorter one in a matching pair, which gives aSb and bSa, or by placing two shorter strings of the language side by side, which gives SS. The third is not optional: without it baab cannot be made.

S->aSb | bSa | SS | ε

Accepts: ε, ab, ba, baab, abba, aabb, abab, aabbab

Rejects: a, b, aab, abb, aba, aaabb

The grammar is ambiguous, and that is a genuine cost of the SS rule which chapter 44 discusses. For a grammar that is asked to generate a language and nothing more, ambiguity is permitted.

Grammar 4: palindromes over {a, b}

Step 1. A string equal to its own reversal.

Step 2. A longer palindrome is a shorter one with the same symbol added at both ends. The shortest ones are epsilon, a and b, and all three are needed: epsilon and the two single symbols, because a palindrome may have odd or even length.

S->aSa | bSb | a | b | ε

Accepts: ε, a, b, aa, aba, abba, ababa

Rejects: ab, ba, aab, abb, aabb

The three terminating rules are what makes this right. Dropping epsilon loses the even length palindromes; dropping a and b loses the odd length ones; and a student who writes only S->aSa | bSb | ε generates only the even ones.

Grammar 5: strings over {0, 1} with an odd number of 1

Step 1. The count of 1 is odd; the 0 are unrestricted.

Step 2 and 3. This is a counting language, so read it as a machine and copy the machine: one variable per condition. E means an even number of 1 produced so far, O means odd. Producing a 0 does not switch; producing a 1 does. Only O can finish, because only an odd count is wanted.

S->E
E->0E | 1O
O->0O | 1E | ε

Accepts: 1, 01, 10, 111, 0100, 1011

Rejects: ε, 0, 00, 11, 0101, 1111

This language is regular, and the machine for it is:

Accepts: 1, 01, 10, 111, 0100, 1011

Rejects: ε, 0, 00, 11, 0101, 1111

Two variables, two states, and the productions are the transitions. That correspondence is the subject of chapter 30, and it means that any language you can build a machine for you can build a grammar for mechanically, by copying the table.

Grammar 6: strings over {a, b} containing the substring abb

Step 1. Anything, then abb, then anything.

Step 2 and 3. Three parts, and the middle is fixed. A variable for "anything" serves both ends.

S->XabbX
X->aX | bX | ε

Accepts: abb, aabb, abba, babba, abbabb

Rejects: ε, ab, ba, aab, bab, abab

(a + b)* a b b (a + b)*

Note how the fixed middle is simply written out as terminals inside a production. There is no need for a variable for something that does not vary.

Grammar 7: a to the n b to the n c to the m, with n and m independent

Step 1. A matched a and b block, then an unrelated number of c.

Step 2 and 3. Two independent parts, so a variable each, and the first part is grammar 2.

S->AC
A->aAb | ε
C->cC | ε

Accepts: ε, ab, c, abc, aabbc, abcc, aabbccc

Rejects: a, b, ba, ac, abbc, cab

The lesson of this one is the word independent in step 3. Putting the c inside the recursive rule, as in A->aAbc, would tie the count of c to the count of a, which is a different language and one no machine in this book's Module 1 or Module 2 can accept without a linear bounded automaton.

Grammar 8: the strings over {a, b} of even length

Step 1. Length divisible by 2.

Step 2. Add two symbols at a time. There are four ways to add two symbols, and all four are needed.

S->aaS | abS | baS | bbS | ε

Accepts: ε, aa, ab, ba, bb, aabb, abab

Rejects: a, b, aab, aba, abb, ababa

((a + b)(a + b))*

A neater grammar for the same language is S->TTS | ε with T->a | b, which has two variables and two rules and says the same thing. Both are correct; the second scales better if the alphabet grows.

The three ways a grammar goes wrong

Each of these is worth recognising by its symptom.

It derives nothing at all. Some variable has no terminating production, so every derivation from S gets stuck with a variable it cannot remove. Symptom: the language is empty, and everything you try fails. Check step 4.

It derives too much. A rule adds symbols independently where they should be tied. Symptom: an example you did not intend is accepted. Chapter 24's C4 is this.

It derives too little. A way of building a string of the language has no rule. Symptom: an example you did intend is rejected. Chapter 24's C2 is this, and the SS rule is what repairs it.

Distinctions

What it does NOT mean

More variables is not safer. Each one needs a meaning and a terminating rule, and an extra variable is an extra thing to get wrong.

A grammar need not be unambiguous. Unless the question asks for one, ambiguity is allowed. Chapter 44 is where it matters.

A grammar for a regular language need not be regular in form. D9 above is context free in form though its language is regular. Chapter 30 is about when the form can be restricted.

Writing down the recursion is not the same as writing down examples. Examples are step 1 evidence. The recursion is the answer.

Quick revision

• Four steps: say what the strings look like; find how a longer one is built from a shorter one and what the

shortest are; give each recurring part a variable with its meaning written down; and give every variable a terminating production.

• Four shapes: any number of something (A->xA, A->ε); two counts that match (S->xSy, S->ε); independent parts

(S->AB); a choice of forms (alternatives).

• Matched counts need the additions in ONE rule. Independent parts need separate variables.
• Equal counts in any order need three recursive rules, including S->SS, or baab is unreachable.
• Palindromes need all three terminating rules: epsilon for even length, a and b for odd.
• A counting language can be written by copying a machine: one variable per state, one production per

transition, an epsilon rule on each final state.

• Three failure modes: derives nothing (a missing terminating rule), too much (counts not tied), too little (a

missing way of building).

Test yourself

1. Write a grammar for the strings over {a, b} that begin and end with the same symbol, of length at least two. S->aAa | bAb, A->aA | bA | ε. The outer rule fixes the two ends to agree and A supplies anything in between, including nothing, so the shortest strings are aa and bb.

2. Write a grammar for a to the n b to the 2n. S->aSbb | ε. Each step adds one a and two b, so the b count is always twice the a count.

3. Why does S->aSb | bSa | ε fail for equal counts of a and b, and what repairs it? Because every derivation wraps a matching pair around a shorter string of the language, so the middle must itself have equal counts; baab would need aa in the middle. Adding S->SS repairs it, since baab splits into ba and ab.

4. Write a grammar for the strings over {a, b} of odd length. S->TTS | T with T->a | b. The T at the end supplies the odd symbol and TT adds symbols in pairs. Equivalently S->aS' | bS' with the pair rule written out, but the two variable form is shorter.

5. What goes wrong with A->aAb, with no other rule for A? Nothing can terminate, because every production of A contains A, so no derivation ever removes the variable and the language is empty.

6. Give a grammar for the strings over {0, 1} whose length is a multiple of 3. S->TTTS | ε with T->0 | 1. Three symbols are added at a time and the epsilon rule finishes, so every string has length divisible by 3.

Machine: the linear bounded automaton, chapter 60. Languages: the context sensitive languages.

S->aSBc | abc
cB->Bc
bB->bb

Accepts: abc, aabbcc, aaabbbccc

Rejects: ε, a, ab, abcc, aabc, aabbc

Check the rule on each production. S to aSBc: one symbol becomes four, so not shortening. S to abc: one becomes three. cB to Bc: two become two. bB to bb: two become two. So E1 is type 1. And it generates a to the n, b to the n, c to the n, which chapter 50 proves is not context free, so this grammar could not have been written as a type 2 one.

Type 2: context free

The rule. Every left hand side is exactly one variable. The right hand side is anything at all, including epsilon.

The name says why: the rule A to gamma applies to any occurrence of A, whatever is around it. The context is irrelevant.

Machine: the pushdown automaton, chapter 52. Languages: the context free languages.

S->aSb | ε

Accepts: ε, ab, aabb, aaabbb

Rejects: a, b, ba, aab, abab

One variable on the left of each production, so type 2.

Note that a type 2 grammar with an epsilon rule on a variable other than S is not type 1, because that production shortens. So type 2 is not literally a subset of type 1 as stated; the containment is between the classes of languages, and every context free language does have a type 1 grammar once the epsilon productions are removed by chapter 46's method. That subtlety is worth a sentence in an answer.

Type 3: regular, also called right linear

The rule. Every left hand side is a single variable, and every right hand side is one of:

• a single terminal;
• a single terminal followed by a single variable;
• epsilon.

So A to aB is allowed, A to a is allowed, A to epsilon is allowed, and A to aBc, A to Ba and A to AB are not.

Machine: the finite automaton, chapter 9. Languages: the regular languages.

S->aS | bS | aA
A->bB
B->aB | bB | ε

Accepts: ab, aba, abab, aabab, babb

Rejects: ε, a, b, ba, aa, bb

Every right hand side here is a terminal, or a terminal then one variable, or epsilon. So E3 is type 3. Read the variables as a machine's states: S means no ab has been completed yet, A means an a has just been read and is waiting for its b, and B means ab has been seen and anything may follow. Its language is regular:

(a + b)* a b (a + b)*

Chapter 30 treats the regular grammar properly, including the left linear form and why mixing the two forms escapes the class.

The four types on one page

Reading the table downward the restriction tightens, the machine weakens, and the class of languages shrinks. Reading it upward the opposite. A student who can reproduce this table has most of what MU asks on this topic.

The containments, and that they are strict

Each containment is proper: there is a language in each class that is not in the one below. That is what makes the hierarchy four things rather than one, and this book proves every step.

So each of the three witnesses is a language this book handles in full, and none of the containments is taken on trust.

Deciding which type a grammar is

The examination asks this, and the method is to check the tightest rule first and work outward.

1. Is every right hand side a terminal, a terminal and a variable, or epsilon, with a single variable on the left? Then type 3.
2. Otherwise, is every left hand side a single variable? Then type 2.
3. Otherwise, does every production have a right hand side at least as long as its left? Then type 1.
4. Otherwise type 0.

A grammar is always classified by the tightest type it satisfies, because the types are nested. A type 3 grammar is also type 2 and also type 0, and calling it type 0 is not wrong but answers nothing.

Worked

The third row is the one that catches people: S->Sa is not type 3. The right hand side must be a terminal first. A grammar all of whose right hand sides are a variable then a terminal is called left linear and generates a regular language too, but a grammar mixing the two forms generally does not, and chapter 30 is where that is settled.

Where the classification came from

Chomsky was not classifying computer languages. He was asking which mathematical models could describe human language, and his "Three Models for the Description of Language" proposes three, in increasing power, and argues that the weakest is not adequate for English. The hierarchy that carries his name came out of that work and was taken up by computer science afterwards, which is why its vocabulary is linguistic: sentence, grammar, derivation, ambiguity.

The fourth type and the machine correspondences were filled in over the following decade by others, and the linear bounded automaton of chapter 60 is the latest of the four to have been matched to its grammar.

Distinctions

What it does NOT mean

Type 0 is not "no rules". The left hand side must still contain a variable. A production of terminals only could never be applied usefully.

Context sensitive does not mean the rules look at context. It means no production shortens the string. The context formulation is equivalent, and the length one is what you check.

Context free does not mean easy. The class contains languages no finite automaton can manage, and equality of two context free languages is undecidable, which chapter 77 proves.

A grammar is not "type 2 or type 3". It is classified by the tightest type it satisfies. Every type 3 grammar is also type 2, and saying so adds nothing.

The hierarchy is about grammars, and the containments are about languages. A regular language has a type 3 grammar and also has type 2, 1 and 0 grammars. What makes it regular is that a type 3 grammar for it exists.

Quick revision

• Type 0, unrestricted or phrase structure: alpha holds a variable, nothing more. Turing machine. Recursively

enumerable languages.

• Type 1, context sensitive: beta at least as long as alpha, with S to epsilon allowed. Linear bounded

automaton.

• Type 2, context free: alpha is a single variable. Pushdown automaton.
• Type 3, regular or right linear: alpha is a single variable, beta is a terminal, a terminal then a variable,

or epsilon. Finite automaton.

• The containments are proper, with witnesses a to the n b to the n, then a to the n b to the n c to the n,

then the halting language.

• Classify by the tightest rule satisfied: check type 3, then 2, then 1, else 0.
• S->Sa is left linear, not type 3, because a right hand side must begin with a terminal.
• Tightening the restriction loses expressive power and gains decidability, which is the whole point.

Test yourself

1. Give the restriction defining each of the four types. Type 0: the left hand side contains a variable. Type 1: the right hand side is at least as long as the left, with S to epsilon permitted. Type 2: the left hand side is a single variable. Type 3: as type 2, and the right hand side is a terminal, a terminal followed by one variable, or epsilon.

2. Classify S->aSa | bSb | ε. Type 2. Each left hand side is a single variable, so not type 0 or 1 is needed; but aSa is not a terminal followed by a single variable, so it is not type 3. Note also that the epsilon rule on S is permitted in type 1 only because S appears on no right hand side, and here it does, so this grammar is not type 1 as written.

3. Classify aB->Ba, B->b, S->aB. Type 1. The first production has a two symbol left hand side, so it is not type 2; and nothing shortens, since aB to Ba is two symbols to two.

4. Name a language in each of the three gaps between the four classes. a to the n b to the n is context free and not regular. a to the n b to the n c to the n is context sensitive and not context free. The halting language is recursively enumerable and not context sensitive.

5. Why is S->Sa | b not type 3? Because a type 3 right hand side must be a terminal, or a terminal followed by a variable, or epsilon. Sa begins with a variable, so the grammar is left linear rather than right linear, and left linear grammars are not type 3 by the standard definition even though they generate regular languages.

6. What is gained by restricting a grammar, and what is lost? Decidability is gained: emptiness is decidable for context free languages and not for context sensitive ones, and membership is decidable for context sensitive languages and not for type 0. Expressive power is lost, since each class is strictly smaller than the one above it.

The two theorems worth knowing

These are proved properly in chapter 70. They are stated here because they are the form the examination asks for, and because the first one explains the second.

Theorem 1. Every recursive set is recursively enumerable.

Immediate: a machine that always halts with an answer is in particular a machine that accepts exactly the members, so the definition of recursively enumerable is satisfied without changing anything.

Theorem 2. A set is recursive if and only if both it and its complement are recursively enumerable.

The forward half is easy: if the set is recursive, swap the accept and reject outcomes of its machine and the complement is recursive too, hence recursively enumerable by theorem 1.

The backward half is the useful one and the construction is worth remembering. Suppose L has a machine M and the complement of L has a machine N, each accepting its own set and possibly running for ever otherwise. Build a machine that runs M and N side by side, one step of each in turn. Any input is in L or in the complement of L, so one of the two must accept eventually. If M accepts, accept. If N accepts, reject. So the combined machine always halts with the right answer, and L is recursive.

Running two machines in turn rather than one after the other is the whole trick, and it has a name: dovetailing. It matters because running M to completion first is exactly what does not work, since M may never finish.

The consequence that gets examined. If L is recursively enumerable and its complement is not, then L is not recursive. That is how chapter 75 shows a second problem undecidable once the first has been done, and it is why the complement is worth asking about at all.

Which class each type of grammar lands in

This is the connection to chapter 26 and the reason MU puts the label here.

So the top of the Chomsky hierarchy is exactly the recursively enumerable sets, and the three lower classes are all recursive. The recursive sets sit strictly between the context sensitive and the recursively enumerable ones: every context sensitive language is recursive, not every recursive language is context sensitive, and not every recursively enumerable language is recursive.

That gives a five level picture rather than the four of chapter 26, and it is worth drawing once:

with every containment proper.

A worked example of the difference

The example is a problem rather than a machine, because the machines are Module 2's.

A recursive set. The set of strings over {a, b} with equally many a and b. Given a string, count the a, count the b, compare. That procedure always finishes, in one pass, so the set is recursive.

A recursively enumerable set that is not recursive. The set of pairs consisting of a program and an input on which that program eventually stops. A machine can enumerate this set: run every program on every input a few steps at a time, dovetailing as above, and print each pair as soon as its program stops. Every pair where the program does stop is printed eventually. But no machine can decide the set, because deciding it would require saying no for a program that has not stopped yet and never will, and chapter 74 proves that impossible.

So the difference between the two definitions is the difference between a program you can wait on and a question you can answer.

Enumerating in order, which is a third notion

Worth knowing because it explains the word enumerable and because it makes theorem 2 obvious.

A recursively enumerable set can be listed in some order. A set that can be listed in increasing order, by length and then alphabetically, turns out to be exactly a recursive set. The reason is short: to decide whether w is in the set, list the set in order until you reach w or pass it. If the set is listed in order you must eventually do one or the other, so the procedure halts. And conversely a recursive set can be listed in order by testing every string in canonical order and printing the ones that pass.

So the three notions line up:

Distinctions