# Perfect Hash Families (a brief overview)

My research deals with Perfect Hash Families, and this article will deal with some of the background in (possible) future posts that I make. No background is strictly necessary for this post other than general mathematical knowledge.

A perfect hash family (PHF) is a 4-tuple ${(N; k, v, t)}$ which is a set of ${N}$ functions ${f : X \rightarrow Y}$ with ${|X| = k}$ and ${|Y| = v}$, such that for any ${t}$-subset ${C}$ of this set, there is at least one function ${g}$ such that ${g}$ restricted to ${C}$ is one-to-one. In matrix form, this represents an ${N \times k}$ matrix over ${v}$ symbols such that for any ${t}$ columns, there is at least 1 row among these columns that has all distinct entries.

If for a given set of ${t}$ columns we have such a condition (i.e., one row is all distinct), then we say that these columns are covering. Also, we say the PHF is covering if all ${t}$-subsets of columns are covering.

We want to find the smallest possible PHF for the given parameters, in terms of the number of rows. We denote this question (the smallest number of rows) by ${PHFN(k, v, t)}$.

These objects were introduced by Mehlhorn in 1984 for fast retrieval of frequently used information. Currently, they are used in the construction of Covering Arrays as well as in combinatorial cryptography.

Theorem 1 ${PHFN(k, v, t) = 1}$ if ${k = t}$, and ${\ge 2}$ otherwise.

Proof: If ${k=t}$, the array consists of 1 row of all distinct symbols. If ${k > t}$ and there is only 1 row, then there must be one set of ${t}$ columns with a duplicate entry. $\Box$

Theorem 2 ${PHFN(k, v, 2) = \lceil \frac{\log(k)}{\log(v)} \rceil}$.

Proof: If ${t=2}$, then the PHF covers if and only if every pair of columns is different. Therefore, we can list columns containing ${v}$ symbols. If each is of length ${N}$, then we have ${v^N = k}$ different columns, and solving for ${N}$ gives the desired result. $\Box$

Theorem 3 (Symbol Increase) ${PHFN(k, v+d, t) \le PHFN(k, v, t)}$ for any ${d \ge 1}$.

Proof: Increasing the number of symbols does not change whether or not the PHF covers. $\Box$

Theorem 4 (Column Decrease) ${PHFN(k-d, v, t) \le PHFN(k, v, t)}$ for any ${d \ge 1}$.

Proof: Removing columns does not change whether or not the PHF covers. $\Box$

Theorem 5 ${PHFN(k+d, v+d, t) \le PHFN(k, v, t)}$ for any ${d \ge 1}$.

Proof: Add ${d}$ new columns to the PHF, each one consisting entirely of a new symbol. The PHF certainly remains covering on any of the previous ${k}$ columns, and covers when involving any of the ${d}$ new columns because they introduce new symbols. $\Box$

1. Recursive Constructions

The power in generating large combinatorial objects lies in being able to create them using smaller “ingredients” – we describe a few of them here. The first two lead to the best bounds, in general, for very large PHFs.

Theorem 6 (Blackburn Composition) ${PHFN(k, v, t) \le PHFN(k, x, t) \times PHFN(x, v, t)}$.

Proof: Call the first PHF ${A}$, and the other ${B}$. Replace all occurrences of the ${i}$th symbol of ${A}$ with the ${i}$th column of ${B}$ to form ${C}$. ${C}$ has the required size, but why is it a PHF? Select any ${t}$ columns of ${C}$. In ${A}$ with the same columns, at least 1 row contains distinct values. In ${C}$, that row includes distinct columns of ${B}$. Since ${B}$ was a PHF, at least 1 row in ${C}$ must contain distinct columns. Therefore, ${C}$ is a PHF. $\Box$

Theorem 7 (Atici-Magliveras-Stinson-Wei Product)

$\displaystyle PHFN(k_0 k_2, v, t) \le PHFN(k_0 k_1, v, t) \times PHFN(k_2, k_1, t-1) + PHFN(k_2, v, t).$

Theorem 8 (Martirosyan Row Decrease)

$\displaystyle PHFN(\lceil \frac{k(t-1)}{v} \rceil, v, t) \le PHFN(k, v, t)-1.$

Proof: Let ${A}$ be the PHF where we want to remove a row. Pick any row ${j}$. Denote ${x_i}$ to be the number of times symbol ${i}$ appears in row ${j}$. Without loss of generality, suppose ${x_0}$ is the largest over all symbols, and ${x_{v-1}}$ is the least (ordered in the usual way).

