Theory of Computation

ε-NFA. An NFA with ε-transitions is a 5-tuple $M=(Q,\Sigma,\delta,q_0,F)$ where $Q$ is a finite set of states, $\Sigma$ the input alphabet, $q_0\in Q$ the start state, $F\subseteq Q$ the final states and

$\delta : Q\times(\Sigma\cup\{\varepsilon\})\to 2^{Q}$

so the machine may change state without reading input.

ε-closure. $\varepsilon\text{-closure}(q)$ is the set of all states reachable from $q$ using zero or more ε-transitions: $q$ itself is in it, and if $p$ is in it and $r\in\delta(p,\varepsilon)$ then $r$ is in it. For a set $S$, $\varepsilon\text{-closure}(S)=\bigcup_{q\in S}\varepsilon\text{-closure}(q)$.

Theorem. For every regular expression $r$ there is an ε-NFA $M$ with $L(M)=L(r)$.

Proof (induction on the number of operators in $r$). We construct $M$ with exactly one final state, no transition into the start state and no transition out of the final state.

Basis.

• $r=\varepsilon$: two states $q_0\xrightarrow{\varepsilon}q_f$.
• $r=\varnothing$: two states $q_0,q_f$ and no transitions.
• $r=a$ ($a\in\Sigma$): $q_0\xrightarrow{a}q_f$.

Induction. Let $r_1,r_2$ have ε-NFAs $M_1=(\,\cdot\,,q_1,f_1)$ and $M_2=(\,\cdot\,,q_2,f_2)$.

• $r=r_1+r_2$: add a new start $q_0$ and new final $f$ with $q_0\xrightarrow{\varepsilon}q_1$, $q_0\xrightarrow{\varepsilon}q_2$, $f_1\xrightarrow{\varepsilon}f$, $f_2\xrightarrow{\varepsilon}f$. A string is accepted iff it is accepted by $M_1$ or $M_2$.
• $r=r_1r_2$: add $f_1\xrightarrow{\varepsilon}q_2$; start is $q_1$, final is $f_2$. A path goes through $M_1$ (reading a string of $L(r_1)$) and then $M_2$ (a string of $L(r_2)$).
• $r=r_1^{*}$: add new start $q_0$ and final $f$ with $q_0\xrightarrow{\varepsilon}q_1$, $q_0\xrightarrow{\varepsilon}f$, $f_1\xrightarrow{\varepsilon}q_1$, $f_1\xrightarrow{\varepsilon}f$. This accepts $\varepsilon$ and any number of repetitions of strings of $L(r_1)$.
• $r=(r_1)$: same automaton as $r_1$.

Each step preserves the three properties and the language, so every regular expression has an equivalent ε-NFA. $\blacksquare$

Conversion of $(a+b)^*ab^*$. Using the construction:

States 0-7 realise $(a+b)^*$ (union of 2-3 and 4-5 with loop 6 to 1), 8-9 realise $a$, and 10-13 realise $b^*$.

Removing ε-moves and merging gives the compact equivalent automaton. The language is the set of strings that contain at least one $a$ (take the last $a$; everything after it is $b^*$):

Here $q_1$ is accepting: after the first $a$ any continuation, being in $(a+b)^*ab^*$ form, is accepted.

Language accepted by a PDA. Let $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ be a PDA. An instantaneous description (ID) is $(q,w,\gamma)$: state, remaining input, stack (top on the left). Moves are written $\vdash$ and $\vdash^{*}$ for zero or more moves. There are two equivalent definitions.

1. Acceptance by final state: $L(P)=\{\,w : (q_0,w,Z_0)\vdash^{*}(q,\varepsilon,\gamma),\ q\in F,\ \gamma\in\Gamma^{*}\}$ The input is consumed and the PDA is in an accepting state; the stack content is irrelevant.

2. Acceptance by empty stack: $N(P)=\{\,w : (q_0,w,Z_0)\vdash^{*}(q,\varepsilon,\varepsilon),\ q\in Q\}$ The input is consumed and the stack is empty; the final-state set is irrelevant.

