Week 4 (06.10. & 09.10.2026) Pumping Lemma Practice, Nondeterministic Finite Automata, Power-Set Construction, State Lower Bounds, Turing Machines (Intro)

Covered:

• Lecture 7 (Tue 06.10.): Pumping Lemma recap (Hromkovič’s version vs. the standard textbook version); $\{ww\}$ is not regular; Def. 3.3 (NFA) with configurations, steps, acceptance and $\hat{\delta }$; regular expressions vs. NFAs; ${\mathcal{L}}_{NEA}={\mathcal{L}}_{EA}$; DFA → NFA; Satz 3.2 (NFA → DFA) via computation trees and the power-set construction; the empty set as a metastate; exercise NFA with states $p,q,r,s$; the language family $L_k$ and the start of Lemma 3.6.
• Lecture 8 (Fri 09.10.): warm-up power-set construction; Satz 3.2 (proof idea); Lemma 3.6 (every DFA for $L_k$ needs $\ge 2^k$ states) in full; lower bounds on the number of states for a concrete language (separating-suffix table); Chapter 4: Turing machines: motivation, informal model, Def. 4.1 (7-tuple), an example idea for $\{0^n{1}^n\}$.

Organisational remarks from Week 4

• A worked-example video on the Pumping Lemma (additional variants of the lemma) was uploaded; the matching exercise is done in the exercise groups. It is not graded, but the content is exam material. Work on it with your colleagues, without an LLM.
• The lecturer uploads his handwritten notes to Moodle; no need to photograph the board.
• A link to a Turing machine simulator will be posted on Moodle. Former students built prime tests and shortest-path TMs with it.
• Next week the lecturer is absent. His colleague (Böckenhauer) will go through the formal TM definition; afterwards the course studies what TMs can compute.
• Exam hints: the power-set construction is “easy points”; a lower bound on the number of states via Lemma 3.3 is “something you must master”; non-regularity proofs remain central.
• “From now on (computability) it gets more demanding, so make sure the automata material sits.”

---

1. Executive Overview & Core Objectives

This week finishes the theory of finite automata with nondeterminism. An NFA may have several successor states, or none, for a state–letter pair. It accepts a word if at least one computation reads the whole word and ends in an accepting state.

Despite this apparent power, NFAs and DFAs recognise exactly the same languages (Satz 3.2), via the power-set (subset) construction. The price can be an exponential number of states, and Lemma 3.6 proves that this blow-up is sometimes unavoidable. The method behind it (find many pairwise distinguishable words via Lemma 3.3) also gives lower bounds on the number of states for concrete languages.

Finally, Chapter 4 introduces the Turing machine: a finite control plus an unbounded, writable, two-way tape. The model comes from analysing what a human “computer” does when calculating by hand.

Learning objectives. After this week you should be able to:

• prove non-regularity with the Pumping Lemma, including choosing a word that does not “accidentally” survive pumping (e.g. for $\{ww\}$);
• state Def. 3.3 and define configuration, step, accepting computation and $\hat{\delta }$ for NFAs, as well as $L(M)=\{w\mid \hat{\delta }(q_0,w)\cap F\ne \varnothing \}$;
• draw a computation tree of an NFA on a word and read off acceptance;
• carry out the power-set construction (table first, then diagram), including the $\varnothing$ metastate and the accepting metastates;
• explain why ${\mathcal{L}}_{NEA}={\mathcal{L}}_{EA}$ (both directions);
• state and prove Lemma 3.6 (exponential lower bound for $L_k$);
• prove “every DFA for $L$ needs $\ge n$ states” with a table of separating suffixes;
• explain Turing’s motivation, the components of a TM, the meaning of $\delta (q,a)=(q^{\prime },b,X)$, and Def. 4.1.

---

2. Core Concepts & Formal Definitions

2.1 Pumping Lemma: the version used in this course