Delete all columns of ${A}$ that have symbols ${x_{t-1}, x_t, \cdots, x_{v-1}}$ in row ${j}$. Now remove row ${j}$ completely. We get an ${(N-1) \times k'}$ array ${C}$ (with potentially fewer symbols, but this is not guaranteed). However, we can guarantee ${C}$ is a PHF of strength ${t}$.

What is the value of ${k'}$? Since ${x_0 \ge \cdots x_{v-1}}$ we have that:

$\displaystyle \sum_{i=0}^{v-1} x_i \le v \frac{\sum_{i=0}^{t-2} x_i}{t-1}$

. Therefore, ${k' \ge \frac{k(t-1)}{v}}$, and the result is proved. $\Box$

2. Probabilistic Constructions

The previous section discusses actually making a PHF, but here we take a different approach: we see that a PHF of given parameters must exist, but the proofs are nonconstructive (unfortunately).

Let ${A}$ be a random ${N \times k}$ array over ${v}$ symbols. Choose a set of ${t}$ columns ${C}$. What is the probability that ${C}$ is not covered? It is the probability that no rows in ${C}$ have all distinct entries. What is the probability that a given row is all distinct? This probability is

$\displaystyle \frac{v(v-1)(v-2)\cdots(v-t+1)}{v^t}.$

Let this probability be ${p}$. Therefore, the probability that a given row is not all distinct is ${1-p}$, and the probability that all rows are not distinct is ${(1-p)^N}$.

So what is the expected number of ${t}$-sets of columns that are not covering? By union bound, we know that since there are ${{k \choose t}}$ columns, that this expected number is

$\displaystyle {k \choose t}(1-p)^N.$

All we need to do is to solve for ${N}$ when this number is strictly less than 1. If we do, then we guarantee that there must be some PHF with those parameters. Taking logarithms, and upper bounds, we have that:

Theorem 9 ${PHFN(k, v, t) \le \frac{t( \log(k) - \log(t) + 1))}{t\log(v) - \log(v^t-t!{v \choose t})}}$.

Deng, Stinson, and Wei showed an improved bound using the Lovász Local Lemma:

Theorem 10 ${PHFN(k, v, t) \le \frac{\log({k \choose t} - {{k-t} \choose t})+1}{t\log(v) - \log(v^t - t! {v \choose t})}}$.

Stinson, van Trung, and Wei improved on this (called “expurgation”):

Theorem 11 ${PHFN(k, v, t) \le \frac{\log{2k \choose t} - \log(k)}{t\log(v) - \log(v^t-t!{v \choose t}))}}$.

Note that improvements are only in the numerator in all cases.

# Perfect Hash Family Tables

Perfect Hash Families are very extensive in combinatorial design theory literature, and have many applications to secure frame proof codes, to lookup of frequently used information, and even to my own research! There is a list of the “smallest” PHFs, located here, but has not been updated since 2006.

I am in the process of creating a “new” set of tables, not only taking into account constructions of mine (as in the last post), but also those that were published since 2006 (and there are many).

Here is a sneak peek!

# New Bounds for Covering Arrays of Strength 7

Happy Halloween!

I want to share some cool results of a project I’m working on in one of my classes. A covering array is a 4-tuple ${CA(N; t, k, v)}$ which is an ${N \times k}$ array, each entry is from an alphabet of size ${v}$, and for every ${t}$ of the ${k}$ columns, all ${t}$-tuples over ${v}$ exists in at least one row when restricted to these columns. The covering array number, ${CAN(t, k, v)}$, is the smallest ${N}$ for which a ${CA(N; t, k, v)}$ exists. Kleitman and Spencer, and Katona independently, found ${CAN(2, k, 2)}$ for all ${k}$; no other cases are known for all ${k}$, and only heuristics are known. My advisor keeps the best-known covering array numbers here.

I was able to show the following:

1. ${CAN(7, 10, 3) \le 4371 (-2184)}$,
2. ${CAN(7, 11, 3) \le 6555 (-2184)}$,
3. ${CAN(7, 13, 3) \le 9225 (-1698)}$,
4. ${CAN(7, 14, 3) \le 10923 (-2184)}$,
5. ${CAN(7, 15, 3) \le 13107 (-2184)}$,
6. ${CAN(7, 17, 5) \le 312485 (-78120)}$.

The numbers in parentheses are the row reductions from previous known bounds. I won’t share how I did this yet, but it is a cool computational technique that works very well for high ${t}$!

# Theory of Computation – Lecture 1: Regular Languages

This is the first post of a series of lecture notes about a topic called “Theory of Computation.” This post (and lecture series) assumes that the reader is familiar with the following topics:

• Sets
• Functions
• Relations
• Formal proofs (especially proof by contradiction).

We will introduce sections from these topics here that are necessary to understand most of these lecture notes. A set is a collection of items that are unique (Note: I won’t delve into the notions of set theory, just yet…), usually written with curly braces and separated by commas. An example of a set is ${\{1, 2, 3\}}$: all items in the set are unique. We can have nested sets within sets, such as ${\{1, \{2\}, \{3\}\}}$. The empty set, written ${\emptyset}$, is the unique set that contains zero items. We say that ${x}$ belongs to (or is a member of) a set ${A}$, written ${x \in A}$, if ${x}$ is a member of ${A}$. Likewise, we say that ${x}$ is not a member of a set ${A}$, written ${x \notin A}$, if ${x}$ is not a member of ${A}$. We write the cardinality of a set ${A}$ as ${|A|}$, and is the number of elements in ${A}$. For most of these lecture notes, we will only work with finite sets.

We say that ${X}$ is a subset of a set ${A}$, written ${X \subseteq A}$, if every element in ${X}$ is a member of ${A}$. The powerset of a set ${A}$, written ${\mathcal{P}(A)}$, is the collection of all possible subsets of ${A}$. For example, if ${A = \{1, 2, 3\}}$, then ${\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}}$. The union of two sets ${A}$ and ${B}$, written ${A \cup B}$, is the set that contains all elements from ${A}$ or ${B}$ (removing duplicates of course). The intersection of two sets ${A}$ and ${B}$, written ${A \cap B}$, is the set that contains all elements that are both in ${A}$ and ${B}$. The set difference (or set minus) of two sets ${A}$ and ${B}$, written ${A \setminus B}$ is the set that contains all elements that are in ${A}$ but not in ${B}$.

Exercise 1 Show that for any finite set ${A}$ with ${n}$ elements, ${\mathcal{P}(A)}$ has ${2^n}$ elements.

A tuple is a sequence of items, not necessarily unique, usually written between two parentheses and separated by commas. An example is ${(1, 2, 3, 1)}$. A ${t}$-tuple is a tuple that has ${t}$ items. The Cartesian product (or just product) of two sets ${A}$ and ${B}$, written ${A \times B}$, is the set of all 2-tuples with the first coordinate being a member of ${A}$, and the second from ${B}$.

A function takes an element of a given set (called the domain), and outputs a member of another set (called the range). If ${f}$ is a function and ${A}$ is its domain, ${B}$ its range, we write the function formally as ${f : A \rightarrow B}$. In other words, for some ${a \in A}$, ${f(a) \in B}$ (there may be some ${a \in A}$ that are not defined). If every element ${a \in A}$ has a defined ${f(a) \in B}$, then we call ${f}$ a total function.

An alphabet ${\Sigma}$ is a finite set of characters (just another name for the elements of ${\Sigma}$). A string is a finite sequence of characters over ${\Sigma}$. If ${\Sigma = \{0, 1, 2\}}$, then an example string is ${0111222012210}$ (technically, we should be writing strings in the tuple format, but we will largely ignore that for strings). The set ${\Sigma^\star}$ (called ${\Sigma}$ “star”) is the set of all strings over ${\Sigma}$. The empty string, ${\epsilon}$, is the unique string that has length 0. A language ${L}$ is a subset of ${\Sigma^\star}$, and can be described as some “set of strings over ${\Sigma}$.” The complement of a language ${A}$, ${\overline{A}}$ is the set of all strings in ${\Sigma^\star}$ that are not in ${A}$.

