Theory of Computation: Lecture 1

Strings and Languages

A finite automaton decides a yes/no question about a string while remembering only one of finitely many things at a time. Before the machines come the objects they read and classify.

Alphabet ($\Sigma$). A finite, nonempty set of symbols. $\{0,1\}$ and $\{a,b\}$ are the usual alphabets here; any finite set works.

String. A finite sequence of symbols from $\Sigma$. The length of a string $w$ is written $|w|$, and the empty string $\epsilon$ is the unique string of length $0$.

String universe ($\Sigma^*$). The set of all finite strings over $\Sigma$, including $\epsilon$. Every string in $\Sigma^*$ has finite length, but $\Sigma^*$ itself is infinite whenever $\Sigma$ is nonempty.

Language. Any set of strings, that is, any subset $L\subseteq\Sigma^*$.

A language is a yes/no problem in set form: "does $w$ have property $P$" becomes "is $w$ in the set of strings with property $P$", so solving the problem means deciding membership.

Finite Automata

Finite automaton. A machine with finitely many states. It reads the input one symbol at a time, left to right, and stores only its current state; when the input ends, the current state alone determines the answer.

• Alphabet. The symbols the machine reads, fixed by the problem.
• States. The possible memory values. Their number is fixed and independent of the input length.
• Transition function. For every state and symbol, the rule giving the next state. In a diagram, the labeled arrows.
• Start state. The state before any symbol is read, marked by an unlabeled incoming arrow.
• Accepting states. The states that answer yes when the input ends there, drawn as double circles.

The machine never looks back: everything it will ever use about the symbols read so far must already be packed into the current state.

Example 1. Even number of M symbols.

For strings over $\Sigma=\{M,W\}$, accept exactly the strings in which M appears an even number of times. Counting the M symbols would need unbounded memory, but the answer depends only on the count's parity, and parity is one bit.

Deterministic Finite Automata

Deterministic finite automaton (DFA). A finite automaton whose transition rule gives exactly one next state for every state-symbol pair. A DFA is drawn as a state diagram or written as a 5-tuple; these are the same machine in two forms:

$$M=(Q,\Sigma,\delta,q_0,F)$$

Symbol	Role
$Q$	finite set of states
$\Sigma$	alphabet
$\delta:Q\times\Sigma\to Q$	transition function
$q_0\in Q$	start state
$F\subseteq Q$	accepting states

The tuple settles what a picture can leave unclear. The transition function is total, so every state has exactly one outgoing arrow per symbol, never zero and never two. The accepting set may be empty; with $F=\varnothing$ the machine accepts no string at all.

Extended transition function. The same letter $\delta$ is reused on whole strings: $\delta(q,w)$ is the state reached from $q$ after reading all of $w$, one symbol at a time.

$$\delta(q,\epsilon)=q, \qquad \delta(q,x\sigma)=\delta(\delta(q,x),\sigma)$$

Here $x\sigma$ means the string $x$ followed by the single symbol $\sigma$.

Read the recursion as "strip the last symbol": to process $x\sigma$, first process $x$, then take one step on $\sigma$. Every induction over strings in what follows unwinds exactly this recursion.

Acceptance. A DFA accepts a string $w$ when its run on $w$ ends in an accepting state, that is, when $\delta(q_0,w)\in F$.

• Run. The sequence of states visited while reading the input, starting at $q_0$.
• Empty input. On $\epsilon$ no transition is taken, so the run starts and ends at $q_0$, and $\epsilon$ is accepted exactly when $q_0\in F$.

Tracing the parity machine of Example 1 on two inputs shows acceptance as a pure table computation:

Language of a machine. The language of a DFA $M$, written $L(M)$, is the set of all strings $M$ accepts.

$$L(M)=\{w\in\Sigma^* \mid \delta(q_0,w)\in F\}$$

Recognize. $M$ recognizes a language $A$ when $L(M)=A$. Every DFA recognizes exactly one language; a machine that accepts no strings still recognizes one language, namely $\varnothing$.

Reading a DFA

State meaning. The property of the input read so far that holds exactly when the machine is in that state. To read an unfamiliar DFA, trace a few short strings and name what each state remembers; the language then falls out of the accepting states. Give every state a meaning, not only the accepting ones.

Example 2. Strings ending in 1.

Example 3. Same transitions, different accepting state.

Example 4. At least one 1, then an even number of 0s.

Therefore:

$$L=\{w \mid w \text{ contains at least one }1\text{ and has an even number of }0\text{s after the last }1\}$$

Accepted: $1$, $101$, $100$, $00100$. Rejected: $\epsilon$, $0$, $10$, $0010$.

Formal description. A formal description instantiates the tuple $M=(Q,\Sigma,\delta,q_0,F)$ with concrete sets and a complete transition table. For the machine of Example 4:

Proving a DFA Correct

A DFA is correct when $L(M)$ equals the intended language $L$. That is two inclusions at once:

• Soundness. Every string the machine accepts belongs to $L$.
• Completeness. Every string of $L$ is accepted.