The two classes of languages are the same (the context-free languages), as shown by the following conversions.

Empty stack to final state. Given $P_N=(Q,\Sigma,\Gamma,\delta_N,q_0,Z_0)$ with $L=N(P_N)$, build

$P_F=(Q\cup\{p_0,p_f\},\ \Sigma,\ \Gamma\cup\{X_0\},\ \delta_F,\ p_0,\ X_0,\ \{p_f\})$

• $\delta_F(p_0,\varepsilon,X_0)=\{(q_0,Z_0X_0)\}$: push the original start symbol above a new bottom marker $X_0$ and start $P_N$.
• All moves of $\delta_N$ are kept in $\delta_F$.
• For every $q\in Q$: $\delta_F(q,\varepsilon,X_0)\ni(p_f,\varepsilon)$.

If $P_N$ empties its stack on $w$, it exposes $X_0$ and $P_F$ jumps to $p_f$ and accepts. $X_0$ prevents $P_F$ from getting stuck by popping the stack empty prematurely. So $L(P_F)=N(P_N)$.

Final state to empty stack. Given $P_F=(Q,\Sigma,\Gamma,\delta_F,q_0,Z_0,F)$ with $L=L(P_F)$, build

$P_N=(Q\cup\{p_0,p\},\ \Sigma,\ \Gamma\cup\{X_0\},\ \delta_N,\ p_0,\ X_0)$

• $\delta_N(p_0,\varepsilon,X_0)=\{(q_0,Z_0X_0)\}$: new bottom marker $X_0$ guards against $P_F$ emptying its stack without accepting.
• All moves of $\delta_F$ are kept.
• For every $q\in F$ and every stack symbol $Y\in\Gamma\cup\{X_0\}$: $\delta_N(q,\varepsilon,Y)\ni(p,\varepsilon)$.
• For every $Y\in\Gamma\cup\{X_0\}$: $\delta_N(p,\varepsilon,Y)=\{(p,\varepsilon)\}$.

When $P_F$ reaches a final state after reading $w$, $P_N$ moves to $p$ and pops every symbol, including $X_0$, ending with an empty stack. If $P_F$ does not accept, $P_N$ never enters $p$, and the stack never becomes empty because $X_0$ stays at the bottom. So $N(P_N)=L(P_F)$.

Hence languages accepted by final state and by empty stack coincide.

Turing machine. A Turing machine is a 7-tuple

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

where $Q$ is a finite set of states, $\Sigma$ the input alphabet, $\Gamma\supseteq\Sigma$ the tape alphabet, $B\in\Gamma\setminus\Sigma$ the blank, $q_0$ the start state, $F\subseteq Q$ the accepting states and

$\delta:Q\times\Gamma\to Q\times\Gamma\times\{L,R\}$

the transition function. The machine has an infinite tape with a read/write head; in each move it reads the scanned symbol, writes a symbol, moves left or right and changes state.

Language. $L=\{wcw^R \mid w\in\{0,1\}^*,\ c\in\{\varepsilon,0,1\}\}$ is the set of all palindromes over $\{0,1\}$ (even length when $c=\varepsilon$, odd length otherwise).

Idea. Repeatedly erase the first symbol (remembering it), run to the right end, compare it with the last symbol, erase that, and return to the left. If all symbols are erased (or one is left in the middle), accept.

$M=(\{q_0,q_1,q_2,q_3,q_4,q_5,q_f\},\{0,1\},\{0,1,B\},\delta,q_0,B,\{q_f\})$

A missing entry means the machine halts without accepting. If $q_3$ or $q_4$ sees $B$, the only remaining symbol was the one just erased (odd palindrome), so the string is accepted. If $q_0$ sees $B$, everything was matched (even palindrome or empty string).

Acceptance of 0110. An ID is written $\alpha\,q\,\beta$ with the head on the first symbol of $\beta$.