Lemma 3.4 (Pumping-Lemma, Hromkovič's version)

Let $L\subseteq {\Sigma }^{\ast }$ be regular. Then there is a constant $n_0\in \mathbb{N}$ such that for all $w\in {\Sigma }^{\ast }$ with $|w|\ge n_0$ there is a decomposition $w=yxz$ with

• (i) $|yx|\le n_0$
• (ii) $|x|\ge 1$
• (iii) $\{y{x}^{k}z\mid k\in \mathbb{N}\}\subseteq L$ or $\{y{x}^{k}z\mid k\in \mathbb{N}\}\cap L=\varnothing$

Intuition: comparison with standard textbooks

Many standard textbooks (e.g. Hopcroft/Motwani/Ullman) state the lemma only for words $w\in L$ and drop the "$\cap L=\varnothing$" alternative. That version is correct but weaker. Hromkovič’s version also covers $w\notin L$: pumping keeps the run ending in the same state, so non-members stay non-members.
This gives extra flexibility for non-regularity proofs: you may start from a word outside $L$ and pump it into $L$.

Exam Trap: $|w|\ge n_0$

The lecture again said “words longer than $n_0$”; the handwritten notes write $|w|\ge n_0$. Use $\ge$.

2.2 Nondeterministic finite automata (Nichtdeterminismus, §3.5)

Exam Trap: Nichtdeterminismus ≠ randomness (again)

There are no probabilities attached to transitions, and there are no coin flips. The model allows several computations on the same word, and the acceptance condition is a single big existential quantifier: “there exists an accepting computation”.

Definition 3.3 (nichtdeterministischer endlicher Automat, NEA)

A nondeterministic finite automaton (NEA / NFA) is a 5-tuple $M=(Q,\Sigma ,\delta ,q_0,F)$, where $Q$, $\Sigma$, $q_0$, $F$ are defined as for a DFA, and
$\delta :Q\times \Sigma \to \mathcal{P}(Q)$
maps into the power set of $Q$. So for a state $q$ and a symbol $a$, several successor states are possible (any number, including $0$).

(In the lecture $\Sigma$ was once called “Arbeitsalphabet”. That was a slip: it is the input alphabet. A work alphabet $\Gamma$ only appears for Turing machines.)

Example: from a state $q$ with $\delta (q,a)=\{q_1,q_2,q_5\}$, reading $a$ may lead to any of the three. If some $\delta (q_5,b)=\varnothing$, the computation gets stuck when reading $b$ in $q_5$.

Definitions (configurations, steps, computations for NFAs)

Let $M=(Q,\Sigma ,\delta ,q_0,F)$ be an NFA.

• A configuration is an element of $Q\times {\Sigma }^{\ast }$. $(q_0,x)$ is the start configuration on $x$.
• A step:
  $(q,w){⊢}_M(p,x)⟺w=ax,a\in \Sigma ,p\in \delta (q,a)$
  The only change compared with DFAs is "$p\in \delta (q,a)$" instead of "$p=\delta (q,a)$".
• A computation is a finite sequence $D_1,\dots ,D_k$ of configurations with $D_i{⊢}_M{D}_{i+1}$.
• An accepting computation of $M$ on $x$ is a computation $C_0,\dots ,C_m$ with $C_0=(q_0,x)$ and $C_m=(p,\lambda )$ for some $p\in F$.
• $M$ accepts $x$ $⟺$ there exists an accepting computation of $M$ on $x$.

Exam Trap: getting stuck is never acceptance

Acceptance requires the word to be completely read (the configuration ends in $\lambda$) and the state to be accepting. If a computation reaches an accepting state but still has to read a letter for which there is no outgoing edge, that computation gets stuck and does not accept, regardless of whether the current state is accepting. Other computations may still accept the word.

Definition ( $\hat{\delta }$ for NFAs)

$\hat{\delta }(q,\lambda )=\{q\}$
$\hat{\delta }(q,wa)=\{p\mid \exists r\in \hat{\delta }(q,w):p\in \delta (r,a)\}={\bigcup }_{r\in \hat{\delta }(q,w)}\delta (r,a)$
Note that $\hat{\delta }(q,\lambda )$ is the singleton $\{q\}$, not $q$. In words: take all states reachable with $w$, then follow every $a$-edge from each of them.

Language of an NFA

$L(M)=\{w\in {\Sigma }^{\ast }\mid \hat{\delta }(q_0,w)\cap F\ne \varnothing \}$
At least one state reachable after reading all of $w$ is accepting.
(On the board, $\delta$ was first written instead of $\hat{\delta }$; a student corrected it. $\hat{\delta }$ is the version defined on words.)

2.3 NFAs and regular expressions (informal)

Writing a regular expression is essentially describing the accepting paths of an NFA. For example
$a(a+b{)}^{\ast }bb+b{a}^{\ast }b$
(where $+$ means “or” and ${}^{\ast }$ is the Kleene star) corresponds to an NFA that branches at the start:

• branch 1: read $b$, loop on $a$, read $b$, accept;
• branch 2: read $a$, loop on $a,b$, read $b$, read $b$, accept.

One can prove that every NFA has an equivalent regular expression and vice versa (Kleene’s theorem; not proved in this course).

Practical relevance: regex → NFA → DFA, and DFAs are trivial to run (follow one edge per letter). Satz 3.2 below is what makes the NFA → DFA step possible.

2.4 Equivalence of NFAs and DFAs

Definition ( ${\mathcal{L}}_{NEA}$)

${\mathcal{L}}_{NEA}=\{L(M)\mid M\text{ is an NFA}\}$

Satz

${\mathcal{L}}_{NEA}={\mathcal{L}}_{EA}$ ($={\mathcal{L}}_{reg}$). Nondeterminism gives finite automata no additional computational power.

This splits into two theorems:

Satz (DFA → NFA)

For every DFA $A$ there is an NFA $M$ with $L(M)=L(A)$.
Proof: take the same automaton and wrap each successor in a singleton, ${\delta }_M(q,a)=\{{\delta }_A(q,a)\}$. A DFA is just an NFA with exactly one successor everywhere. ∎

Satz 3.2 (NFA → DFA)

For every NFA $M$ there is a DFA $A$ with $L(A)=L(M)$.

Power-set construction (Potenzmengenkonstruktion, also called subset construction). For $M=(Q,\Sigma ,\delta ,q_0,F)$ define
$A=(Q_A,\Sigma ,{\delta }_A,⟨\{q_0\}⟩,F_A)$
with:

• States: $Q_A=\{⟨P⟩\mid P\subseteq Q\}$. Each metastate $⟨P⟩$ stands for ”$M$ could currently be in any state of $P$”. The angle brackets mark a single state of $A$ that corresponds to the set $P$.
• Transitions: ${\delta }_A(⟨P⟩,a)=⟨{\bigcup }_{p\in P}\delta (p,a)⟩$.
• Accepting states: $F_A=\{⟨P⟩\mid P\cap F\ne \varnothing \}$, i.e. $A$ accepts iff $M$ could be in an accepting state.

In practice you only construct the metastates reachable from $⟨\{q_0\}⟩$ (see §4.2).

Exam Trap: rules for the power-set construction

• The start state is the singleton $⟨\{q_0\}⟩$.
• If a successor set is $\varnothing$, then $⟨\varnothing ⟩$ is an ordinary metastate. It must appear in the DFA with self-loops on all letters: it is a sink. A DFA may never get stuck. The NFA’s “getting stuck” becomes “entering the sink $⟨\varnothing ⟩$”.
• Accepting: every metastate containing at least one accepting NFA state.
• Final sanity check: the result must be deterministic and complete, with exactly one edge per letter per state.

2.5 The price: exponential blow-up (Lemma 3.6)

Formally, $|Q_A|=2^{|Q|}$. Often far fewer metastates are reachable, and some may even be mergeable. But the blow-up is sometimes unavoidable:

Definition ( $L_k$)

For $k\in \mathbb{N}-\{0\}$:
$L_k=\{x1y\mid x\in {\Sigma }_{\text{bool}}^{\ast },y\in {\Sigma }_{\text{bool}}^{k-1}\}$
the binary words whose $k$-th symbol from the end is a $1$.
Example $k=5$: $0010001\in L_5$ (5th from the end is $1$), $1001001\notin L_5$ (5th from the end is $0$).
(The notes of 06.10. write $x\in {\Sigma }_{\text{bool}}^k$, a slip. The notes of 09.10. correctly have $x\in {\Sigma }_{\text{bool}}^{\ast }$.)

NFA $M_k$ with $k+1$ states:

• $q_0$ loops on $0,1$;
• $q_0\stackrel{1}{\to }{q}_1\stackrel{0,1}{\to }{q}_2\stackrel{0,1}{\to }\cdots \stackrel{0,1}{\to }{q}_k$;
• $F=\{q_k\}$;
• no outgoing edges from $q_k$.

It “guesses” that the current $1$ is the $k$-th symbol from the end, then checks that exactly $k-1$ more symbols follow. Too few: the run ends before $q_k$. Too many: it gets stuck in $q_k$.

Lemma 3.6

For all $k\in \mathbb{N}-\{0\}$, every DFA that accepts $L_k$ has at least $2^k$ states.

So nondeterministically $k+1$ states suffice, while deterministically $2^k$ are needed. (A more involved construction makes the gap even sharper; it is not covered.)

2.6 Lower bounds on the number of states (general method)

Intuition: distinguishable words

Two words $x\ne y$ are distinguishable with respect to $L$ if some suffix $z$ has exactly one of $xz$, $yz$ in $L$. By Lemma 3.3, distinguishable words must end in different states of every DFA for $L$.
Hence: if you find $n$ pairwise distinguishable words, every DFA for $L$ has at least $n$ states.

Method:

1. Choose $n$ words $w_1,\dots ,w_n$.
2. For every pair $i<j$, give a separating suffix $z_{ij}$. A triangular table is the standard presentation.
3. Conclude by Lemma 3.3: all $n$ words lie in different states, so $|Q|\ge n$.

Heuristic for finding the words: build a small DFA for $L$, then take the shortest word reaching each state. Starting with $\lambda$ is often a good idea.

2.7 Turing machines (Chapter 4), motivation and informal model

History. Developed by Alan Turing around 1935 and published 1936 (“On Computable Numbers”), before electronic computers existed. He called it a computing machine; the name “Turing machine” came later.

Precursors existed:

• Jacquard’s looms, controlled by punched cards;
• Babbage’s Analytical Engine, about 100 years earlier and inspired by the looms;
• Leibniz’s dream of mechanical calculation.

Turing’s new question was: what can be automated at all? That is, what can a person do who works purely mechanically by fixed rules, without creativity or improvisation?

Exam Trap: chronology

In the lecture, a “24-year-old Turing at Bletchley Park” had the idea. That mixes two periods.

• Turing conceived the machine around 1935–36 at Cambridge (he reportedly got the idea lying in a meadow).
• Bletchley Park (the Enigma codebreaking) was during WWII, from 1939.
• The Turing test is from his 1950 paper “Computing Machinery and Intelligence”.
• The Imitation Game is a film about his life.

Analysis of written multiplication ($789\cdot 23$):
$\begin{array}{r}789\cdot 23\\ 1578\\ 2367\\ 18147\end{array}$
($789\cdot 2=1578$, shifted one place; $789\cdot 3=2367$; sum $15780+2367=18147$.)

What is actually needed:

• read and remember constantly many symbols at a time;
• carry out a small computation in your head using finitely many rules;
• find the place for the result and write it there;
• keep a constant-size intermediate result in your head (the carry);
• write larger intermediate results on paper: their size grows with the input, so they do not fit in a finite head.

Moreover, complex operations reduce to simple ones: multiplication is repeated addition, and addition is repeated $+1$. (Inefficient, but efficiency is not the question here.) Once you can do $+1$ and compare, you can add, multiply, exponentiate, divide, take roots, …

The idealised human computer:

• a pen that never runs out;
• infinitely much squared paper;
• finitely many rules, applied without errors and without tiring.

Process:

1. The input is written on the paper, one symbol per square. The pen starts on the first square.
2. Repeat: look at the current symbol; depending on it and on the internal “state of mind”, leave it or overwrite it, then move one square left or right.
3. Eventually she halts (as in the Linux halt command, and as in the “halting problem”). What is on the paper is the result. For decision problems: accept or reject.

Simplification: 2D paper becomes a 1D tape.

The Turing machine:

• finite control (the “brain”, finitely many states, drawn like a DFA);
• a tape, infinite to the right (semi-infinite), divided into cells;
• cell 0 contains $¢$ (the cent sign), the left end marker: you cannot move left of it;
• then the input $x_1{x}_2\cdots x_n$;
• then infinitely many blanks $\bigsqcup$, so the machine can write beyond the input;
• a read/write head (Lese-/Schreibkopf) on one cell at a time.

The essential differences from a DFA:

1. the head can write;
2. it can move in both directions;
3. the tape is unbounded.

Random access is not needed; sequential movement suffices.

A transition:
$\delta (q,x_i)=(q^{\prime },1,R)$
“In state $q$ reading $x_i$: go to state $q^{\prime }$, overwrite $x_i$ with $1$, move the head one cell to the right.” The movement is one of $L$ (left), $R$ (right), $N$ (stay).

Definition 4.1 (Turing-Maschine, first version; formal details next week)

A Turing machine (TM) is a 7-tuple
$M=(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{accept},q_{reject})$

• $Q$: finite set of states.
• $\Sigma$: input alphabet.
• $\Gamma$: work (tape) alphabet (Arbeitsalphabet), with $\Sigma \subseteq \Gamma$. It contains extra symbols such as the blank $\bigsqcup \in \Gamma -\Sigma$ (and $¢$), plus any auxiliary symbols you want to write (e.g. markers $X$, $Y$).
• $\delta$: transition function, mapping (state, tape symbol) to a triple (new state, symbol to write, head movement).
• $q_0\in Q$: start state.
• $q_{accept}\in Q$: the unique accepting state.
• $q_{reject}\in Q$: the unique rejecting state.

Remarks:

• Unlike DFAs (with a set $F$), a TM has exactly one accepting and one rejecting state. This is no restriction, and it means you do not need to read an output off the tape for decision problems.
• $q_{accept}$ and $q_{reject}$ are sinks: there are no transitions out of them, and entering one ends the computation.
• The precise conditions on $\Gamma$, $¢$, $\bigsqcup$ and $\delta$ come next week.

Exam Trap: $F=\varnothing$ for DFAs is still allowed

While introducing the TM, the lecturer remarked that finite automata have “at least one accepting state, otherwise it would be pointless”. Pointless, yes, but allowed: a DFA with $F=\varnothing$ is valid and accepts $\varnothing$, as stated in an earlier lecture.

Diagram notation (as used in the lecture): an edge from $q$ to $q^{\prime }$ labelled "$a,bX$" means: read $a$, write $b$, move $X\in \{L,R,N\}$. Example fragment from the board:

• $q_0\stackrel{0,1R}{\to }{q}_1$
• $q_0\stackrel{1,1R}{\to }{q}_2$
• a loop on $q_1$ labelled "$1,0R$"
• $q_1\stackrel{0,1L}{\to }{q}_4$

(This was only to illustrate the notation; no particular language.)

---

3. Step-by-Step Derivations & Mathematical Proofs

3.1 $L=\{ww\mid w\in \{0,1{\}}^{\ast }\}$ is not regular (Pumping Lemma)

(On the board the star was first forgotten, giving $\{ww\mid w\in \{0,1\}\}=\{00,11\}$, a finite and hence “highly regular” language. Always check the definition.)

1. Suppose $L$ regular. Let $n_0\in \mathbb{N}$ be the constant from the Pumping Lemma.
2. Choose $u=0^{n_0}10^{n_0}1$. Then $u\in L$ (take $w=0^{n_0}1$) and $|u|=2n_0+2\ge n_0$.
3. Let $u=yxz$ be any decomposition satisfying (i) and (ii):
   • by (i), $|yx|\le n_0$, so $yx=0^l$ with $0\le l\le n_0$ (the first $n_0$ symbols are zeros);
   • by (ii), $x=0^m$ with $m\ge 1$.
4. Since $u\in L$, (iii) requires $y{x}^{k}z\in L$ for all $k$. Take $k=2$:
   $y{x}^{2}z=0^{n_0+m}10^{n_0}1$
5. Why this is not of the form $ww$:
   • The word contains exactly two $1$s.
   • If it equalled $ww$, then $w$ would contain exactly one $1$, say $w=0^{a}10^b$, so $ww=0^{a}10^{a+b}10^b$.
   • Our word ends in $1$, so $b=0$ and $ww=0^{a}10^{a}1$.
   • That would require $n_0+m=a=n_0$, i.e. $m=0$, contradicting $m\ge 1$.
6. So $y{x}^{2}z\notin L$, contradicting (iii). $L$ is not regular. ∎

Intuition: why the single $1$s matter

The obvious choice $0^{n_0}{0}^{n_0}=0^{2n_0}$ fails. Pumping inside the zeros gives $0^{2n_0+(k-1)m}$, which is in $L$ whenever the length is even, e.g. for every $k$ if $m$ is even. There is no contradiction. The separating $1$s “pin” the two halves, so pumping the first block breaks the symmetry. Other choices work too; what matters is a clean contradiction in (iii).

3.2 Correctness of the power-set construction (proof idea of Satz 3.2)

The lecture did not write this out (“you read it in the book like prose”). Here is the full argument.

Claim: for all $x\in {\Sigma }^{\ast }$:
${\hat{\delta }}_A(⟨\{q_0\}⟩,x)=⟨{\hat{\delta }}_M(q_0,x)⟩$
That is, the DFA state after $x$ corresponds exactly to the set of NFA states reachable with $x$.

Induction on $|x|$.

Base case $x=\lambda$: ${\hat{\delta }}_A(⟨\{q_0\}⟩,\lambda )=⟨\{q_0\}⟩=⟨{\hat{\delta }}_M(q_0,\lambda )⟩$.

Induction step: let $x=wa$ with $a\in \Sigma$, and assume the claim for $w$. Then

\hat\delta_A(\langle\{q_0\}\rangle,wa)&=\delta_A\big(\hat\delta_A(\langle\{q_0\}\rangle,w),a\big) &&\text{(Def. of }\hat\delta\text{ for DFAs)}\\ &=\delta_A\big(\langle\hat\delta_M(q_0,w)\rangle,a\big) &&\text{(IH)}\\ &=\Big\langle\bigcup_{r\in\hat\delta_M(q_0,w)}\delta(r,a)\Big\rangle &&\text{(Def. of }\delta_A)\\ &=\langle\hat\delta_M(q_0,wa)\rangle &&\text{(Def. of }\hat\delta\text{ for NFAs)} \end{aligned}$$ **Conclusion:** $$x\in L(A)\iff\langle\hat\delta_M(q_0,x)\rangle\in F_A\iff\hat\delta_M(q_0,x)\cap F\ne\emptyset\iff x\in L(M)$$ ∎ ### 3.3 Proof of Lemma 3.6 1. Let $B_k=(Q_k,\Sigma_{\text{bool}},\delta_k,q_{0k},F_k)$ be any DFA with $L(B_k)=L_k$. 2. Consider all words of length $k$: $S_k=\Sigma_{\text{bool}}^k$, so $\lvert S_k\rvert=2^k$. 3. **Suppose $\lvert Q_k\rvert<2^k$.** By pigeonhole there are $x,y\in S_k$ with $x\neq y$ and $$\hat\delta_k(q_{0k},x)=\hat\delta_k(q_{0k},y)=q$$ 4. Since $x\neq y$ (both of length $k$), there is a position $j\in\{1,\dots,k\}$ with $x_j\neq y_j$. W.l.o.g. $x_j=1$, $y_j=0$: $$x=x_1\cdots x_{j-1}\,1\,x_{j+1}\cdots x_k,\qquad y=y_1\cdots y_{j-1}\,0\,y_{j+1}\cdots y_k$$ 5. **Choose** $z=0^{j-1}$. In $xz$ and $yz$ (length $k+j-1$), position $j$ is the $(k+j-1)-j+1=k$-th symbol **from the end**. Mind the fencepost. 6. So $xz\in L_k$ (the $k$-th symbol from the end is $x_j=1$), but $yz\notin L_k$ (it is $y_j=0$). 7. By Lemma 3.3, $xz$ and $yz$ (same state after $x$ resp. $y$, same suffix $z$) are either both accepted or both rejected. Contradiction. 8. Therefore $\lvert Q_k\rvert\ge2^k=\lvert S_k\rvert$. ∎ > [!tip] Intuition: why exponential is natural here > > The input may end at **any** moment. At every point the DFA must know the symbol $k$ positions back, and then the one $k-1$ back (in case one more symbol comes), and so on. So it must remember the **entire last-$k$ window**, which has $2^k$ possibilities. > The NFA instead **guesses** the right moment once. This "guess and verify" pattern is exactly what NP will formalise for Turing machines. > [!warning] Exam Trap: the position $j$ is arbitrary > > At the end of Tuesday's lecture the lecturer worried that one must take the first or last differing position. As the Friday proof shows, **any** differing position works, because the suffix $z=0^{j-1}$ is adapted to $j$. Just choose $z$ so that position $j$ becomes exactly the $k$-th from the end. --- ## 4. Worked Examples & Applications ### 4.1 Computation tree of an NFA NFA $M$ for "contains $11$": - $q_0$ loops on $0,1$; - $q_0\xrightarrow{1}q_1\xrightarrow{1}q_2$; - $q_2$ accepting, loops on $0,1$; - $\delta(q_1,0)=\emptyset$. Input $x=10110$. The tree branches at every nondeterministic choice and dead-ends where a run gets stuck: | After reading | Configurations (reachable) | $\hat\delta(q_0,\cdot)$ | |---|---|---| | $\lambda$ | $(q_0,10110)$ | $\{q_0\}$ | | $1$ | $(q_0,0110)$, $(q_1,0110)$ | $\{q_0,q_1\}$ | | $10$ | $(q_0,110)$; $(q_1,0110)$ is stuck | $\{q_0\}$ | | $101$ | $(q_0,10)$, $(q_1,10)$ | $\{q_0,q_1\}$ | | $1011$ | $(q_0,0)$, $(q_1,0)$, $(q_2,0)$ | $\{q_0,q_1,q_2\}$ | | $10110$ | $(q_0,\lambda)$, $(q_2,\lambda)$; $(q_1,0)$ is stuck | $\{q_0,q_2\}$ | $(q_2,\lambda)$ is an **accepting configuration**, so $10110\in L(M)$. The accepting path is $q_0\xrightarrow{1}q_0\xrightarrow{0}q_0\xrightarrow{1}q_1\xrightarrow{1}q_2\xrightarrow{0}q_2$. The last column (the **sets of states per level**) is exactly what the power-set construction tracks. ### 4.2 Power-set construction for the "contains 11" NFA (Lecture 7) Build the table **on the fly**, starting from $\langle\{q_0\}\rangle$ and adding every new set as a row: | $\delta_A$ | $0$ | $1$ | |---|---|---| | $\to\{q_0\}$ | $\{q_0\}$ | $\{q_0,q_1\}$ | | $\{q_0,q_1\}$ | $\{q_0\}$ | $\{q_0,q_1,q_2\}$ | | $\{q_0,q_1,q_2\}$ (accepting) | $\{q_0,q_2\}$ | $\{q_0,q_1,q_2\}$ | | $\{q_0,q_2\}$ (accepting) | $\{q_0,q_2\}$ | $\{q_0,q_1,q_2\}$ | Example entries: - $\{q_0,q_1\}$ on $0$: $\delta(q_0,0)\cup\delta(q_1,0)=\{q_0\}\cup\emptyset=\{q_0\}$. - $\{q_0,q_1\}$ on $1$: $\{q_0,q_1\}\cup\{q_2\}$. Accepting: every set containing $q_2$. Only 4 of the $2^3=8$ subsets are reachable. **Diagram:** - $\{q_0\}$: $0$-loop, $1\to\{q_0,q_1\}$; - $\{q_0,q_1\}$: $0\to\{q_0\}$, $1\to\{q_0,q_1,q_2\}$; - $\{q_0,q_1,q_2\}$: $1$-loop, $0\to\{q_0,q_2\}$; - $\{q_0,q_2\}$: $0$-loop, $1\to\{q_0,q_1,q_2\}$. > [!tip] Intuition: post-processing > > The two accepting metastates $\{q_0,q_2\}$ and $\{q_0,q_1,q_2\}$ accept and never lead to a non-accepting state, so they could be **merged**. The resulting 3-state DFA is again very close to the original NFA. Merging is optional "fine-tuning"; the raw construction is what is asked. > > Example run of $01100$ in the DFA: $\{q_0\}\xrightarrow{0}\{q_0\}\xrightarrow{1}\{q_0,q_1\}\xrightarrow{1}\{q_0,q_1,q_2\}\xrightarrow{0}\{q_0,q_2\}\xrightarrow{0}\{q_0,q_2\}$, accepting. This mirrors the NFA path $q_0q_0q_1q_2q_2q_2$. ### 4.3 Exercise NFA with $p,q,r,s$ (Lecture 7) NFA over $\{0,1\}$: - $\delta(p,0)=\{q\}$, $\delta(p,1)=\{p,r\}$ - $\delta(q,0)=\{q,r\}$, $\delta(q,1)=\emptyset$ - $\delta(r,0)=\{r\}$, $\delta(r,1)=\{s\}$ - $\delta(s,0)=\{r,s\}$, $\delta(s,1)=\{s\}$ - start $p$, $F=\{r\}$ **Power-set construction:** | $\delta_A$ | $0$ | $1$ | |---|---|---| | $\to\{p\}$ | $\{q\}$ | $\{p,r\}$ | | $\{q\}$ | $\{q,r\}$ | $\emptyset$ | | $\emptyset$ (sink) | $\emptyset$ | $\emptyset$ | | $\{p,r\}$ (accepting) | $\{q,r\}$ | $\{p,r,s\}$ | | $\{q,r\}$ (accepting) | $\{q,r\}$ | $\{s\}$ | | $\{p,r,s\}$ (accepting) | $\{q,r,s\}$ | $\{p,r,s\}$ | | $\{s\}$ | $\{r,s\}$ | $\{s\}$ | | $\{q,r,s\}$ (accepting) | $\{q,r,s\}$ | $\{s\}$ | | $\{r,s\}$ (accepting) | $\{r,s\}$ | $\{s\}$ | Sample checks: - $\{p,r,s\}$ on $0$: $\{q\}\cup\{r\}\cup\{r,s\}=\{q,r,s\}$. - $\{q,r\}$ on $1$: $\emptyset\cup\{s\}=\{s\}$. 9 of the 16 subsets are reachable. The $\emptyset$ row answers the student question "what if the empty set appears?": it is a **sink metastate** with loops on $0$ and $1$, which is the DFA's way of representing "every NFA run is stuck". ### 4.4 Warm-up power-set construction (Lecture 8) NFA over $\{a,b\}$: - $\delta(q_0,a)=\{q_0\}$, $\delta(q_0,b)=\{q_1\}$ - $\delta(q_1,a)=\{q_0,q_2\}$, $\delta(q_1,b)=\{q_1\}$ - $\delta(q_2,a)=\{q_2,q_3\}$, $\delta(q_2,b)=\emptyset$ - $\delta(q_3,a)=\{q_3\}$, $\delta(q_3,b)=\{q_2\}$ - $F=\{q_3\}$ | $\delta_A$ | $a$ | $b$ | |---|---|---| | $\to\{q_0\}$ | $\{q_0\}$ | $\{q_1\}$ | | $\{q_1\}$ | $\{q_0,q_2\}$ | $\{q_1\}$ | | $\{q_0,q_2\}$ | $\{q_0,q_2,q_3\}$ | $\{q_1\}$ | | $\{q_0,q_2,q_3\}$ (accepting) | $\{q_0,q_2,q_3\}$ | $\{q_1,q_2\}$ | | $\{q_1,q_2\}$ | $\{q_0,q_2,q_3\}$ | $\{q_1\}$ | - **Student question:** would anything change without the $a$-loop on $q_3$? **No**: $\{q_0,q_2,q_3\}$ on $a$ still contains $q_3$ via $q_2\xrightarrow{a}q_3$. - **Correction from the board:** the first drawing had two $a$-edges leaving one state. In the final DFA, $\{q_1,q_2\}$ has $a\to\{q_0,q_2,q_3\}$ and $b\to\{q_1\}$. Always run the determinism check. - **Example:** $abba$ reaches $\{q_0,q_2\}$ in the DFA, so it is rejected. In the NFA, $abba$ can also reach $q_2$ or $q_0$, but never $q_3$. ### 4.5 Lower bound for a concrete language (Lecture 8) $$L=\{w\in\{a,b\}^*\mid \lvert w\rvert_b\equiv1\ (\text{mod }3)\ \text{and } w \text{ starts with } ab\}$$ **Claim:** every DFA for $L$ has at least 6 states. **A natural 6-state DFA** (used to find the words): - $q_0\xrightarrow{a}q_1$, $q_0\xrightarrow{b}q_5$ - $q_1\xrightarrow{a}q_5$, $q_1\xrightarrow{b}q_2$ - $q_2$ (accepting, one $b$): $a$-loop, $b\to q_3$ - $q_3$ (two $b$s mod 3): $a$-loop, $b\to q_4$ - $q_4$ (zero $b$s mod 3): $a$-loop, $b\to q_2$ - $q_5$: sink, loops on $a,b$ Together with Lemma 3.3 this shows the DFA is **minimal**. **Words** (shortest word into each state): - $w_1=\lambda$ ($q_0$) - $w_2=a$ ($q_1$) - $w_3=b$ ($q_5$) - $w_4=ab$ ($q_2$) - $w_5=abb$ ($q_3$) - $w_6=abbb$ ($q_4$) **Separating suffixes** (entry $z$: exactly one of $w_iz$, $w_jz$ is in $L$): | | $w_2=a$ | $w_3=b$ | $w_4=ab$ | $w_5=abb$ | $w_6=abbb$ | |---|---|---|---|---|---| | $w_1=\lambda$ | $b$ | $ab$ | $ab$ | $ab$ | $b$ | | $w_2=a$ | — | $b$ | $\lambda$ | $bb$ | $ab$ | | $w_3=b$ | — | — | $\lambda$ | $bb$ | $b$ | | $w_4=ab$ | — | — | — | $\lambda$ | $\lambda$ | | $w_5=abb$ | — | — | — | — | $b$ | Spot checks: - $(\lambda,a)$, $z=b$: $b\notin L$, $ab\in L$. - $(a,abbb)$, $z=ab$: $aab\notin L$ (wrong prefix), $abbbab\in L$ (four $b$s, $4\equiv1$). - $(abb,abbb)$, $z=b$: $abbb$ has 3 $b$s, so $\notin L$; $abbbb$ has 4, so $\in L$. **Write-up:** by Lemma 3.3, any two words with a separating suffix must end in different states. The table gives one for **every** pair, so the six words lie in six different states and $\lvert Q\rvert\ge6$. ∎ (Many other words and suffixes work.) > [!warning] Exam Trap: every pair, not just consecutive ones > > "Pairwise distinguishable" means **all** $\binom{n}{2}$ pairs need a separating suffix, not only neighbours. You do not need the diagonal or the lower triangle. ### 4.6 TM idea for $L=\{0^n1^n\mid n\in\mathbb{N}\}$ A TM can decide this non-regular language because it can **mark** symbols and **move back**: 1. *(Format check)* Sweep right once to verify the input has the form $0^*1^*$; otherwise reject. 2. Return to the leftmost unmarked symbol: - if it is a $0$, overwrite it with $X$; - if there are no unmarked symbols left, accept; - if it is an unmarked $1$, reject (more $1$s than $0$s). 3. Move right to the **last** unmarked $1$, just before the $Y$s or blanks: - overwrite it with $Y$; - if there is none, reject (more $0$s than $1$s). 4. Go back left to the first unmarked symbol and repeat from step 2. The finite control only needs a handful of states. The unbounded **counting** that a DFA cannot do is done **on the tape** with the markers $X$ and $Y$. (The lecture sketched exactly this idea; TMs will not be built at this level of detail in the course.) --- ## 5. Intuition & Conceptual Bridges > [!tip] Intuition: nondeterminism as "magic guessing" or "parallel worlds" > > Two equivalent views of an NFA run: > - **(a)** it **guesses** the right choice at each step, accepting if some sequence of guesses works; > - **(b)** it runs **all** choices **in parallel**. > > The power-set DFA implements view (b) with finite bookkeeping: the set of currently possible states. For finite automata this bookkeeping is always finite ($\le2^{\lvert Q\rvert}$), so nondeterminism adds no power, only succinctness. > For Turing machines the analogous simulation is possible but potentially exponentially **slow**. Whether that slowdown is avoidable is the **P vs. NP** question. > [!tip] Intuition: all non-regularity and lower-bound proofs are one idea > > Lemma 3.3, the Pumping Lemma, Lemma 3.6 and the state-count tables all exploit the same fact: **a DFA's only memory is its current state**. They differ only in how they force too many distinct "situations" (infinitely many for non-regularity, $2^k$ or $n$ for lower bounds) into finitely many states. **Connections:** - *Back:* - The product automaton (Lemma 3.2) is the same simulation idea with pairs; the power-set construction uses sets. - Lemma 3.3 now yields quantitative lower bounds. - *Forward:* - formal TM definition: configurations, steps, computations, acceptance, halting; - what TMs can and cannot compute (undecidability, the halting problem); - the universal TM (simulation again); - nondeterministic TMs and NP. --- ## 6. Summary & Self-Assessment Questions ### Cheat table | Item | Statement | |---|---| | PL (Hromkovič) | also for $w\notin L$: pumped words stay outside; lets you pump **into** $L$ | | $\{ww\}$ | not regular; e.g. $u=0^{n_0}10^{n_0}1$, pump $k=2$ | | NFA (Def. 3.3) | $(Q,\Sigma,\delta,q_0,F)$, $\delta:Q\times\Sigma\to\mathcal{P}(Q)$ | | NFA step | $(q,ax)\vdash_M(p,x)$ iff $p\in\delta(q,a)$ | | NFA acceptance | $\exists$ computation from $(q_0,x)$ to $(p,\lambda)$, $p\in F$; stuck runs never accept | | $\hat\delta$ (NFA) | $\hat\delta(q,\lambda)=\{q\}$, $\hat\delta(q,wa)=\bigcup_{r\in\hat\delta(q,w)}\delta(r,a)$ | | $L(M)$ (NFA) | $\{w\mid\hat\delta(q_0,w)\cap F\ne\emptyset\}$ | | $\mathcal{L}_{NEA}$ | equals $\mathcal{L}_{EA}=\mathcal{L}_{reg}$ | | DFA → NFA | $\delta_M(q,a)=\{\delta_A(q,a)\}$ | | Satz 3.2 | power-set construction: states $\langle P\rangle$, $P\subseteq Q$; start $\langle\{q_0\}\rangle$ | | Power-set $\delta_A$ | $\delta_A(\langle P\rangle,a)=\langle\bigcup_{p\in P}\delta(p,a)\rangle$ | | Power-set $F_A$ | $\{\langle P\rangle\mid P\cap F\ne\emptyset\}$; $\langle\emptyset\rangle$ is a sink | | $L_k$ | $k$-th symbol from the end is $1$; NFA with $k+1$ states | | Lemma 3.6 | every DFA for $L_k$ has $\ge2^k$ states | | State lower bound | $n$ pairwise distinguishable words (table of suffixes $z$) give $\ge n$ states | | TM components | finite control; tape with $¢$, input, blanks $\sqcup$; read/write head moving $L/R/N$ | | TM transition | $\delta(q,a)=(q',b,X)$: new state, written symbol, movement | | Def. 4.1 | $M=(Q,\Sigma,\Gamma,\delta,q_0,q_{accept},q_{reject})$, $\Sigma\subseteq\Gamma$, $\sqcup\in\Gamma-\Sigma$ | | $q_{accept}$, $q_{reject}$ | unique, sinks (computation ends) | ### Self-assessment questions **Question 1.** Show that $L=\{0^i1^j\mid i\neq j\}$ is not regular. (a) Use the Pumping Lemma directly, choosing $w$ and $k$ cleverly. (b) Give a second proof using closure properties (Lemma 3.2) and the known non-regularity of $\{0^n1^n\}$. > [!question]- Solution to Question 1 > > **(a)** > 1. Suppose $L$ regular, with constant $n_0\ge1$ (forced by (i)+(ii)). > 2. Choose $w=0^{n_0}1^{n_0+n_0!}\in L$, since $n_0\ne n_0+n_0!$. > 3. By (i), any admissible decomposition has $x=0^m$ with $1\le m\le n_0$. In particular $m$ divides $n_0!$. > 4. Since $w\in L$, (iii) requires all $yx^kz\in L$. > 5. Choose $k=1+\frac{n_0!}{m}$. Then $yx^kz=0^{n_0+n_0!}1^{n_0+n_0!}\notin L$ (equal counts). > 6. Contradiction, so $L$ is not regular. ∎ > > (The naive choice $w=0^{n_0}1^{n_0+1}$ with $k=0$ fails when $m\ge2$: it gives $0^{n_0-m}1^{n_0+1}$, still unequal.) > > **(b)** > 1. Suppose $L$ regular. > 2. $L'=0^*1^*$ is regular (2 states plus a sink). Regular languages are closed under complement ($\Sigma^*-L$, a special case of Lemma 3.2's "$-$") and under intersection (Lemma 3.2). > 3. So $(\Sigma^*-L)\cap0^*1^*=\{0^n1^n\mid n\in\mathbb{N}\}$ would be regular. > 4. Contradiction to the earlier result. ∎ **Question 2.** Construct an NFA for $L_2$ (second symbol from the end is $1$), apply the power-set construction, and check that the result matches Lemma 3.6. > [!question]- Solution to Question 2 > > **NFA:** > - $q_0$ loops on $0,1$; > - $q_0\xrightarrow{1}q_1\xrightarrow{0,1}q_2$; > - $F=\{q_2\}$; > - no edges from $q_2$. > > **Power-set construction:** > - $\{q_0\}$: $0\to\{q_0\}$, $1\to\{q_0,q_1\}$ > - $\{q_0,q_1\}$: $0\to\{q_0,q_2\}$, $1\to\{q_0,q_1,q_2\}$ > - $\{q_0,q_2\}$ (accepting): $0\to\{q_0\}$, $1\to\{q_0,q_1\}$ > - $\{q_0,q_1,q_2\}$ (accepting): $0\to\{q_0,q_2\}$, $1\to\{q_0,q_1,q_2\}$ > > **Check:** 4 reachable metastates $=2^2$, exactly the lower bound of Lemma 3.6 for $k=2$. The metastates encode the last two symbols read: $\{q_0\}\leftrightarrow 00$ (or start), $\{q_0,q_1\}\leftrightarrow 01$, $\{q_0,q_2\}\leftrightarrow 10$, $\{q_0,q_1,q_2\}\leftrightarrow 11$. **Question 3.** Prove that every DFA for $L=\{w\in\{0,1\}^*\mid\lvert w\rvert\equiv0\ (\text{mod }3)\}$ has at least 3 states. > [!question]- Solution to Question 3 > > Words: $\lambda$, $0$, $00$. Separating suffixes: > - $(\lambda,0)$, $z=00$: $00$ has length 2, so $\notin L$; $000$ has length 3, so $\in L$. > - $(\lambda,00)$, $z=0$: $0\notin L$, $000\in L$. > - $(0,00)$, $z=0$: $00\notin L$, $000\in L$. > > By Lemma 3.3, the three words lie in pairwise different states of any DFA for $L$, so it has $\ge3$ states. ∎ (The obvious mod-3 counter has exactly 3 states, so 3 is optimal.) **Question 4.** For the warm-up NFA of §4.4, compute $\hat\delta(q_0,w)$ for $w=baa$ and $w=abba$ step by step, decide acceptance, and give an accepting computation where one exists. > [!question]- Solution to Question 4 > > **$w=baa$:** $\{q_0\}\xrightarrow{b}\{q_1\}\xrightarrow{a}\{q_0,q_2\}\xrightarrow{a}\delta(q_0,a)\cup\delta(q_2,a)=\{q_0\}\cup\{q_2,q_3\}=\{q_0,q_2,q_3\}$. > This intersects $F=\{q_3\}$, so **accepted**. Accepting computation: > $$(q_0,baa)\vdash(q_1,aa)\vdash(q_2,a)\vdash(q_3,\lambda)$$ > > **$w=abba$:** $\{q_0\}\xrightarrow{a}\{q_0\}\xrightarrow{b}\{q_1\}\xrightarrow{b}\{q_1\}\xrightarrow{a}\{q_0,q_2\}$. > $\{q_0,q_2\}\cap F=\emptyset$, so **rejected**. No computation ends in $q_3$ after reading all of $abba$. **Question 5.** (a) Why can a TM decide $\{0^n1^n\}$ although no DFA can? Name the model features used. (b) Why does Def. 4.1 have exactly one accepting and one rejecting state, and why are they sinks? > [!question]- Solution to Question 5 > > **(a)** A DFA's only memory is its state (finitely many). Distinguishing $0^i$ for unboundedly many $i$ is impossible (Lemma 3.3). A TM additionally has: > - an **unbounded, writable tape**, where it can mark matched symbols ($X$, $Y$) and thus "count" on the tape; > - **two-way movement**, so it can go back to find the next unmatched $0$. > > The finite control only implements the fixed marking loop. > > **(b)** For decision problems, the result is accept or reject. Two designated states make this explicit, so the tape content at the end is irrelevant. One state of each kind suffices: any "accept situation" can just transition into $q_{accept}$. They are **sinks** (no outgoing transitions) because reaching one **ends** the computation, i.e. the machine **halts** with that answer. A TM may also **never** reach either state, i.e. loop forever. This possibility is the root of undecidability and the halting problem.