Both directions follow from one stronger statement that pins down where every string lands, and that statement is proved by induction.

Induction on strings. To prove a claim for all strings: prove it for $\epsilon$, then prove that it survives appending one symbol.

• Base case. Prove the claim for $w=\epsilon$.
• Induction hypothesis. Assume the claim for an arbitrary string $x$.
• Inductive step. Prove the claim for $x\sigma$, for every symbol $\sigma\in\Sigma$.

This is sound because every string is built from $\epsilon$ by finitely many appends, and it fits DFAs perfectly because the extended transition function is defined by the same last-symbol recursion.

State characterization. For each state $q_i$ of a DFA, the set of strings that drive the machine from the start state to $q_i$:

$$T_i=\{w\in\Sigma^*\mid \delta(q_0,w)=q_i\}$$

The sets $T_0,\dots,T_n$ partition $\Sigma^*$, since every string lands in exactly one state, and $L(M)$ is the union of the $T_i$ whose states are accepting. A characterization is the state meanings made formal.

Recipe: proving $L(M)=L$.

1. Characterize every state. Write a precise description of $T_i$ for each state $q_i$, accepting or not.
2. Match the language. Check that $L$ is exactly the union of the $T_i$ for accepting $q_i$.
3. Claim. For all strings $w$: $\delta(q_0,w)=q_i$ iff $w\in T_i$, simultaneously for every $i$.
4. Base case. Check that $\epsilon$ satisfies the description of the start state and no other.
5. Inductive step. Assume the claim for $x$ and prove it for $x\sigma$, by cases over the state after $x$ and the symbol $\sigma$. Each case is one application of $\delta(q_0,x\sigma)=\delta(\delta(q_0,x),\sigma)$.
6. Conclude. The claim plus step 2 give $L(M)=L$.

Example 5. Even number of a symbols, proved correct.

Let $\Sigma=\{a,b\}$ and $L=\{w\mid \mathrm{count}(w,a)\text{ is even}\}$, where $\mathrm{count}(w,a)$ is the number of a symbols in $w$.

1. Claim. For every string $w$, the DFA reaches $q_0$ iff $\mathrm{count}(w,a)$ is even, and reaches $q_1$ iff $\mathrm{count}(w,a)$ is odd.

2. Base case. For $w=\epsilon$, no symbol is read, so $\delta(q_0,\epsilon)=q_0$. Also $\mathrm{count}(\epsilon,a)=0$, which is even.

3. Inductive step. Assume the claim holds for $x$. Appending one symbol gives exactly four cases:

State after $x$	Symbol $\sigma$	State after $x\sigma$	Count effect
$q_0$	$b$	$q_0$	even stays even
$q_0$	$a$	$q_1$	even becomes odd
$q_1$	$b$	$q_1$	odd stays odd
$q_1$	$a$	$q_0$	odd becomes even

4. Conclusion. The transition table and the count update agree in every case, so the claim holds for all strings. Since $q_0$ is the only accepting state, the DFA accepts exactly the strings with an even number of a symbols.

Weak claim. A claim that identifies the language but does not pin down every state. It can be true yet unprovable by direct induction, because the induction step needs to know which state the run is in after $x$, not only whether $x$ is currently accepted.

Example 6. At least two a symbols: weak versus strong claims.

Let $\Sigma=\{a,b\}$. The following DFA accepts once it has seen two a symbols and then stays accepting.

The weak hypothesis only says: if $\delta(q_0,x)\ne q_2$, then $\mathrm{count}(x,a)<2$. It cannot rule out the combination $\delta(q_0,x)=q_0$ with $\mathrm{count}(x,a)=1$. The real machine never produces that combination, but the induction does not know it, and on it the step breaks: $xa$ would have two a symbols while the machine has only reached $q_1$. The claim must distinguish $\mathrm{count}=0$ from $\mathrm{count}=1$, because reading a from $q_0$ gives $q_1$ while reading a from $q_1$ gives $q_2$.

The stronger claim names all three state meanings:

$$\delta(q_0,w)= \begin{cases} q_0 & \text{if } \mathrm{count}(w,a)=0,\\ q_1 & \text{if } \mathrm{count}(w,a)=1,\\ q_2 & \text{if } \mathrm{count}(w,a)\ge 2. \end{cases}$$

When an induction stalls, do not weaken the goal; strengthen it. The right claim names, for every state, exactly which strings lead there.

1. Claim. For every string $w$, the reached state is the one named by the piecewise characterization.

2. Base case. For $w=\epsilon$, no symbol is read, so $\delta(q_0,\epsilon)=q_0$, and $\mathrm{count}(\epsilon,a)=0$.

3. Inductive step. Assume the stronger claim holds for $x$. The transition function and the count update agree in all six possible cases:

State after $x$	Count from the hypothesis	Symbol $\sigma$	State after $x\sigma$	Count after $x\sigma$
$q_0$	$0$	$b$	$q_0$	$0$
$q_0$	$0$	$a$	$q_1$	$1$
$q_1$	$1$	$b$	$q_1$	$1$
$q_1$	$1$	$a$	$q_2$	$2$
$q_2$	$\ge 2$	$b$	$q_2$	$\ge 2$
$q_2$	$\ge 2$	$a$	$q_2$	$\ge 3$

4. Conclusion. The stronger claim is preserved after appending either symbol, so it holds for every string. Since $q_2$ is the only accepting state, the DFA accepts exactly the strings with at least two a symbols.

Regular Languages

Regular language. A language $L\subseteq\Sigma^*$ is regular if some DFA recognizes it, that is, if $L=L(M)$ for a DFA $M$.

Regularity means finite-state recognizability. The machine may read strings of any length, but it must classify them using only finitely many states.

The language of strings over $\{0,1\}$ ending in 1 is regular. The language $\{0^n1^n\mid n\ge 0\}$ is not regular, because it needs unbounded counting.

Whether every language is regular, and how to prove that a specific one is not, is the next big question; first come the operations that build new regular languages from old ones.

Operations on Languages

Closure. A class of languages is closed under an operation if applying the operation to languages in the class always produces another language in the class.

Closure results give a second way to prove regularity. The first is direct: design a DFA and prove it correct with the recipe. The second is algebraic: write the language as a combination of known regular languages under operations that preserve regularity, and no new machine or induction is needed.

Complement. The complement of $L$ over alphabet $\Sigma$ is the set of all strings in $\Sigma^*$ that are not in $L$.

$$\overline{L}=\{w\in\Sigma^*\mid w\notin L\}$$

If $M=(Q,\Sigma,\delta,q_0,F)$ recognizes $L$, then $M'=(Q,\Sigma,\delta,q_0,Q\setminus F)$ recognizes $\overline{L}$. The construction keeps the same states, start state, and transitions, so every run ends in the same state as before; only the verdict is flipped. Regular languages are therefore closed under complement.

Example 7. Complement of strings ending in 1.

The arrows are identical. Only the accepting states change.

Union. The union of two languages contains the strings that belong to at least one of them.

$$L_1\cup L_2=\{w\in\Sigma^*\mid w\in L_1\text{ or }w\in L_2\}$$

Intersection. The intersection of two languages contains the strings that belong to both of them.

$$L_1\cap L_2=\{w\in\Sigma^*\mid w\in L_1\text{ and }w\in L_2\}$$

Product construction. The construction that recognizes both: run the two DFAs in parallel by letting one state record a pair of states, one from each machine. For DFAs $M_1=(Q_1,\Sigma,\delta_1,s_1,F_1)$ and $M_2=(Q_2,\Sigma,\delta_2,s_2,F_2)$:

Part	Product DFA
States	$Q_1\times Q_2$
Start state	$(s_1,s_2)$
Transition	$\delta((r,t),a)=(\delta_1(r,a),\delta_2(t,a))$
Accepting, union	$\{(r,t)\mid r\in F_1\text{ or }t\in F_2\}$
Accepting, intersection	$\{(r,t)\mid r\in F_1\text{ and }t\in F_2\}$

The construction lists every pair, whether or not the pair is reachable, so a product DFA is often larger than necessary but never wrong. If the alphabets differ, first extend both machines to the common alphabet $\Sigma=\Sigma_1\cup\Sigma_2$ by adding a rejecting dead state for the new symbols.

Two finite memories running side by side are still a finite memory: the pair of current states is all the product needs to remember.

Example 8. Product states for union and intersection.

Let $A$ be the language of strings containing at least one 1. Let $B$ be the language of strings with an even number of 0 symbols.

In the product machine, the first letter tracks $A$ and the second letter tracks $B$:

Product state	Meaning
NE	no 1 seen, even number of 0s
NO	no 1 seen, odd number of 0s
YE	at least one 1 seen, even number of 0s
YO	at least one 1 seen, odd number of 0s

The string 1 is in the intersection, since it contains a 1 and has zero 0s. The string 10 is in the union but not the intersection, since it contains a 1 but has an odd number of 0s.

Concatenation. The concatenation of two languages contains the strings obtained by taking one string from the first language followed by one string from the second.

$$L_1\circ L_2=\{xy\mid x\in L_1,\ y\in L_2\}$$

It is also written $L_1L_2$. A string $w$ is in $L_1\circ L_2$ if it has some split $w=xy$ with $x\in L_1$ and $y\in L_2$; the split point is not marked in the input and not fixed in advance.

Example 9. Concatenating finite languages.

Let $L_1=\{0,11\}$ and $L_2=\{1\}$. Then $L_1\circ L_2=\{01,111\}$.

$x\in L_1$	$y\in L_2$	$xy\in L_1\circ L_2$
$0$	$1$	$01$
$11$	$1$	$111$

The split is the whole difficulty. A DFA reading $w$ left to right never knows whether the first part is finished, and a deterministic run cannot try all splits at once. Regular languages are closed under concatenation, but the clean automaton construction needs a machine that is allowed to guess.