$$\begin{aligned} &q_0\,0110 \vdash B\,q_1\,110 \vdash B1\,q_1\,10 \vdash B11\,q_1\,0 \vdash B110\,q_1\,B\\ &\vdash B11\,q_3\,0 \vdash B1\,q_5\,1B \vdash B\,q_5\,11B \vdash q_5\,B11B \vdash B\,q_0\,11B\\ &\vdash BB\,q_2\,1B \vdash BB1\,q_2\,B \vdash BB\,q_4\,1 \vdash B\,q_5\,BB \vdash BB\,q_0\,B \vdash BBB\,q_f \end{aligned}$$

The machine reaches the accepting state $q_f$, so $0110$ is accepted.

Formal definition of a DFA. A deterministic finite automaton is a 5-tuple $M=(Q,\Sigma,\delta,q_0,F)$ where

• $Q$ is a finite set of states,
• $\Sigma$ is a finite input alphabet,
• $\delta:Q\times\Sigma\to Q$ is the transition function (exactly one next state for every state and symbol),
• $q_0\in Q$ is the start state,
• $F\subseteq Q$ is the set of accepting (final) states.

A string $w$ is accepted if $\hat\delta(q_0,w)\in F$.

DFA for even number of 0s and even number of 1s. Each state records the parity of the 0s and 1s read so far:

• $q_0$ = (even 0s, even 1s), start and final
• $q_1$ = (odd 0s, even 1s)
• $q_2$ = (even 0s, odd 1s)
• $q_3$ = (odd 0s, odd 1s)

$M=(\{q_0,q_1,q_2,q_3\},\{0,1\},\delta,q_0,\{q_0\})$

Reading a 0 flips the 0-parity and reading a 1 flips the 1-parity. Check with $0110$ (two 0s, two 1s): $q_0\xrightarrow{0}q_1\xrightarrow{1}q_3\xrightarrow{1}q_1\xrightarrow{0}q_0$, which is final, so it is accepted. The string $010$ goes $q_0\to q_1\to q_3\to q_2$, which is not final, so it is rejected.

Chomsky Normal Form (CNF). A context-free grammar is in CNF if every production has one of the forms

$A\to BC \quad\text{or}\quad A\to a$

where $A,B,C$ are variables ($B,C$ not the start symbol) and $a$ is a terminal. (The rule $S\to\varepsilon$ is allowed only if $\varepsilon\in L$ and $S$ does not appear on any right side.) Every CFG without $\varepsilon$ can be converted to CNF by removing $\varepsilon$-productions, unit productions and useless symbols, then replacing terminals inside long right sides by new variables and breaking long right sides into pairs of variables. Derivation trees of CNF grammars are binary trees, and a string of length $n$ is derived in exactly $2n-1$ steps.

Example. The grammar $S\to aSb\mid ab$ becomes

$S\to AC\mid AB,\quad C\to SB,\quad A\to a,\quad B\to b$

Greibach Normal Form (GNF). A CFG is in GNF if every production has the form

$A\to a\alpha$

where $a$ is a terminal and $\alpha$ is a (possibly empty) string of variables. Every derivation step therefore produces exactly one terminal at the left end, so a string of length $n$ is derived in $n$ steps, and the form is useful for building PDAs without ε-moves and for proving that left recursion can be removed.

Example. The same grammar in GNF:

$S\to aSB\mid aB,\quad B\to b$

Derivation of $aabb$: $S\Rightarrow aSB\Rightarrow aaBB\Rightarrow aabB\Rightarrow aabb$.

(a) Strings over $\{0,1\}$ whose 2nd symbol from the right is 1.

The string must end with 1 followed by exactly one more symbol (0 or 1); anything may precede:

$(0+1)^*\,1\,(0+1)$

Examples accepted: $10$, $11$, $0110$, $0011$. Rejected: $0$, $01$, $100$.

(b) Strings starting with 00 or 11 and ending with 10 or 01.

For strings of length at least 4 the start and end parts do not overlap, so

$(00+11)\,(0+1)^*\,(10+01)$

generates them (e.g. $0010$, $1101$, $00110$). The start and end can overlap in the middle symbol for length 3: $001$ (starts with 00, ends with 01) and $110$ (starts with 11, ends with 10) satisfy the condition but are not generated above, and no shorter string works. The complete expression is therefore