1. Introduction

Computer Science is largely the field based off of being able to understand what “computation” really means (hence the name). We will approach this by looking at several basic questions, which will turn out to be very deep and are very non-trivial in general:

• What does it “mean” to “compute” something?
• How do we measure (or could we even measure) how many resources a certain computation uses?
• And relating to the last question, what kinds of resources do we care about?
• How can we compare two computations to certify if one is better than another?
• Is there a way to formally define a “computer” so that we can ask basic questions about how they compute something?

Of course, at a first glance one may run into trouble as to how to formally define (or model) a “computer.” Since there are many types of computers available to buy, does one actually compute differently than another? Of course, with different configurations of the hardware and software, we can certainly see that some computations are faster or more efficient in some manner; for example, a process in one operating system only takes 2 GB of memory to run, whereas a ported version in another takes 3 GB.

But this is not the central question we are after, for multiple reasons:

1. It seems difficult to characterize what “fast” computation actually means.
2. We may run into the situation where some computer model actually computes some function (let’s say) faster (or more efficiently) on some inputs, and slower (or less efficiently) on other inputs.
3. For some models, we may not worry about minute differences in computation efficiency between the two models; for instance, if the two models described above used 2 GB and 2.01 GB respectively, then we may not worry about this tiny difference.

We want, instead, to characterize what a computer can do, instead of what are the means it does to perform the computation. Now, let’s discuss what, at a high-level, a computer “needs” to perform a computation.

First, there usually is some input that is encoded in some form. In most computers, the input is given in binary (i.e., consisting entirely of 0s and 1s). There may be many input devices, such as a keyboard, mouse, etc. However, we will abstract this by calling all of them “1 device.”

Exercise 2 Given ${n}$ strings, give a method to produce 1 string that contains all of the information of the ${n}$ strings that makes each bit of each string “efficiently recoverable.” What is the bound on the number of bits that you get?

Next, there is a CPU (Central Processing Unit): the basic part of a computer that takes some input (code, data, etc.), and performs some operation depending on what was given to it. Naturally, there are many possible instructions that a CPU may receive, such as add two numbers, store this value, etc. To simplify everything, we will consider the entire contents of memory of the computer as a state. Since most computers store values as binary, we can think of the entire contents of memory as a single integer. We will think about transitions between states as what the CPU does to change (or possibly not) the contents of memory.

Like the input, there is usually some output that is the result of multiple iterations of code/data/etc. entering and then leaving the CPU, also encoded in some form. As before, we will assume that there is exactly one output for simplicity. But even deciding what is the “right” type of output can be cumbersome. So we overcome this by making the “output” be a binary “flag” of sorts: either a “yes” or a “no.”

And finally, there is some kind of secondary storage that will be where “long-term” code/data/etc. is stored. However, for simplicity, we will defer this part to a future section. The reason for this is that actually having some storage like this drastically changes the computational power of the model.

2. DFAs

Following the argument above, we need to introduce a machine model for “solving” a problem or “computing” something. We want this machine to be as deterministic as possible in order to make analyzing it easier.

Definition 1 A DFA (Deterministic Finite Automaton) is a 5-tuple ${(Q, \Sigma, \delta, q_0, F)}$ where ${Q}$ is a finite set of states, ${q_0 \in Q}$ is the start state, ${F \subseteq Q}$ is the set of final states, ${\Sigma}$ is a finite set called the alphabet, and ${\delta: Q \times \Sigma \rightarrow Q}$ is a total function called the transition function.

DFAs are sometimes drawn (also called “embedded into the plane”). Conventionally, the start state has an arrow coming from nowhere to the start state, each state is a circle, final states are double circles, and transitions are drawn as arrows between states with the label from ${\Sigma}$ on the transition. Given an input ${w}$ consisting of characters, we start in the start state, and progressively read characters off of ${w}$ and transitioning between states according to ${\delta}$ until we cannot read any other characters; in this case, we say that the machine accepts ${w}$ if we land in one of the final states.

Example 1 Here is an example of a DFA that accepts all strings that consist of an odd number of 0’s and an even number of 1’s, or an even number of 0’s and an odd number of 1’s.

Exercise 3 For the DFA above, what are each of the 5 pieces defined to be?

Exercise 4 Create a DFA that accepts the same strings as Example 1 but with only 2 states.

Indeed, we can talk about DFAs as being very “simple” computers, in that they are not only deterministic, but they are also fully specified from construction, and have no dependency on “past history” when running on some input string. This last fact will actually be useful in characterizing the structure of regular languages. But for now, we will introduce more definitions:

Definition 2 The Kleene-closure, sometimes called Kleene star, for an alphabet ${\Sigma}$ is the set of all strings for which the symbols are from ${\Sigma}$, usually denoted ${\Sigma^\star}$.

Example 2 If ${\Sigma = \{0, 1\}}$, then ${\Sigma^\star}$ consists of all possible binary sequences.

Example 3 Here is a DFA that accepts all strings in ${\{0, 1\}^\star}$ that contain 3 or more sequential 0’s.

We want to look at a particular string, say ${w = 101000110}$, and how it is accepted by this machine. We start off in ${q_0}$, then read the first character of ${w}$, which is a 1. We stay in ${q_0}$, and by reading a 0, we transition to ${q_1}$. We keep reading through the string until we reach the last character, which is a 0. At this point, we have reached ${q_3}$, and so we take the self-loop on ${q_3}$. Since there are no other characters left, we accept this string. Now we will make this more general for an arbitrary DFA and arbitrary string.

Definition 3 Let ${M = (Q, \Sigma, \delta, q_0, F)}$ be a DFA, and ${w \in \Sigma^\star}$ with ${n}$ characters denoted as ${w_1w_2 \cdots w_n}$, with each ${w_i \in \Sigma}$. We define a computation of ${M}$ on ${w}$ as the sequence ${r_0, \cdots, r_n}$ of states (with ${r_i \in Q}$) so that:

1. ${r_0 = q_0}$,
2. ${r_{i+1} = \delta(r_i, w_{i+1})}$ for all ${0 \le i < n}$.

A computation is accepting if ${r_n \in F}$.

Definition 4 The language recognized by a DFA ${M}$, written ${L(M)}$, is the set:

${\{w \in \Sigma^\star\;|\;M}$ has an accepting computation on ${w}\}$

Definition 5 A language ${L}$ is regular if there exists a DFA ${M}$ so that ${L}$ is the language recognized by ${M}$. In other words, ${L = L(M)}$.

3. Regular Operations

Since languages are sets of strings, we want to consider the usual set operations: union, intersection, and complement. We want to show that we can apply these operations to the regular languages and still have a regular language at the end. The regular operations are: union, concatenation, and star. But to prove these, we need to prove closures of other operations first.

Definition 6 We say that regular languages are closed under an operation ${\oplus}$ if whenever ${\oplus}$ is applied to regular languages, the result is a regular language. In other words, if ${A, B}$ are regular languages, ${A \oplus B}$ is also regular.

Theorem 7 Regular languages are closed under complement.

Proof: We want to show that if ${L}$ is regular, then ${\overline{L}}$ is regular. Since ${L}$ is regular, there is a DFA ${M = (Q, \Sigma, \delta, q_0, F)}$ recognizing ${L}$. ${L}$ is also defined as the set of strings ${w \in \Sigma^\star}$ such that ${M}$ has an accepting computation on ${w}$. But this means that ${\overline{L}}$ is defined as the set of strings ${w \in \Sigma^\star}$ with ${M}$ not having an accepting computation on ${w}$; this implies the computation ends in a non-final state. So we can just make a machine ${\overline{M} = (Q, \Sigma, \delta, q_0, Q\setminus F)}$ for ${\overline{L}}$. $\Box$

Theorem 8 Regular languages are closed under union.

One idea to try to prove this is to feed the input string to the first machine, and then send it to the second machine afterwards. If either machine accepts the string, we accept; otherwise, we reject. The problem with this is that we only have one chance to read the input, and each character is consumed and cannot be returned to. Instead, we will try to remember both states of both machines as if we were simulating both simultaneously. Proof: We want to show that if ${L_1, L_2}$ are regular, then ${L_1 \cup L_2}$ is regular. Because ${L_1, L_2}$ are regular, there are DFAs ${M_i = (Q_i, \Sigma, \delta_i, q_{0, i}, F_i)}$ for ${i \in \{1, 2\}}$ accepting ${L_1, L_2}$, respectively. We create a DFA ${M = (Q, \Sigma, \delta, q_0, F)}$ to recognize ${L_1 \cup L_2}$:

• ${Q = Q_1 \times Q_2}$,
• ${q_0 = (q_{0,1}, q_{0,2})}$,
• ${F = \{(q, q')\;|\;q \in Q_1, q' \in Q_2}$, and either ${q \in F_1}$ or ${q' \in F_2}$ or both$\}$,
• ${\delta((q, q'), a) = (p_1, p_2)}$ where ${\delta_1(q, a) = p_1}$ and ${\delta_2(q', a) = p_2}$ for all ${q \in Q_1, q' \in Q_2, a \in \Sigma}$.

Intuitively, we keep a pair of states in which the first coordinate corresponds to a simulation of the first machine, and the second coordinate of the second. $\Box$

Example 4 For the following 2 DFAs:

Here is the resulting DFA ${D}$ with ${L(D)}$ being the union of the two DFAs’ languages, after performing the product construction on them:

Corollary 9 Regular languages are closed under intersection.

Proof: If ${A, B}$ are regular languages, then ${A \cap B = \overline{\overline{A} \cup \overline{B}}}$, which we know is regular from Theorems 1 and 2. $\Box$

Exercise 5 Show that regular languages are closed under symmetric difference (i.e., ${x \in A}$ or ${x \in B}$ but not both).

Now we discuss concatenation: if ${A, B}$ are regular, is ${AB}$ necessarily regular? Given a string ${w \in AB}$, we want to decompose ${w = w_1 \cdots w_n}$ such that ${w_1 \cdots w_\ell \in A}$ and ${w_{\ell +1}\cdots w_n \in B}$ for some integer ${\ell}$. But it seems to be difficult to know where to split the string: would there be a way to “guess” this index? We will generalize our model of computation to allow for “guesses.”

We in general would like a generalized version of our machine that allows for multiple selections to be made. Now the model will change depending on how a “selection” is made (uniformly at random, the first one seen, lexicographically first by state name, etc.). But here, we will use a model which involves “nondeterminism” which essentially means “picks the correct choice, if one exists.” Of course, this does not exist in the real world, because if we were able to do this, then we can solve many intractable problems much more quickly.

But the idea of “nondeterminism” is quite important when talking about later topics. One such topic is NP-completeness, which are the candidate languages that have no known polynomial-time algorithm to solve (most people believe that this is true). One definition of problems in NP uses nondeterminism, and another (equivalent) one concerns “certificates” of solutions.

4. NFAs

Definition 10 An NFA (Nondeterministic Finite Automaton) is a 5-tuple ${(Q, \Sigma, \delta, q_0, F)}$ where ${Q}$ is a finite set of states, ${q_0 \in Q}$ is the start state, ${F \subseteq Q}$ is the set of final states, ${\Sigma}$ is a finite set called the alphabet, and ${\delta: Q \times (\Sigma \cup \{\epsilon\}) \rightarrow \mathcal{P}(Q)}$ is the transition function.

Note the only difference is in the transition function: we allow not reading a character from the input alphabet, we map to a set of states instead of a single state, and the function is not total anymore. Now note that a computation on an NFA needs to be re-defined because of this.

Definition 11 Let ${M = (Q, \Sigma, \delta, q_0, F)}$ be an NFA, and ${w \in \Sigma^\star}$ with ${n}$ characters denoted as ${w_1w_2 \cdots w_n}$, with each ${w_i \in \Sigma \cup \{\epsilon\}}$. We define a computation of ${M}$ on ${w}$ as a sequence ${r_0, \cdots, r_n}$ of states (with ${r_i \in Q}$) so that:

1. ${r_0 = q_0}$,
2. ${r_{i+1} \in \delta(r_i, w_{i+1})}$ for all ${0 \le i < n}$.

A computation is accepting if ${r_n \in F}$.

There are a few differences: there may be many (accepting) sequences that give a valid computation, and the next state in the sequence is a member (not just defined as) of the set given by ${\delta(r_i, w_{i+1})}$. We define the language recognized by an NFA the same way as for a DFA, except that we only require at least one accepting computation here.

Example 5 Observe the following NFA ${M}$:

We test if ${111 \in L(M)}$. We start in ${q_0}$. Reading a 1 has us allowed to be in either state ${q_0}$ and ${q_1}$ (there is a choice). But we keep track of what states we “could” be in as it is important for later. Now, we have to see what the transition from both states on each symbol goes to (since any one of them can lead to an accepting computation); doing so puts us in states ${q_0}$, ${q_1}$. Since there is no transition out of ${q_1}$, the transition function on ${q_1}$ and 1 gives the empty set, ${\emptyset}$. After reading the last 1, we still end up in states ${q_0}$ and ${q_1}$; since neither is accepting, we have that ${111 \notin L(M)}$.

Note that “choice” here is implemented in a deterministic way as handling all possible computation paths at the same time. However, in the nondeterministic world, only one computation is ever performed, no matter how many computations on a given string actually exist.

Now we discuss the relation of DFAs to NFAs. Clearly, every DFA is an NFA, as a DFA really is an NFA without any choice or “non-reading” transitions. What is not-so-obvious is whether we can transform an NFA into an equivalent DFA. We will actually show this after some build-up; for now, we present constructions for the regular operations:

Theorem 12 If ${L_1}$ and ${L_2}$ have NFAs recognizing them, then there is an NFA recognizing ${L_1 \cup L_2}$.

Proof: Create a new non-final start state, and an ${\epsilon}$-transition from it to the original start states. Correctness details are left as an exercise for the reader. $\Box$

Theorem 13 If ${L_1}$ and ${L_2}$ have NFAs recognizing them, then there is an NFA recognizing ${L_1 L_2}$. Note: we do not say anything about regularity, since we have not proven that NFAs recognize only the regular languages yet.

Proof: Let ${M_i = (Q_i, \Sigma, \delta_i, q_{0,i}, F_i)}$ for ${i \in \{1, 2\}}$ be NFAs for ${L_1}$ and ${L_2}$. Construct an NFA ${M = (Q, \Sigma, \delta, q_0, F)}$ as follows:

• ${Q = Q_1 \cup Q_2}$,
• ${q_0 = q_{0,1}}$,
• ${F = F_2}$,
• Create an ${\epsilon}$-transition from every ${q \in F_1}$ to ${q_{0,2}}$.

Another way of saying this is that whenever we have achieved a string that is in ${L_1}$, we are in a state in ${F_1}$–we “guess” to transition over to the second machine. If we have “guessed” and at the end of reading the input have reached a state in ${F_2}$, then we accept a string; otherwise, we do not. Correctness details are left as an exercise for the reader. $\Box$

Theorem 14 If ${L_1}$ has an NFA recognizing it, then there is an NFA recognizing ${L_1^\star}$.

Proof: Create a new start state that is final, with an ${\epsilon}$-transition to the old start state. For all final states (except the newly created one), create an ${\epsilon}$-transition to the new start state. We actually could make all final states of the machine (except the new one) to be non-final, but modifying the machine as little as possible is our main goal here. Correctness details are left as an exercise for the reader. $\Box$

Now we want to show that every NFA accepts a regular language. First, we will work without ${\epsilon}$-transitions; after that, we will add them with a slightly different proof.

Theorem 15 Let ${M = (Q, \Sigma, \delta, q_0, F)}$ be an NFA without ${\epsilon}$-transitions. Then ${L(M)}$ is regular.

Proof: We create a DFA ${M' = (Q', \Sigma, \delta', q_0', F')}$ as follows:

• ${Q' = \mathcal{P}(Q)}$,
• ${q_0' = \{q_0\}}$,
• ${F' = \{X \subseteq Q : X \cap F \ne \emptyset\}}$,
• ${\delta'(S,a) = \bigcup_{s \in S} \delta(s,a)}$ for all ${S \subseteq Q, a \in \Sigma}$.

$\Box$

Now we look at NFAs with ${\epsilon}$-transitions – the above construction does not work since ${\epsilon}$-transitions are not “removed” from the resulting automaton (and DFAs cannot have them). We want to handle any arbitrarily many choices of taking an ${\epsilon}$-transition at the same time; in essence, we take the union of all possible “reachable” states that can be reached via a chain of ${\epsilon}$-transitions.

Definition 16 Let ${M = (Q, \Sigma, \delta, q_0, F)}$ be an NFA, with ${S \subseteq Q}$. The epsilon closure (sometimes written ${\epsilon}$-closure) of ${S}$, ${E(S)}$, is the smallest subset ${X \subseteq Q}$ such that:

• ${S \subseteq X}$, and
• If ${x \in X}$ and ${y \in \delta(x, \epsilon)}$, then ${y \in X}$.

Now we just slightly modify the proof above to handle ${\epsilon}$-closures instead of just taking one transition:

Theorem 17 Let ${M = (Q, \Sigma, \delta, q_0, F)}$ be an arbitrary NFA, with or without ${\epsilon}$-transitions. Then ${L(M)}$ is regular.

Proof: We create a DFA ${M' = (Q', \Sigma, \delta', q_0', F')}$ as follows:

• ${Q' = \mathcal{P}(Q)}$,
• ${q_0' = E(\{q_0\})}$,
• ${F' = \{X \subseteq Q : X \cap F \ne \emptyset\}}$,
• ${\delta'(S,a) = E(\bigcup_{s \in S} \delta(s,a))}$ for all ${S \subseteq Q, a \in \Sigma}$.

$\Box$

Exercise 6 Construct a family of NFAs ${\{N_i\}_{i \ge 1}}$ with ${n_i}$ states for NFA ${N_i}$ such that an equivalent DFA for ${N_i}$ must have at least ${2^{n_i}}$ states.

Example 6 Here is an NFA with ${\epsilon}$-transitions:

We start with state ${0}$: the ${\epsilon}$-closure of it is ${\{0, 1, 3\}}$, so we create a state called that. Then we look at all states that can be reached from ${\{0, 1, 3\}}$ via 1 transition on 0 or 1, and take their epsilon closures as necessary. We keep iterating until we either exhaust all possible states (which is ${2^6}$ in this case), or have no “branch” that can be reached. The resulting constructed DFA is below:

Exercise 7 Look at the previous NFA; instead of the “fast” construction which involves 7 states, think of the “brute-force” construction which involves 64 states. How come we could make an NFA with 7 states? What has to happen with the other 57 possible states?

5. Regular Expressions

With the DFA/NFA models that we have created, they describe a machine model for being able to individually “test” strings and accept/reject them based off of whether the state at the end of the computation is an accepting one. But, one may want to describe a particular language in a convenient form that is completely unambiguous (of course after the creation of necessary definitions!). We turn to an object called a regular expression.

Definition 18 ${R}$ is a regular expression over ${\Sigma}$ iff one of the following holds:

1. ${a \in \Sigma}$, and ${R = a}$;
2. ${R = \epsilon}$;
3. ${R = \emptyset}$;
4. ${R = (R_1 \cup R_2)}$ with ${R_1, R_2}$ being regular expressions;
5. ${R = (R_1 R_2)}$ with ${R_1, R_2}$ being regular expressions;
6. ${R = (R_1)^\star}$ with ${R_1}$ being a regular expression.

Example 7 A regular expression for all the strings that contain the substring ${aa}$ (with alphabet ${\Sigma = \{a, b\}}$) is: ${(a \cup b)^\star aa (a \cup b)^\star}$. The idea is that if there is an ${aa}$ substring, then any string can appear before and after it. If the string does not contain ${aa}$, then it won’t be matched anyway.

We show that regular expressions also describe the regular languages by showing an equivalence between them and NFAs.

Theorem 19 Every language described by a regular expression is regular.

Proof: We need to convert an arbitrary regular expression ${R}$ into an NFA. The first case involves a 2-state NFA, and the second and third describe a 1-state NFA. The last three are implied by Theorems, 3, 4, and 5. $\Box$

Theorem 20 Every regular language is described by a regular expression.

Proof: It is sufficient to convert a DFA or NFA into a regular expression. The idea is to “remove” states one-by-one, and maintain on the transitions an equivalent regular expression. However, we cannot do this as DFAs/NFAs only allow one “symbol” on the transition; therefore, we need a generalization.

Definition 21 A generalized NFA (or GNFA) is an NFA with a single start state having no incoming transition, a single final state with no outgoing transitions, and every transition is labelled with a regular expression.

Clearly, any arbitrary NFA or DFA satisfies the last requirement of GNFAs. For an arbitrary NFA, we can add a single start state with an ${\epsilon}$-transition to the old start state, and an ${\epsilon}$-transition from all previously final states to a new single final state without any outgoing transitions. Therefore, we have converted it into a GNFA.

Now we handle “ripping” out of states. Suppose we had a situation similar to the following:

where ${R, T, X}$ are regular expressions, ${q_{rip}}$ is the state that we want to remove, and ${q_i}$ and ${q_j}$ are arbitrary other states (final or non-final). Then we can remove state ${q_{rip}}$ and create a transition from ${q_i}$ to ${q_j}$ with the following regular expression:

Clearly, if we only have 2 states in the GNFA, then the resulting regular expression on the only transition is the converted regular expression. So for all states other than the new start and final states, we “rip” each state out one by one, and replace each transition that goes into and then out of that state with a regular expression.

Some details that we may need to check for:

• There may already be a transition ${q_i \rightarrow q_j}$ not shown above (where ${q_i \ne q_j}$); if this is the case and the regular expression on this transition is ${A}$, then after ripping state ${q_{rip}}$, the resulting regular expression is ${A \cup RT^\star X}$.
• If ${q_i = q_j}$, removing ${q_{rip}}$ introduces a loop.
• For completeness, for all “undefined” transitions, we create a new transition between the states as ${\emptyset}$ (but this does not affect the correctness of the algorithm).

$\Box$

Exercise 8 Let ${L}$ be a regular language. Then ${L^{rev}}$ (all ${w \in L}$ but taking their reverse instead) is also regular. (Hint: use regular expressions and the definition. This can be proved via NFAs but is a little more tricky for details. It’s even easier with regular grammars below.)

6. Regular Grammars

We now have two formalisms to describe the regular languages: a machine model, and a tool to describe the language in terms of the three regular operations. But what if instead of matching against a particular string to check whether or not it is in the language, we wanted to show that it can be generated in some way? (Regular) grammars will help us do this. Because of this, we will have an increasingly large collection of ways to describe these “simple” languages.

Definition 22 A regular grammar is a 4-tuple ${(V, \Sigma, R, S)}$ where:

• ${V}$ is a finite set of variables,
• ${S \in V}$ is the start variable,
• ${\Sigma}$ is a finite set of terminals, and
• ${R}$ is a finite set of rules, of the form: ${X \rightarrow Y, X \rightarrow aY, X \rightarrow a, X \rightarrow \epsilon}$. with ${X,Y \in V, a \in \Sigma}$.

Example 8 Here is an example of a regular grammar:

$S \rightarrow 0S$

$S \rightarrow T$

$T \rightarrow 1T\;|\;\epsilon.$

This has ${\Sigma = \{0, 1\}, V = \{S, T\}}$. Let’s see if the string 00011 is in the grammar. We have to start with ${S}$, and we could choose either to replace ${S}$ with ${0S}$, or with ${T}$. But a quick glance at ${T}$‘s rules show that none will help us derive the string, so we replace ${S}$ with ${0S}$. Then we keep iterating until we do, in fact, derive 00011.

Definition 23 We say that a particular derived string ${X}$ derives another string ${X'}$ if ${X}$ is of the form ${uAv}$, ${X'}$ is of the form ${uxv}$, and ${A \rightarrow x}$ is a rule. If there is a sequence of derivations ${S \rightarrow w_1 \rightarrow \cdots \rightarrow w_m}$ and ${w_m \in \Sigma^\star}$, then ${w_m}$ is in the language of the grammar (often denoted ${S \rightarrow^\star w_m}$).

Implied by the name, we show that regular grammars recognize the regular languages.

Theorem 24 Let ${L}$ be an arbitrary regular language. Then there is a regular grammar ${G}$ with ${L = L(G)}$.

Proof: Since ${L}$ is regular, let ${D}$ be a DFA recognizing ${L}$. The construction is as follows. Make 1 variable for each state, the start variable is the start state, the terminals are the input alphabet. For transitions, if ${\delta(q, a) = p}$, then add the rule ${q \rightarrow ap}$; if ${q}$ is a final state, add a rule ${q \rightarrow \epsilon}$. $\Box$

Theorem 25 Let ${G}$ be an arbitrary regular grammar. Then ${L(G)}$ is regular.

Proof: The construction is essentially a reverse proof of the last theorem, iterating over all the rules:

• For ${A \rightarrow aB}$, make a transition from state ${A}$ to state ${B}$ on symbol ${a}$.
• For ${A \rightarrow B}$, add an ${\epsilon}$-transition from state ${A}$ to state ${B}$.
• For ${A \rightarrow a}$, make a single final state ${S}$ (shared among all variables) with a transition from state ${A}$ to it on symbol ${a}$.
• For ${A \rightarrow \epsilon}$, make ${A}$ a final state.

$\Box$

7. Non-Regular Languages

We have shown regularity properties for many languages, so it seems not that possible that there are non-regular languages. Suppose we wanted to have a pattern matcher that “counted” numbers of two characters in a string:

${\{w : }$ the number of 0’s in ${w}$ is equal to the number of 1’s in ${w}\}$

Exercise 9 Try designing a DFA/NFA/regular expression for this language. It will turn out to be impossible, but what are the difficulties you run into?

Let’s suppose that there were a non-regular language (we haven’t proven any exist, but let’s assume). Then if we suppose that this actually non-regular language is in fact regular, then we can design a DFA for it; if we can prove that there is a contradiction somewhere, then we can prove that no DFA can in fact exist for it, implying that the language is not regular.

Now look at an arbitrary language; it either is finite or infinite.

Exercise 10 Show that every finite language is regular.

If it is infinite, it may or may not be regular. If it is, then it has a specific property: for any ${w \in \Sigma^\star}$ that we run on the DFA for it (for a long-enough ${w}$), there is a state that will be repeated in the computation steps. The “long-enough” criterion is satisfied if ${|w|}$ is at least the number of states.

Exercise 11 Show that if an arbitrary ${n}$-state DFA accepts any string ${w}$ with ${|w| \ge n}$, then the DFA’s language is infinite. (Hint: Pigeonhole Principle)

Here is an important lemma that is used most often in proofs involving non-regularity of languages.

Lemma 26 Let ${L}$ be a regular language. Then there is a positive integer ${p}$, often called the “pumping constant,” so that if ${w \in L}$ with ${|w| \ge p}$ then ${w}$ can be written as ${uvx}$ such that:

1. ${|uv| \le p}$,
2. ${|v| \ge 1}$,
3. ${uv^ix \in L}$ for all ${i \ge 0}$.

Exercise 12 Prove this lemma. (Hint: it uses the intuitive notion of infinite languages from earlier).

This is often called the “Pumping Lemma.” A common use of the Pumping Lemma is to assume a language is regular, then “pump” a given string in the language until we violate the third condition (i.e., obtain a string not in the language). We do this by showing that no matter the decomposition into ${uvx}$, we can pump out of the language.

Theorem 27 The language ${L = \{0^n1^n : n \ge 0\}}$ is not regular.

Proof: Suppose that ${L}$ were regular, and let ${p}$ be its pumping length. Choose ${w = 0^p1^p}$. Clearly, ${w \in L}$ and ${|w| \ge p}$. What are the decompositions of ${w}$? Since ${|uv| \le p}$, and ${uv}$ occurs only at the beginning of the string, ${u}$ and ${v}$ consist entirely of 0’s (or are empty). We therefore have ${u = 0^a}$ and ${v = 0^b}$ for some constants ${a, b}$. By the second condition, ${b \ge 1}$. Clearly, ${x = 0^{p-a-b}1^p}$.

Now we pump ${w}$ by inserting more copies of ${v}$ into the middle (“pumping up”) or removing ${v}$ (“pumping down”). Either method works here, but we will pump up: observe the string ${uv^2x = 0^a 0^b 0^b 0^{p-a-b}1^p = 0^{p+b}1^p}$. What is the only way that ${uv^2x \in L}$? The only possibility is that ${p+b = p}$. But since ${b \ge 1}$, this is not possible. Therefore, ${L}$ is not regular. $\Box$

Exercise 13 Show that the language ${L = \{w : }$ the number of 0’s in ${w}$ is the same as the number of 1’s in ${w}\}$ is not regular. (Hint: use the previous theorem, and apply a closure property with a known regular language).

Exercise 14 Show that ${L = \{ww : w \in \Sigma^\star\}}$ is not regular.

8. Conclusion

What have we done in this post? Our original goal was to describe, in a formal way, a “simple” computer: one that can only say accept/reject on a input string using simple transitions between states. We called these machines DFAs, and we wanted to understand all of the languages (sets of strings) for which they recognize. We then introduced a generalization of this model that allowed a “choice” between multiple of the same transition, and showed that this model, the NFAs, are equivalent in computational power.

We next introduced a way to describe regular languages, the regular expressions, with equivalence shown between NFAs. Since NFAs are equivalent to DFAs, we have shown that regular expressions describe these languages also. And the final new model we introduced was regular grammars, which is a way of generating strings in a language, and equivalence (again) was shown with NFAs. We now have four equivalent models of computation for the same set of languages.

But we asked the question about whether there exist languages that were not regular. In order to prove their existence, we observed simple facts about long, accepted strings for a DFA, and noted that they must repeat a state. Looking further, we found that we can describe the structure of regular languages. If we can prove a language does not have that structure, it cannot be regular. And we found many languages that are not regular.

There are a lot of other questions here on regular languages that I will not expand upon, but are nevertheless important to study:

• For a given DFA ${M}$, it may be important to know the number of accepted strings of a given length ${n}$. For those of you who know about graphs, this relates to the adjacency matrix of a graph, and can be proved in that setting by looking at successive powers of this matrix.
• Is there an algorithm to find the smallest equivalent DFA (i.e., not changing the language)? What about for an NFA? Regular expression? Regular grammar? It turns out that only the first is computationally tractable, whereas the other three are not!
• Related to the last item: instead of the minimum number of states, but the minimum number of final states?
• We may be concerned for running time in terms of one of the conversions described earlier. Can we prove that for the NFA to DFA conversion, there are some NFAs for which we need to create ${\Theta(2^n)}$ states? What about on “average”?

In the next set of lecture notes, we will look at a model of computation that is “more powerful” than the ones described here (i.e., they will recognize strictly more languages than the regular ones).

9. Further Exercises

Exercise 15 Show that ${L = \{ww^{rev} : w \in \Sigma^\star\}}$ is not regular.

Exercise 16 Show that ${L = \{0^m1^n : m > n\}}$ is not regular.

Exercise 17 Show that ${L = \{0^n : n\;\text{is prime}\}}$ is not regular. (Hint: choose ${i = |ux|}$, and make the length of the string slightly larger than needed).

Exercise 18 (Difficult) Show that if ${L}$ is any unary language, then ${L^\star}$ is regular (even if ${L}$ is itself not regular!).

# Formal Correctness

I am currently a Teaching Assistant for my advisor for a class called Introduction to Theoretical Computer Science, which essentially covers a standard curriculum on automata theory. We just recently covered the Pumping Lemma for regular languages:

Lemma 1 (Pumping Lemma for Regular Languages) Let ${L}$ be a regular language. Then there exists a “pumping constant” $p$ for ${L}$ such that for all ${w \in L}$ with ${|w| \ge p}$, there is a decomposition of ${w}$ into ${uvx}$ such that ${|uv| \le p, |v| \ge 1}$, and ${uv^ix \in L}$ for all ${i \ge 0}$.

The main “use” of the Pumping Lemma is to prove that a language is not regular, with a simple proof by contradiction. The most standard example of non-regularity is ${\{0^n 1^n : n \ge 0\}}$, but another example that I have done in my recitation sections is ${L = \{0^{n^2} : n \ge 0\}}$, which follows from a simple argument of showing inequality with 2 consecutive perfect squares.

One of my students pointed me to this blog post. It claims to show that “checking whether a input number is prime or not” is regular (because there is a regular expression) for it. Of course, I was skeptical: I already knew the problem of even showing that the language consisting of all prime-length strings is not regular:

Theorem 2 The language $L$ consisting of prime lengths only is not regular.

Proof: Suppose it is. Then choose ${w = a^p}$ with ${p}$ any prime number at least (the pumping length of ${L}$) + 1; note, the + 1 here is needed. A small technical detail: there may not necessarily be a prime strictly larger than ${L}$‘s pumping length. But we can guarantee a prime?s existence by the “infinitely many primes” proof by Euclid.

We want to decompose ${w}$ into ${uvx}$, as usual. Whatever the decomposition is, ${|x| \ge 2}$ (because of the +1 from earlier). Therefore, ${|ux| \ge 2}$. Choose ${i = |ux|}$. It suffices to show ${|uv^i x|}$ is not prime. We have ${|uv^i x| = |ux| + |v| \times |ux|}$, which factors into ${(1 + |v|) \times |ux|}$. Since ${1 + |v| \ge 2}$, and ${|ux| \ge 2}$, then ${|uv^i x| = (1 + |v|) \times |ux|}$ is not prime. $\Box$

And of course, Theorem 2 only shows the case of unary alphabets (although the argument can be easily extended). Also note that the language above is not even context-free (a similar counting-then-show-nondivisibility argument): in fact, if it were context free, we would immediately have shown that we can check whether a number is prime or not in ${O(n^3)}$ time (via the well-known CYK algorithm). Looking at the reference my student sent to me, I came across this line: “…The regular expression engine will backtrack and will make (11+?) match “111″…” (emphasis mine). Of course, anyone familiar with automata theory would know that backtracking is not possible here, and can only be done (as taught in standard classes) by Turing Machines.

And that got me thinking. The reason that this student thought that the language was regular was that the name “Regular Expression” is so colloquially and mis-used (as is the norm in theory…), whereas there was a Turing Machine hidden behind the scenes! Also, where else has notation or terminology been mis-used in Computer Science?

One well-known one (in that I differ from the standard opinion) is Landau notation, specifically with big-O notation, commonly used to classify some bound on some function like running time of an algorithm. Here is a standard definition of big-O notation given in an introductory algorithms class:

Definition 3 Let ${f(n), g(n)}$ be two non-negative, real-valued functions with ${n}$ a natural number. Then we say that ${f(n)}$ is big-O of ${g(n)}$, commonly written ${f(n) = O(g(n))}$, if there are fixed constants ${c, n_0}$ (independent of ${n}$) such that ${f(n) \le c \times g(n)}$ for all ${n \ge n_0}$.

One can note that that for some function ${f(n)}$, ${O(f(n))}$ describes many functions, and is actually a set of functions, all with the property listed above. Here is my opinion: I hate the notation ${f(n) = O(g(n))}$. Why? It suggests that a function is equal to a set of functions, which is simply false! I’ve heard the argument that the notation implies that ${f(n)}$ is equal to some function in ${O(g(n))}$. But why go the extra mile? Why not just use the correct mathematical notation of ${f(n) \in O(g(n))}$?

I completely understand the need for lackadaisical definitions: sometimes the math of the problem at-hand is too dense, and a more intuitive approach is necessary. However, I would argue the opposite for most cases here. My main argument stems from having worked in multi-person projects before: although many of us do it all the time, we should not assume that the person reading our code/requirements document/etc. knows exactly what we mean in every scenario. Even though we cannot always be semantically correct, there are places in where we can be formally correct, and I think taking advantage of those opportunities is what is most important.