$(00+11)(0+1)^*(10+01)\;+\;001\;+\;110$

Claim. $L=\{0^m1^m\mid m\ge1\}$ is not regular.

Proof by the pumping lemma. Pumping lemma: if $L$ is regular there is a constant $n\ge1$ such that every $w\in L$ with $|w|\ge n$ can be written $w=xyz$ with (i) $|xy|\le n$, (ii) $|y|\ge1$, (iii) $xy^iz\in L$ for all $i\ge0$.

Assume $L$ is regular and let $n$ be the pumping length. Choose

$w=0^n1^n\in L,\qquad |w|=2n\ge n.$

Since $|xy|\le n$, the substring $xy$ lies inside the leading block of 0s. So

$x=0^{a},\quad y=0^{b}\ (b\ge1),\quad z=0^{\,n-a-b}1^n.$

Pump with $i=2$:

$xy^2z=0^{a}\,0^{2b}\,0^{n-a-b}1^n=0^{\,n+b}1^n.$

Because $b\ge1$, the number of 0s ($n+b$) is greater than the number of 1s ($n$), so $xy^2z\notin L$. This contradicts condition (iii). Hence the assumption is false and $L$ is not regular. $\blacksquare$

(Intuitively, a finite automaton has only finitely many states and cannot remember the unbounded count of 0s needed to match the 1s.)

These are variants of the basic Turing machine; none of them is more powerful than the standard single-tape TM, they only make programming easier.

1. Multiple-tape Turing machine. The machine has $k$ tapes, each with its own independent read/write head. The finite control reads the $k$ scanned symbols together, and in one move it changes state, writes a new symbol on each tape and moves each head left, right or keeps it still:

$\delta:Q\times\Gamma^k\to Q\times\Gamma^k\times\{L,R,S\}^k$

Input is placed on tape 1; the other tapes start blank. It is convenient, e.g. for $\{wcw^R\}$ or copying: copy the input to tape 2 and compare in reverse. Equivalence: a one-tape TM simulates a $k$-tape machine by storing all tapes on one tape, separated by markers, and marking head positions; each move of the multitape machine takes $O(n)$ steps, so a computation of $T(n)$ steps is simulated in $O(T(n)^2)$ time. Hence the same languages are accepted.

2. Multiple-track Turing machine. There is one tape and one head, but the tape is divided into $k$ tracks, so each cell holds a $k$-tuple of symbols $[a_1,a_2,\dots,a_k]$ that is read and written as a single symbol. The tape alphabet is $\Gamma=\Gamma_1\times\dots\times\Gamma_k$. A typical use is marking: the first track holds the input and the second track holds check marks (e.g. primality or divisibility testing, or binary addition with operands on different tracks). It is only a notational convenience, as a standard TM with tape alphabet of tuples is the same.

3. Storage in the finite control (state). The state is made a tuple $[q,d_1,\dots,d_m]$ where $q$ is the control state and $d_i$ are stored data items (symbols remembered). Since both $Q$ and the data are finite, the number of such states is still finite. Example: to test $\{0^n1^n\}$ or the palindrome machine, the first symbol is remembered in the state as $[q_1,0]$ while the head travels to the other end, and then compared. The machine is still an ordinary TM with a larger set of states.

All three models accept exactly the recursively enumerable languages.

NFA for strings ending with 01 over $\{0,1\}$.

$N=(\{q_0,q_1,q_2\},\{0,1\},\delta,q_0,\{q_2\})$

The NFA loops in $q_0$ while reading anything, and guesses the last two symbols: 0 moves to $q_1$, then 1 moves to $q_2$.

Conversion to DFA (subset construction). Start with $\{q_0\}$.

• $\{q_0\}$: on 0 $\to\{q_0,q_1\}$; on 1 $\to\{q_0\}$.
• $\{q_0,q_1\}$: on 0 $\to\{q_0,q_1\}\cup\varnothing=\{q_0,q_1\}$; on 1 $\to\{q_0\}\cup\{q_2\}=\{q_0,q_2\}$.
• $\{q_0,q_2\}$: on 0 $\to\{q_0,q_1\}$; on 1 $\to\{q_0\}$.

No new subsets appear. Final states are those containing $q_2$: $\{q_0,q_2\}$. Renaming $A=\{q_0\}$, $B=\{q_0,q_1\}$, $C=\{q_0,q_2\}$:

Check: $1101$: $A\to A\to A\to B\to C$ accepted; $0110$: $A\to B\to C\to A\to B$ rejected.

PDA for strings over $\{0,1\}$ with equal numbers of 0s and 1s.

Idea: the stack holds the surplus symbol. If the top is the same as the input symbol (or the stack holds only $Z_0$), push; if it is the opposite symbol, pop (cancel one pair). When the input is finished and only $Z_0$ remains, the counts are equal.

$P=(\{q_0,q_f\},\{0,1\},\{0,1,Z_0\},\delta,q_0,Z_0,\{q_f\})$

1. $\delta(q_0,0,Z_0)=\{(q_0,0Z_0)\}$
2. $\delta(q_0,1,Z_0)=\{(q_0,1Z_0)\}$
3. $\delta(q_0,0,0)=\{(q_0,00)\}$
4. $\delta(q_0,1,1)=\{(q_0,11)\}$
5. $\delta(q_0,0,1)=\{(q_0,\varepsilon)\}$
6. $\delta(q_0,1,0)=\{(q_0,\varepsilon)\}$
7. $\delta(q_0,\varepsilon,Z_0)=\{(q_f,Z_0)\}$

(Acceptance is by final state $q_f$; equivalently, rule 7 could pop $Z_0$ to accept by empty stack.)

Acceptance of 0101 (top of stack on the left):

$$\begin{aligned} (q_0,0101,Z_0)&\vdash(q_0,101,0Z_0) &&\text{rule 1}\\ &\vdash(q_0,01,Z_0) &&\text{rule 6}\\ &\vdash(q_0,1,0Z_0) &&\text{rule 1}\\ &\vdash(q_0,\varepsilon,Z_0) &&\text{rule 6}\\ &\vdash(q_f,\varepsilon,Z_0) &&\text{rule 7} \end{aligned}$$

The input is consumed and the PDA is in the final state $q_f$, so $0101$ is accepted.

Complexity of a Turing machine. The complexity of a TM $M$ measures the resources it uses on an input of length $n$.

• Time complexity $T(n)$: the maximum number of moves $M$ makes on any input of length $n$ before halting. $M$ is said to be of time complexity $T(n)$ (language in $\text{DTIME}(T(n))$).
• Space complexity $S(n)$: the maximum number of tape cells scanned on any input of length $n$.

For a nondeterministic TM the maximum is taken over all branches of the computation tree. Complexity is described for large $n$ using asymptotic notation.

Big Oh (upper bound). $f(n)=O(g(n))$ if there are constants $c>0$ and $n_0$ such that

$f(n)\le c\,g(n)\quad\text{for all } n\ge n_0.$

It gives an upper bound (worst-case growth). Example: $3n^2+5n+2=O(n^2)$ (take $c=4$ for $n\ge 6$).

Big Omega (lower bound). $f(n)=\Omega(g(n))$ if there are constants $c>0$ and $n_0$ such that

$f(n)\ge c\,g(n)\quad\text{for all } n\ge n_0.$

It gives a lower bound. Example: $3n^2+5n+2=\Omega(n^2)$ with $c=3$.

Big Theta (tight bound). $f(n)=\Theta(g(n))$ if there are constants $c_1,c_2>0$ and $n_0$ such that

$c_1\,g(n)\le f(n)\le c_2\,g(n)\quad\text{for all } n\ge n_0,$

that is, $f=O(g)$ and $f=\Omega(g)$. Example: $3n^2+5n+2=\Theta(n^2)$.

Example for a TM: a single-tape machine recognising $\{0^k1^k\}$ by repeatedly crossing off a 0 and a 1 takes about $n^2/2$ steps, so $T(n)=\Theta(n^2)$.

Tractable problems. A problem is tractable if it can be solved by a deterministic Turing machine in polynomial time, i.e. in $O(n^k)$ steps for some constant $k$ on inputs of length $n$. These problems form the class P:

$P=\bigcup_{k\ge1}\text{DTIME}(n^k)$

Examples: sorting, shortest path, searching, matrix multiplication, testing whether a string is accepted by a DFA. A polynomial time algorithm stays practical as $n$ grows, and the class is robust: it does not change between reasonable models (multitape TM, RAM), because simulation costs only a polynomial factor.

Intractable problems. A problem is intractable if no polynomial-time algorithm is known, or can exist, so that every algorithm needs super-polynomial (typically exponential) time such as $2^n$ or $n!$. Even for moderate $n$ (say $n=100$) these are unusable, since $2^{100}$ steps is far beyond any computer.

• Problems solvable in polynomial time by a nondeterministic TM form NP: $NP=\bigcup_k \text{NTIME}(n^k)$. A solution can be verified in polynomial time. Clearly $P\subseteq NP$; whether $P=NP$ is open.
• NP-complete problems are the hardest in NP: every NP problem reduces to them in polynomial time (Cook's theorem: Satisfiability, SAT). Others: Travelling Salesman (decision form), Hamiltonian circuit, Vertex cover, Clique, 0/1 knapsack. If any NP-complete problem is in P, then $P=NP$.
• Some problems are provably intractable (EXPTIME-complete), and others are undecidable (halting problem), so not solvable at all.

With reference to TM. A problem is tractable if a deterministic TM decides it in at most $p(n)$ moves for a polynomial $p$; it is treated as intractable if the best known deterministic TM needs exponential moves (a nondeterministic TM may still solve it in polynomial time by guessing the solution and verifying it). Example: a deterministic TM trying all $2^n$ assignments for SAT takes exponential time, while a nondeterministic TM guesses an assignment and checks it in $O(n^2)$ time.

DFA (formal definition). A deterministic finite automaton is a 5-tuple $M=(Q,\Sigma,\delta,q_0,F)$ with a finite set of states $Q$, input alphabet $\Sigma$, start state $q_0\in Q$, accepting states $F\subseteq Q$ and transition function

$\delta:Q\times\Sigma\to Q$

giving exactly one next state for every state and input symbol.

NFA (formal definition). A nondeterministic finite automaton is a 5-tuple $N=(Q,\Sigma,\delta,q_0,F)$ where everything is as above except

$\delta:Q\times\Sigma\to 2^{Q}$

so from a state on a symbol the machine may go to zero, one or several states. A string is accepted if at least one path ends in a state of $F$.

Conversion of NFA to DFA (subset construction). Every NFA $N=(Q_N,\Sigma,\delta_N,q_0,F_N)$ has an equivalent DFA $D=(Q_D,\Sigma,\delta_D,\{q_0\},F_D)$:

1. $Q_D\subseteq 2^{Q_N}$; the start state is $\{q_0\}$.
2. For a DFA state $S$ and symbol $a$: $\delta_D(S,a)=\bigcup_{p\in S}\delta_N(p,a)$.
3. Begin with $\{q_0\}$, compute the transitions, and add each new subset obtained; repeat until no new subset appears.
4. $F_D=\{S\in Q_D : S\cap F_N\ne\varnothing\}$.

By induction on $|w|$, $\hat\delta_D(\{q_0\},w)=\hat\delta_N(q_0,w)$, so $L(D)=L(N)$. In the worst case the DFA has $2^{|Q_N|}$ states.

Example. NFA over $\{0,1\}$ accepting strings whose second symbol from the right is 1.

Subset construction:

• $\{q_0\}$: 0 $\to\{q_0\}$, 1 $\to\{q_0,q_1\}$
• $\{q_0,q_1\}$: 0 $\to\{q_0\}\cup\{q_2\}=\{q_0,q_2\}$, 1 $\to\{q_0,q_1\}\cup\{q_2\}=\{q_0,q_1,q_2\}$
• $\{q_0,q_2\}$: 0 $\to\{q_0\}\cup\varnothing=\{q_0\}$, 1 $\to\{q_0,q_1\}$
• $\{q_0,q_1,q_2\}$: 0 $\to\{q_0,q_2\}$, 1 $\to\{q_0,q_1,q_2\}$

Final states are the subsets containing $q_2$. Naming $A=\{q_0\}$, $B=\{q_0,q_1\}$, $C=\{q_0,q_2\}$, $D=\{q_0,q_1,q_2\}$:

Check: $0110$ goes $A\to A\to B\to D\to C$ (final), accepted; the second symbol from the right is 1. $0101$: $A\to A\to B\to C\to B$, rejected, as the second symbol from the right is 0.

The DFA has states $A,\dots,F$, start state $A$, and the only final state is $D$:

All six states are reachable from $A$ ($A\to B,F$; $B\to E,C$; $C\to D$), so no state is removed first. Use the partition-refinement (table-filling) method.

Step 0. Separate final from non-final: $P_0=\{A,B,C,E,F\},\{D\}$.

Step 1. For the non-final states look at the groups reached on 0 and 1 (group 1 = $\{A,B,C,E,F\}$, group 2 = $\{D\}$):

$C$ reaches $D$ on 1, so it is distinguished: $P_1=\{A,B,E,F\},\{C\},\{D\}$.

Step 2. Groups: $g_1=\{A,B,E,F\}$, $g_2=\{C\}$, $g_3=\{D\}$.

$A,F$ go to $g_1$ on both symbols; $B,E$ go to $g_1$ on 0 and $g_2$ on 1. So $P_2=\{A,F\},\{B,E\},\{C\},\{D\}$.

Step 3. Check $\{A,F\}$: on 0 both go to $B$; on 1, $A\to F$ and $F\to A$, both in $\{A,F\}$. Check $\{B,E\}$: on 0, $B\to E$, $E\to B$, both in $\{B,E\}$; on 1 both go to $C$. No further splitting, so $P_3=P_2$.

Equivalent states: $A\equiv F$ and $B\equiv E$.

Minimum DFA (4 states), with $[AF]$ as start state and $[D]$ final:

It accepts the strings ending in $011$ (for example $[AF]\xrightarrow{0}[BE]\xrightarrow{1}[C]\xrightarrow{1}[D]$ on $011$).

TM for odd-length strings over $\{a,b\}$.

Idea: the head moves right over the input, toggling between two states $q_0$ (even number of symbols read so far) and $q_1$ (odd number read). At the blank, accept if the machine is in $q_1$.

$M=(\{q_0,q_1,q_2\},\{a,b\},\{a,b,B\},\delta,q_0,B,\{q_2\})$

There is no move for $(q_0,B)$ (even length, including $\varepsilon$), so the machine halts and rejects.

For $w=abb$: $q_0\,abb\vdash a\,q_1\,bb\vdash ab\,q_0\,b\vdash abb\,q_1\,B\vdash abbB\,q_2$, accepted.

Encoding for the Universal Turing Machine. Number the states $q_0,q_1,q_2$ as $1,2,3$ (the index is the number of 0s), symbols $a=X_1$, $b=X_2$, $B=X_3$, and directions $L=D_1$, $R=D_2$. A move $\delta(q_i,X_j)=(q_k,X_l,D_m)$ is coded

$0^i\,1\,0^j\,1\,0^k\,1\,0^l\,1\,0^m$

(state numbers 1, 2, 3 for $q_0,q_1,q_2$):

The code of $M$ is the moves written one after another, separated by $11$ and enclosed by $111$:

$\langle M\rangle=111\,01010010100\,11\,0100100100100\,11\,00101010100\,11\,0010010100100\,11\,00100010001000100\,111$

Input $w=abb$ is encoded by writing each symbol as its number of 0s, separated by single 1s: $a=0$, $b=00$, so

$\langle w\rangle = 0\,1\,00\,1\,00=0100100$

The tape given to the universal TM is $\langle M\rangle$ followed by $\langle w\rangle$:

$\langle M\rangle\langle w\rangle=11101010010100110100100100100110010101010011001001010010011001000100010001001110100100$