Week 3 (29.09. & 02.10.2026) - Product Automata, Non-Regularity, Pumping Lemma, Nondeterminism

Covered:

• Lecture 5 (Tue 29.09.): recap of the infix automaton; a systematic (“remember the last $k$ symbols”) automaton for $L_{110}$ (book Fig. 3.8, p. 62); product automaton for $L_{10}\cap L_{011}$ with unreachable states; Lemma 3.2 (product construction, formal proof); ${\mathcal{L}}_{EA}={\mathcal{L}}_{reg}$; sink states; §3.4 proofs of non-existence; Lemma 3.3 with proof; $\{0^n{1}^n\}$ is not regular; exercise $L_{sq}$ (cliffhanger).
• Lecture 6 (Fri 02.10.): $L_{sq}$ via Lemma 3.3; Lemma 3.4 (Pumping Lemma for regular languages) with intuition, proof and the “game” for applying it; $\{0^n{1}^n\}$ and $L_{sq}$ via the Pumping Lemma; §3.5 Nondeterminism (intuition and first example).

Exam remarks from Week 3

• Lemma 3.3 and the Pumping Lemma: “know by heart”. A non-regularity proof “will 100 % appear in some form in the midterm and also in the final”. Typical wording: “Prove that the following language is not regular”, either with a prescribed technique (Lemma 3.3 or the Pumping Lemma) or your choice.
• The boilerplate earns easy points, so write it out: “We prove this by contradiction. Assume $L$ is regular. Then there is a DFA $A=(Q,\Sigma ,\delta ,q_0,F)$ with $L(A)=L$ …” and close with “Contradiction, so $L$ is not regular.” The real difficulty is choosing the right words, $w$, $z$ or $k$.
• DFA tasks: if the task just says “construct an automaton”, a transition table or explicit $\delta$ is fine. If a diagram is explicitly asked for, draw one. Forgetting a single edge (e.g. a self-loop) costs points, so always do the completeness check.
• Multiple choice on “regular or not?” is common. There is no general shortcut for deciding it.
• The book’s third non-regularity technique (Kolmogorov complexity) is skipped in the lecture. Another technique may be presented later as a video.

---

1. Executive Overview & Core Objectives

This week first completes the constructive side of finite automata: systematic designs, and the product construction, now proved formally as Lemma 3.2, which shows that regular languages are closed under $\cap$, $\cup$ and $-$. It then turns to the harder question of what DFAs cannot do. Since you cannot “show that no automaton exists” by exhibiting one, the lecture introduces two indirect techniques. Both are based on the finiteness of $Q$ and the pigeonhole principle:

• Lemma 3.3: two words that reach the same state are indistinguishable forever after.
• the Pumping Lemma (Lemma 3.4): every sufficiently long word passes through a loop, and that loop can be repeated or removed.

Finally, nondeterministic finite automata (NFAs) are introduced as a step towards the class NP.

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

• build a “sliding window” DFA that remembers the last $k$ symbols, and explain why it is exponentially larger than the “smart” infix automaton;
• carry out the product construction for $\cap$, $\cup$ and $-$, identify unreachable states, and prove Lemma 3.2 by induction;
• state and prove Lemma 3.3, and use it in a full non-regularity proof (choose $|Q|+1$ words, apply pigeonhole, choose a separating suffix $z$);
• state the Pumping Lemma exactly (all quantifiers, $|w|\ge n_0$, conditions (i)–(iii)), explain its proof idea, and apply it with the correct quantifier structure;
• prove $\{0^n{1}^n\mid n\in \mathbb{N}\}$ and $\{0^{n^2}\mid n\ge 1\}$ non-regular with both techniques;
• explain what an NFA is, how its acceptance is defined, and why “nondeterministic” here does not mean “random”.

---

2. Core Concepts & Formal Definitions

2.1 Two styles of DFA design for pattern languages

(a) “Smart” design (partial-match tracking). States record the length of the longest suffix read so far that is a prefix of the pattern. For a pattern of length $k$ this gives $k+1$ states, but the backward edges need thought. Example $L_{0010}$ (from Week 2):

$\delta$	$0$	$1$
$\to q_0$	$q_1$	$q_0$
$q_1$	$q_2$	$q_0$
$q_2$	$q_2$	$q_3$
$q_3$	$q_4$	$q_0$
$q_4$ (accepting)	$q_4$	$q_4$

(At the start of Lecture 5 the self-loop $q_0\stackrel{1}{\to }{q}_0$ was again missing and was added after a student remark: “a nasty grader would deduct a point”.)

(b) Systematic design (sliding window). Example from the book (Abb. 3.8, p. 62):
$L_{110}=\{w\in \{0,1{\}}^{\ast }\mid w\text{ contains }110\}$
Build a binary tree of states $p_{\lambda },p_0,p_1,p_{00},\dots ,p_{111}$, so state $p_u$ means “the last $\min (3,\#\text{read})$ symbols are $u$”:

• $p_{\lambda }\stackrel{a}{\to }{p}_a$, and $p_a\stackrel{b}{\to }{p}_{ab}$, and $p_{ab}\stackrel{c}{\to }{p}_{abc}$ (tree part, $a,b,c\in \{0,1\}$);
• on level 3, shift the window: $p_{abc}\stackrel{d}{\to }{p}_{bcd}$;
• except $p_{110}$, which is accepting and absorbing ($0,1$ self-loop), because the condition is an infix.

Examples on level 3: $p_{000}\stackrel{0}{\to }{p}_{000}$, $p_{000}\stackrel{1}{\to }{p}_{001}$, $p_{001}\stackrel{0}{\to }{p}_{010}$, $p_{010}\stackrel{1}{\to }{p}_{101}$, $p_{011}\stackrel{0}{\to }{p}_{110}$.

Intuition: systematic vs. smart

The systematic DFA has $1+2+4+8=15$ states, versus 4 for the smart one. With a pattern of length $k$ it has about $2^{k+1}$ states versus $k+1$: an exponential blow-up. It is bulky but mechanical, with no tricky backward edges, so it is hard to get wrong. This exponential gap between a “structured” and a “brute-force” description will reappear (NFA → DFA, and later P vs. NP).

2.2 Product construction, formal (Lemma 3.2, “modularer Entwurf” / Simulation, §3.3)

Lemma 3.2

Let $\Sigma$ be an alphabet and let $M_1=(Q_1,\Sigma ,{\delta }_1,q_{01},F_1)$ and $M_2=(Q_2,\Sigma ,{\delta }_2,q_{02},F_2)$ be DFAs. For every set operation $\odot \in \{\cap ,\cup ,-\}$ there is a DFA $M$ with
$L(M)=L(M_1)\odot L(M_2)$

Construction (proof of Lemma 3.2)

$M=(Q,\Sigma ,\delta ,q_0,F_{\odot })$ with

• $Q=Q_1\times Q_2$
• $q_0=(q_{01},q_{02})$
• $\delta ((q,p),a)=({\delta }_1(q,a),{\delta }_2(p,a))$ for all $q\in Q_1$, $p\in Q_2$, $a\in \Sigma$
• $F_{\cup }=F_1\times Q_2\cup Q_1\times F_2$
• $F_{\cap }=F_1\times F_2$
• $F_{-}=F_1\times (Q_2-F_2)$

Idea: $M$ runs $M_1$ and $M_2$ simultaneously on the same word. The lecturer stresses that simulation is the important principle here: later a universal Turing machine simulates arbitrary TMs given as encodings, one of Turing’s key insights.

Requirement: both automata use the same input alphabet (in this course, typically binary encodings).

2.3 Regular languages, notation confirmed

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

${\mathcal{L}}_{EA}=\{L(M)\mid M\text{ is a DFA}\}={\mathcal{L}}_{reg}$
the class of regular languages (reguläre Sprachen). Calligraphic $\mathcal{L}$, because it is a class of languages.

By Lemma 3.2, ${\mathcal{L}}_{reg}$ is closed under intersection, union and difference. With ${\Sigma }^{\ast }\in {\mathcal{L}}_{reg}$ it is also closed under complement, since $L^C={\Sigma }^{\ast }-L$.

2.4 Sink states (Senke) must still be complete

Exam Trap: a sink state still needs its loop

A sink (e.g. the “wrong prefix” state $q_{\varnothing }$ in a prefix automaton) is not a formal component of a DFA. It is just a non-accepting state you can never leave. But since $\delta$ is total, it still needs an outgoing edge for every letter: draw the self-loop labelled with all letters.
There is no “getting stuck” in a DFA. This is different for NFAs (§2.7).
Also, as confirmed again this week: $F=\varnothing$ is allowed; the set of accepting states may be empty.

2.5 Lemma 3.3 (the “no memory except the state” lemma, §3.4)

Why a lemma is needed: to show $L$ is regular, exhibit a DFA. To show $L$ is not regular, you must rule out every DFA, whether with 9, 50 or $3\cdot 10^{20}$ states. “Here is no automaton” is not a proof. So you argue indirectly: any DFA has only finitely many states, and its state is its only memory. It cannot look back at the tape and does not know how it got into its current state.

Lemma 3.3

Let $A=(Q,\Sigma ,{\delta }_A,q_0,F)$ be a DFA. Let $x,y\in {\Sigma }^{\ast }$ with $x\ne y$, such that
$(q_0,x){⊢}_A^{\ast }(p,\lambda )\text{and}(q_0,y){⊢}_A^{\ast }(p,\lambda )$
for some $p\in Q$, i.e. ${\hat{\delta }}_A(q_0,x)={\hat{\delta }}_A(q_0,y)=p$, i.e. $x,y\in Kl[p]$.
Then for every $z\in {\Sigma }^{\ast }$ there is an $r\in Q$ with $xz\in Kl[r]$ and $yz\in Kl[r]$. In particular,
$xz\in L(A)⟺yz\in L(A)$

The condition $x\ne y$ is not needed for the lemma to be true (for $x=y$ it is trivial). It is there because in applications you need two different words that collide.

2.6 The Pumping Lemma (Lemma 3.4)

Lemma 3.4 (Pumping-Lemma für reguläre Sprachen)

Let $L\subseteq {\Sigma }^{\ast }$ be regular. Then there is a constant $n_0\in \mathbb{N}$ such that every word $w\in {\Sigma }^{\ast }$ with $|w|\ge n_0$ can be decomposed into three parts $w=yxz$ with

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

Important features:

• Book naming: the decomposition is $yxz$, with $x$ in the middle. The lecturer finds it annoying but keeps the book’s convention, and so should you.
• $n_0$ is a constant. It depends on $L$ (on a DFA for $L$, in fact $n_0=|Q|$), not on $w$ or $|w|$.
• $w$ ranges over all of ${\Sigma }^{\ast }$, not only over $L$. Condition (iii) covers both cases: if $w\in L$, all pumped words are in $L$; if $w\notin L$, none are. This is Hromkovič’s version; many other textbooks only state it for $w\in L$.
• $k\in \mathbb{N}$ includes $0$. $x$ itself is non-empty, but $y{x}^{0}z=yz$ removes it (“pumping down”).
• It is an implication, not an equivalence. Regular implies pumpable; the converse is in general false (see the exercises). So the Pumping Lemma can only be used to show non-regularity, never regularity.

Exam Trap: $|w|\ge n_0$, not $>$

In the lecture the lemma was read out as “every word longer than $n_0$”, while the notes and book write $|w|\ge n_0$. The proof shows that $|w|=n_0$ already suffices ($n_0$ letters give $n_0+1$ configurations). Use $\ge$.

2.7 Nondeterminism (Nichtdeterminismus, §3.5, intuition only; formal definition next lecture)

In a DFA, $\delta :Q\times \Sigma \to Q$ is total: exactly one successor. A nondeterministic finite automaton (NEA / NFA) relaxes both requirements:
$\delta :Q\times \Sigma \to \mathcal{P}(Q)$

• several successors are allowed, e.g. $\delta (q_0,1)=\{q_0,q_1\}$;
• no successor is allowed, e.g. $\delta (q_1,0)=\varnothing$, and then that computation gets stuck.

Acceptance (informal)

An NFA reads the word left to right exactly once, as a DFA does, but at each step it may follow any available transition. A word $w$ is accepted if there exists at least one computation that reads $w$ completely and ends in an accepting state.

• Other computations that reject or get stuck are irrelevant.
• $w$ is rejected iff every possible computation either gets stuck before the end or ends in a non-accepting state.

Exam Trap: "Nichtdeterminismus" is not randomness

“Not deterministic” in everyday language includes randomised algorithms (coin flips, random bits, Monte Carlo). Nichtdeterminismus in this course is a specific hypothetical model:

• no probabilities;
• no coin flips;
• acceptance means “some choice sequence succeeds”.

A randomised algorithm is “nicht-deterministisch” in the everyday sense, but it is not an instance of Nichtdeterminismus. This model is later used to define NP.

---

3. Step-by-Step Derivations & Mathematical Proofs

3.1 Proof of Lemma 3.2 (correctness of the product automaton)

It suffices to prove, for all $x\in {\Sigma }^{\ast }$:
\hat\delta((q_{01},q_{02}),x)=(\hat\delta_1(q_{01},x),\ \hat\delta_2(q_{02},x))\tag{3.1}
Then $L(M)=L(M_1)\odot L(M_2)$ follows directly from the definition of $F_{\odot }$. For example, for $\cup$: $x\in L(M)⟺\hat{\delta }((q_{01},q_{02}),x)\in F_1\times Q_2\cup Q_1\times F_2⟺{\hat{\delta }}_1(q_{01},x)\in F_1\vee {\hat{\delta }}_2(q_{02},x)\in F_2$. The cases $\cap$ and $-$ are analogous.

Induction on $|x|$.

Base case: $x=\lambda$. Both sides equal $(q_{01},q_{02})$ by $\hat{\delta }(q,\lambda )=q$.

Induction step: assume (3.1) holds for all words of length $\le i$. Let $w\in {\Sigma }^{i+1}$, $w=za$, $a\in \Sigma$.

\hat\delta((q_{01},q_{02}),w)&=\hat\delta((q_{01},q_{02}),za)\\ &=\delta(\hat\delta((q_{01},q_{02}),z),a) &&\text{(Def. 3.2 of }\hat\delta)\\ &\overset{(3.1)}{=}\delta((\hat\delta_1(q_{01},z),\hat\delta_2(q_{02},z)),a) &&\text{(IH, since }\lvert z\rvert=i)\\ &=(\delta_1(\hat\delta_1(q_{01},z),a),\ \delta_2(\hat\delta_2(q_{02},z),a)) &&\text{(Def. of }\delta)\\ &=(\hat\delta_1(q_{01},w),\ \hat\delta_2(q_{02},w)) &&\text{(Def. 3.2 for }\delta_1,\delta_2) \end{aligned}$$ ∎ (The board version contained a typo, $\hat\delta_2(q_{01},z)$; it must be $q_{02}$. A student spotted it.) ### 3.2 Proof of Lemma 3.3 Since $(q_0,x)\vdash_A^*(p,\lambda)$, the same steps can be performed with any suffix $z$ still on the tape: $(q_0,xz)\vdash_A^*(p,z)$. Similarly $(q_0,yz)\vdash_A^*(p,z)$, for all $z\in\Sigma^*$. Let $r=\hat\delta_A(p,z)$. Then the computations are $$(q_0,xz)\vdash_A^*(p,z)\vdash_A^*(r,\lambda)\qquad\text{and}\qquad(q_0,yz)\vdash_A^*(p,z)\vdash_A^*(r,\lambda)$$ so $xz,yz\in Kl[r]$. - If $r\in F$: $xz\in L(A)$ and $yz\in L(A)$. - If $r\notin F$: $xz\notin L(A)$ and $yz\notin L(A)$. So $xz\in L(A)\iff yz\in L(A)$. ∎ > [!tip] Intuition: the coloured-paths picture from the lecture > > In a 5-state DFA, 5 words can land in 5 different states, but a **6th** word must share a state with one of them. In the example, $00111$ and $0111111111$ both end in the same state. From there, reading the same suffix (e.g. $10$) leads both to the **same** state, so they are accepted or rejected together. The automaton "does not know" which of the two it read. ### 3.3 Recipe: non-regularity via Lemma 3.3 1. **Assume** $L$ regular, so there is a DFA $A=(Q,\Sigma,\delta,q_0,F)$ with $L(A)=L$. Let $m=\lvert Q\rvert$ (finite, but you know nothing more). 2. **You choose** $m+1$ distinct words, depending on $m$. This is the creative part. 3. **Pigeonhole:** two of them, $w_i\ne w_j$, reach the same state. **You cannot choose which**: $i,j$ are arbitrary, and you may assume w.l.o.g. $i<j$. 4. **Lemma 3.3:** for **all** $z$: $w_iz\in L\iff w_jz\in L$. 5. **You choose** one $z$ (depending on $i,j$) with $w_iz\in L$ but $w_jz\notin L$, or vice versa. This contradicts step 4, so $A$ cannot exist and $L$ is not regular. The universal quantifier "for all $z$" works in your favour: one counterexample $z$ suffices. ### 3.4 $L_{01}=\{0^n1^n\mid n\in\mathbb{N}\}$ is not regular (via Lemma 3.3) $L_{01}=\{\lambda,01,0011,000111,\dots\}$. Motivation: think of $0$ as "(" and $1$ as ")". Regular expressions cannot check that brackets match, e.g. in HTML tags or `{}` blocks in C/Java. > [!abstract] Lemma > > $L_{01}\notin\mathcal{L}_{EA}$. **Proof (indirect).** 1. Suppose $L_{01}\in\mathcal{L}_{EA}$. Then there is a DFA $A=(Q,\Sigma_{\text{bool}},\delta_A,q_0,F)$ with $L(A)=L_{01}$. 2. Consider the $\lvert Q\rvert+1$ words $0^1,0^2,0^3,\dots,0^{\lvert Q\rvert+1}$. 3. These are more words than $A$ has states, so there are $i,j\in\{1,\dots,\lvert Q\rvert+1\}$ with $i\neq j$ and $\hat\delta_A(q_0,0^i)=\hat\delta_A(q_0,0^j)$. 4. By Lemma 3.3, for all $z\in\Sigma_{\text{bool}}^*$: $0^iz\in L_{01}\iff0^jz\in L_{01}$. 5. Take $z=1^i$. Then $0^i1^i\in L_{01}$, but $0^j1^i\notin L_{01}$ because $j\neq i$. 6. This contradicts the existence of $A$. So $L_{01}$ is not regular. ∎ ### 3.5 $L_{sq}=\{0^{n^2}\mid n\in\mathbb{N}-\{0\}\}$ is not regular (via Lemma 3.3) 1. Suppose $L_{sq}$ regular, with DFA $A=(Q,\{0\},\delta,q_0,F)$. Let $m=\lvert Q\rvert$. 2. Consider $0^1,0^2,\dots,0^{m+1}$. By pigeonhole there are $i,j\in\{1,\dots,m+1\}$ with $i<j$ (w.l.o.g.) and $\hat\delta(q_0,0^i)=\hat\delta(q_0,0^j)$. 3. By Lemma 3.3, for all $z\in\{0\}^*$: $0^iz\in L_{sq}\iff0^jz\in L_{sq}$. 4. **Choose $z$** to complete $0^j$ to the next square: $z=0^{j^2-j+2j+1}=0^{j^2+j+1}$, since $j+(j^2+j+1)=(j+1)^2$. 5. Then $0^jz=0^{j^2+2j+1}=0^{(j+1)^2}\in L_{sq}$. 6. But $0^iz=0^{i+j^2+j+1}=0^{j^2+j+i+1}$, and $$j^2<j^2+j+i+1<(j+1)^2=j^2+2j+1$$ - The left inequality holds because $j+i+1>0$. - The right one holds because $i<j$, so $i+1\le j$, so $j^2+j+i+1\le j^2+2j<j^2+2j+1$. A number strictly between two **consecutive** squares is not a square, so $0^iz\notin L_{sq}$. 7. Contradiction to step 3. So $L_{sq}$ is not regular. ∎ > [!warning] Exam Trap: always justify "not a square" > > It is not enough to say "$j^2+j+i+1$ is not a square". You must give the argument (strictly between two consecutive squares). The lecturer: "Write it down explicitly, so the grader sees you understood it." > [!warning] Exam Trap: the "squares as words" variant needs care > > The lecturer remarked that you could instead take the words $0^{1},0^{4},0^{9},\dots,0^{(m+1)^2}$ and "extend with $2j+1$ zeros or so". As stated, that is **wrong**: > - with words $0^{i^2},0^{j^2}$ ($i<j$) and $z=0^{2j+1}$, the word $0^{i^2+2j+1}$ **can** be a square: for $i=1,j=7$ it is $0^{1+15}=0^{16}=0^{4^2}$. > - **Correct choice:** complete the **smaller** one, $z=0^{2i+1}$. Then $0^{i^2+2i+1}=0^{(i+1)^2}\in L_{sq}$, while $j^2<j^2+2i+1<j^2+2j+1=(j+1)^2$ (since $i<j$), so $0^{j^2+2i+1}\notin L_{sq}$. ✓ > > Lesson: check that the "bad" word really is outside $L$ for **all** admissible $i<j$. ### 3.6 Proof of the Pumping Lemma **Intuition (lecture example over $\{a,b,c\}$, 6 states):** | $\delta$ | $a$ | $b$ | $c$ | |---|---|---|---| | $\to q_0$ | $q_1$ | $q_1$ | $q_2$ | | $q_1$ | $q_1$ | $q_1$ | $q_5$ | | $q_2$ | $q_3$ | $q_1$ | $q_1$ | | $q_3$ | $q_4$ | $q_4$ | $q_4$ | | $q_4$ | $q_2$ | $q_2$ | $q_5$ | | $q_5$ (accepting) | $q_5$ | $q_5$ | $q_5$ | Take $w=cabbcc$, with $\lvert w\rvert=6=\lvert Q\rvert$ (the transcript says "5 letters"; it has 6). **Trace:** $q_0\xrightarrow{c}q_2\xrightarrow{a}q_3\xrightarrow{b}q_4\xrightarrow{b}q_2\xrightarrow{c}q_1\xrightarrow{c}q_5$. That is 6 letters and 7 visited states (counting the start), but only 6 states exist, so some state repeats: here $q_2$, via the loop $abb$. **Decomposition:** $y=c$, $x=abb$, $z=cc$. - $yxxz=c\,abb\,abb\,cc$ goes around the loop twice and still ends in $q_5$, so it is accepted. - $yz=ccc$ skips the loop: $q_0\to q_2\to q_1\to q_5$, accepted. - Going around the loop any number of times $k\ge0$ ends in the same state. **Formal proof.** 1. Let $L\subseteq\Sigma^*$ be regular, with DFA $A=(Q,\Sigma,\delta_A,q_0,F)$, $L(A)=L$. **Set $n_0=\lvert Q\rvert$.** 2. Let $w\in\Sigma^*$ with $\lvert w\rvert\ge n_0$. Write $w=w_1\cdots w_{n_0}u$ with $w_i\in\Sigma$, $u\in\Sigma^*$. Only the first $n_0$ letters matter. 3. Consider the computation of $A$ on $w_1\cdots w_{n_0}$: $$(q_0,w_1\cdots w_{n_0})\vdash_A(q_1,w_2\cdots w_{n_0})\vdash_A\cdots\vdash_A(q_{n_0-1},w_{n_0})\vdash_A(q_{n_0},\lambda)\tag{3.2}$$ Here $q_0,\dots,q_{n_0}$ just **name the states in order of visit**; they are not the automaton's own state names, and some may coincide. 4. These are $n_0+1$ configurations with $n_0+1$ states, but $\lvert Q\rvert=n_0$. So there are $i,j\in\{0,\dots,n_0\}$ with $i<j$ and $q_i=q_j$. 5. So (3.2) can be written as $$(q_0,w_1\cdots w_{n_0})\vdash_A^*(q_i,w_{i+1}\cdots w_{n_0})\vdash_A^*(q_i,w_{j+1}\cdots w_{n_0})\vdash_A^*(q_{n_0},\lambda)\tag{3.3}$$ 6. Set $y=w_1\cdots w_i$, $x=w_{i+1}\cdots w_j$, $z=w_{j+1}\cdots w_{n_0}u$. Then $w=yxz$ and: - **(i)** $\lvert yx\rvert=j\le n_0$. - **(ii)** $i<j$, so $\lvert x\rvert=j-i\ge1$. - **(iii)** From (3.3): $(q_0,yx)\vdash_A^*(q_i,x)\vdash_A^*(q_i,\lambda)$, i.e. reading $x$ from $q_i$ returns to $q_i$. Hence $(q_i,x^k)\vdash_A^*(q_i,\lambda)$ for all $k\in\mathbb{N}$ (by induction on $k$; for $k=0$ it is trivial). Therefore $$(q_0,yx^kz)\vdash_A^*(q_i,x^kz)\vdash_A^*(q_i,z)\vdash_A^*(\hat\delta_A(q_i,z),\lambda)$$ The end state $\hat\delta_A(q_i,z)$ **does not depend on $k$**. If it is in $F$, all $yx^kz\in L$; otherwise none are. ∎ ### 3.7 Applying the Pumping Lemma: quantifiers and the game The lemma has the shape: $L$ regular $\Rightarrow$ $\exists n_0\ \forall w\ (\lvert w\rvert\ge n_0)\ \exists\,y,x,z$ (with $w=yxz$): (i) $\wedge$ (ii) $\wedge$ (iii). To show $L$ is **not** regular, show the **negation** of the right-hand side. Pushing the "not" through flips the quantifiers: $$\forall n_0\ \exists w\ (\lvert w\rvert\ge n_0)\ \forall\, y,x,z \text{ with } w=yxz:\ \big((\text{i})\wedge(\text{ii})\big)\Rightarrow\neg(\text{iii})$$ $\neg$(iii) means: some pumped word is in $L$ and some is not, i.e. $\exists k,k'$ with $yx^kz\in L$ and $yx^{k'}z\notin L$. Typically $w\in L$ (so $k=1$ is in), and you exhibit one $k$ with $yx^kz\notin L$. > [!tip] Intuition: the two-player game (Zwei-Personen-Nullsummenspiel) > > 1. The **adversary** gives you $n_0$. You may **not** choose it. Your argument must work for **every** $n_0$. > 2. **You** choose $w$, depending on $n_0$, with $\lvert w\rvert\ge n_0$. It may lie inside or outside $L$. This is the creative step. > 3. The **adversary** gives you a decomposition $w=yxz$. You may **not** choose it; but you may **use** (i) and (ii) to narrow down what it can look like. > 4. **You** choose $k$ so that $yx^kz$ is on the wrong side of $L$. Then (iii) fails, which is a contradiction. > [!warning] Exam Trap: the most common mistake > > **Never choose the decomposition** ("let $y$ be the first third of the zeros …"). You must argue for **all** decompositions satisfying (i) and (ii). > Likewise **never fix $n_0$** to a number ("for $n_0=15$ we get …"). > What you *do* choose: the word $w$ (as a function of $n_0$) and the pumping exponent $k$. ### 3.8 $L_{01}$ is not regular (via the Pumping Lemma) 1. Suppose $L_{01}=\{0^n1^n\mid n\in\mathbb{N}\}$ regular. Then there is a constant $n_0$ with the properties described by the Pumping Lemma. 2. **Choose** $w=0^{n_0}1^{n_0}\in L_{01}$. Then $\lvert w\rvert=2n_0\ge n_0$. 3. There must be a decomposition $w=yxz$ satisfying (i), (ii), (iii). Consider any such decomposition: - By (i), $\lvert yx\rvert\le n_0$. The first $n_0$ letters are all $0$, so $y=0^l$ and $x=0^m$ for some $l,m\in\mathbb{N}$. - By (ii), $\lvert x\rvert\ge1$, so $m\ge1$. 4. Since $w=yx^1z\in L_{01}$, (iii) requires $$\{yx^kz\mid k\in\mathbb{N}\}=\{0^{n_0-m+km}1^{n_0}\mid k\in\mathbb{N}\}\subseteq L_{01}$$ 5. **Choose $k=0$:** $yx^0z=yz=0^{n_0-m}1^{n_0}\notin L_{01}$, since $m\ge1$ gives fewer zeros than ones. 6. Contradiction, so $L_{01}$ is not regular. ∎ (Any $k\neq1$ works here. The lemma claims membership for **all** $k$, so one bad $k$ suffices.) ### 3.9 $L_{sq}$ is not regular (via the Pumping Lemma) 1. Suppose $L_{sq}$ regular, with constant $n_0$. Note that (i) and (ii) together force $1\le\lvert x\rvert\le n_0$, so $n_0\ge1$. 2. **Choose** $w=0^{n_0^2}\in L_{sq}$, with $\lvert w\rvert=n_0^2\ge n_0$. 3. For any decomposition satisfying (i) and (ii): $x=0^m$ with $1\le m\le n_0$. (On the board this was first written as $m<n_0$; a student corrected it to $\le$.) 4. Since $w\in L_{sq}$, (iii) demands all $yx^kz\in L_{sq}$. **Choose $k=2$:** $yx^2z=0^{n_0^2+m}$. 5. $n_0^2<n_0^2+m\le n_0^2+n_0<n_0^2+2n_0+1=(n_0+1)^2$. The exponent lies strictly between consecutive squares, so $yx^2z\notin L_{sq}$. 6. Contradiction, so $L_{sq}$ is not regular. ∎ (The notes write "$\notin L_{01}$" in this step, a copy slip; it should be $L_{sq}$.) > [!tip] Intuition: Lemma 3.3 vs. Pumping Lemma > > Both exploit finiteness via pigeonhole: > - **Lemma 3.3:** **many words** ($\lvert Q\rvert+1$), so two of them collide in a state. > - **Pumping Lemma:** **one long word** ($\ge\lvert Q\rvert$ letters), so its own run revisits a state, which gives a loop. > > In 3.3 the creative choices are the word family and $z$; in the Pumping Lemma they are $w$ and $k$. The same proof pattern works for $0^{n^3}$, $0^{n!}$, $0^{\lceil n\log n\rceil}$, …: languages whose gaps grow unboundedly. --- ## 4. Worked Examples & Applications ### 4.1 Product automaton for $L_{10}\cap L_{011}$ (solution of last week's voluntary task) $L_{10}=\{w\in\{0,1\}^*\mid w \text{ contains } 10\}$, rows $p_0,p_1,p_2$: - $p_0$: $0\to p_0$, $1\to p_1$ - $p_1$: $1\to p_1$, $0\to p_2$ - $p_2$ (accepting): $0,1\to p_2$ $L_{011}=\{w\mid w \text{ starts with } 011\}$, columns $q_\emptyset,q_0,q_1,q_2,q_3$: - $q_0$: $0\to q_1$, $1\to q_\emptyset$ - $q_1$: $1\to q_2$, $0\to q_\emptyset$ - $q_2$: $1\to q_3$, $0\to q_\emptyset$ - $q_3$ (accepting): $0,1\to q_3$ - sink $q_\emptyset$: $0,1\to q_\emptyset$ (the self-loop is needed!) Embed the smaller automaton as rows and the larger as columns. Product states $r_{i,j}=(p_i,q_j)$, $3\cdot5=15$ in total, start $r_{0,0}$. **Reachable part:** | $\delta$ | $0$ | $1$ | |---|---|---| | $\to r_{0,0}$ | $r_{0,1}$ | $r_{1,\emptyset}$ | | $r_{0,1}$ | $r_{0,\emptyset}$ | $r_{1,2}$ | | $r_{1,2}$ | $r_{2,\emptyset}$ | $r_{1,3}$ | | $r_{1,3}$ | $r_{2,3}$ | $r_{1,3}$ | | $r_{2,3}$ (accepting for $\cap$) | $r_{2,3}$ | $r_{2,3}$ | | $r_{0,\emptyset}$ | $r_{0,\emptyset}$ | $r_{1,\emptyset}$ | | $r_{1,\emptyset}$ | $r_{2,\emptyset}$ | $r_{1,\emptyset}$ | | $r_{2,\emptyset}$ | $r_{2,\emptyset}$ | $r_{2,\emptyset}$ | - **Intersection:** $F=\{r_{2,3}\}$. Language check: $L_{10}\cap L_{011}=\{011u\mid u \text{ contains a } 0\}$. The prefix $011$ contains no $10$, and the first $0$ after it is preceded by a $1$. Matches $r_{1,3}\xrightarrow{0}r_{2,3}$ ✓. - **Union:** additionally make all states with $p_2$ or $q_3$ accepting: $r_{2,\emptyset},r_{2,3},r_{1,3}$ among the reachable ones. > [!tip] Intuition: unreachable states are harmless but redundant > > Seven of the 15 product states are **unreachable** from $r_{0,0}$: $r_{0,2},r_{0,3},r_{1,0},r_{1,1},r_{2,0},r_{2,1},r_{2,2}$. In the lecture, $r_{0,2}$ and $r_{1,1}$ were pointed out as examples. You **may** delete them without changing $L(M)$, and keeping them is also correct ("full points"); you could even add extra useless states, though "why would you". In an exam you can remark that redundant states exist. Lemma 3.2 formally uses all of $Q_1\times Q_2$. > > (Last week the task was announced as the union; this week the lecturer solved it for the intersection and then showed the union by adding accepting states. Both are worth knowing.) ### 4.2 Student question: can I tell quickly whether a language is regular? No general trick. There are hints, e.g. a need for **unbounded counting or matching**, but in general you have to think. That is why exams like multiple-choice questions where it is not obvious. What DFAs **can** count: - **modulo a constant:** $\{0^n\mid n\equiv3\bmod4\}$ needs 4 states (states = residues), and the classes are the residue classes; - **up to a fixed bound** ("at least three 1s"). What they **cannot** count: unboundedly ($0^n1^n$), or with unboundedly growing gaps ($0^{n^2}$). ### 4.3 Student question: why can't the Pumping Lemma "disprove" a regular language? **Question:** for $L=\{w\in\{0,1\}^*\mid w \text{ has at most one } 1\}$, a regular language, pumping a $1$ seems to break (iii). **Answer:** you do not choose the decomposition; the lemma only promises that **one** good decomposition exists. - $L$ has a 3-state DFA, so $n_0=3$. - For $w=100$, pick $y=1$, $x=0$, $z=0$. Then (i) $\lvert yx\rvert=2\le3$, (ii) $\lvert x\rvert=1$, and (iii): $10^k0$ always has exactly one $1$, so every pumped word is in $L$ ✓. - A decomposition with $x=1$ would violate (iii), but the lemma never claims that **every** decomposition works. ### 4.4 Student question: may $x$ be empty? The original $x$ may not be empty: $\lvert x\rvert\ge1$ by (ii). But pumping with $k=0$ **removes** it: $yx^0z=yz$. ### 4.5 First NFA example (§3.5) | $\delta$ | $0$ | $1$ | |---|---|---| | $\to q_0$ | $\{q_0\}$ | $\{q_0,q_1\}$ | | $q_1$ | $\emptyset$ | $\{q_2\}$ | | $q_2$ (accepting) | $\{q_2\}$ | $\{q_2\}$ | Two violations of the DFA rules: $\delta(q_0,1)=\{q_0,q_1\}$ (two choices) and $\delta(q_1,0)=\emptyset$ (stuck). **Language:** $L=\{w\in\{0,1\}^*\mid w \text{ contains } 11\}$, as a student suggested. The two 1s must be **consecutive**: $0101\notin L$. - To accept, the NFA must stay in $q_0$ and then "guess" the right moment to jump to $q_1$ exactly on the first of two consecutive 1s. - Then it reads the second 1 into $q_2$ and loops there. > [!example] Example: computations on $001101$ > > - **Accepting:** $q_0\xrightarrow{0}q_0\xrightarrow{0}q_0\xrightarrow{1}q_1\xrightarrow{1}q_2\xrightarrow{0}q_2\xrightarrow{1}q_2$. One accepting computation suffices, so $001101\in L$. > - **Rejecting:** staying in $q_0$ throughout ends in $q_0\notin F$. > - **Stuck:** $q_0\xrightarrow{0}q_0\xrightarrow{0}q_0\xrightarrow{1}q_0\xrightarrow{1}q_1$, then reading $0$ from $q_1$ is impossible. > > These two failures are irrelevant: existence of one accepting computation is all that counts. > [!example] Example: $000$ and $0101$ > > - $000$: the only computation is $q_0q_0q_0q_0$, so it is rejected. > - $0101$: every attempt to use $q_1$ either gets stuck (the next symbol is $0$) or ends in $q_1\notin F$. Staying in $q_0$ ends in $q_0\notin F$. So it is rejected. > [!warning] Exam Trap: getting stuck in an accepting state still rejects > > Student question: if $q_1$ were accepting, would $010$ be accepted? **No.** $01$ would be accepted (end of word in $q_1$). For $010$, every computation that reaches $q_1$ after the $1$ gets stuck on the final $0$, and a computation that cannot read the **whole** word does not accept. The computation that stays in $q_0$ ends in $q_0\notin F$. --- ## 5. Intuition & Conceptual Bridges > [!tip] Intuition: a DFA's memory is bounded by $\log_2\lvert Q\rvert$ bits > > A DFA with $m$ states can remember at most $\lceil\log_2 m\rceil$ bits about the past, independently of the input length. Any language requiring the automaton to distinguish **infinitely many** "situations" (how many zeros so far? how far to the next square?) is therefore not regular. Lemma 3.3 makes "distinguish" precise: $x$ and $y$ must lead to different states if some $z$ separates them. (This is the idea behind the Myhill–Nerode theorem, which the lecture does not name.) > [!tip] Intuition: why regexes can't parse programs > > Matching brackets is essentially $\{0^n1^n\}$, generalised to nesting. A compiler therefore uses regular expressions only for **lexing** (tokens). **Parsing** needs a stronger model with unbounded memory: the **pushdown automaton** (Kellerautomat, "an external memory"), which comes later, then Turing machines with a work tape. **Connections:** - *Back:* - Lemma 3.3 is the class concept $Kl[p]$ from Week 2, used negatively. - The product proof reuses $\hat\delta$ and the induction pattern of Lemma 3.1. - Pigeonhole and contradiction go back to Diskrete Mathematik. - *Forward:* - Formal NFA definition; NFA → DFA (subset construction), with a possible **exponential** blow-up, as already seen in the sliding-window automaton. - A Pumping Lemma for context-free languages. - Turing machines (unbounded memory), universal TMs (simulation), nondeterministic TMs and **NP**. --- ## 6. Summary & Self-Assessment Questions ### Cheat table | Item | Statement | |---|---| | Sliding-window DFA | remembers the last $k$ symbols; about $2^{k+1}$ states, mechanical | | Lemma 3.2 | $L(M_1)\odot L(M_2)$ regular for $\odot\in\{\cap,\cup,-\}$ via $Q_1\times Q_2$ | | Product $F$ | $\cup$: $F_1\times Q_2\cup Q_1\times F_2$; $\cap$: $F_1\times F_2$; $-$: $F_1\times(Q_2-F_2)$ | | Key identity (3.1) | $\hat\delta((q_{01},q_{02}),x)=(\hat\delta_1(q_{01},x),\hat\delta_2(q_{02},x))$, by induction on $\lvert x\rvert$ | | $\mathcal{L}_{EA}$ | $\{L(M)\mid M \text{ DFA}\}=\mathcal{L}_{reg}$ | | Sink | non-accepting, self-loop on **all** letters; DFAs never get stuck | | Lemma 3.3 | $\hat\delta(q_0,x)=\hat\delta(q_0,y)$ implies $\forall z$: $xz\in L(A)\Leftrightarrow yz\in L(A)$ | | 3.3 recipe | $\lvert Q\rvert+1$ words → two collide ($i<j$ arbitrary) → choose separating $z$ | | Pumping Lemma | $L$ regular ⇒ $\exists n_0\ \forall w,\lvert w\rvert\ge n_0\ \exists\, w=yxz$: $\lvert yx\rvert\le n_0$, $\lvert x\rvert\ge1$, all or none of $yx^kz$ in $L$ | | PL proof | $n_0=\lvert Q\rvert$; the first $n_0$ letters revisit a state, giving the loop $x$ | | PL game | adversary picks $n_0$ → you pick $w$ → adversary picks $yxz$ with (i),(ii) → you pick $k$ | | PL direction | only regular ⇒ pumpable; it cannot prove regularity | | Non-regular | $\{0^n1^n\}$, $\{0^{n^2}\}$, matching brackets | | NFA | $\delta:Q\times\Sigma\to\mathcal{P}(Q)$; accept iff **some** full computation ends in $F$; stuck means that computation rejects | | Nichtdeterminismus | a specific model, **not** randomness | ### Self-assessment questions **Question 1.** Prove with **Lemma 3.3** that $L=\{0^n1^{2n}\mid n\in\mathbb{N}\}$ is not regular. > [!question]- Solution to Question 1 > > 1. Suppose $L$ regular, so there is a DFA $A=(Q,\Sigma_{\text{bool}},\delta,q_0,F)$ with $L(A)=L$. Let $m=\lvert Q\rvert$. > 2. Consider the $m+1$ words $0^1,0^2,\dots,0^{m+1}$. There are more words than states, so there are $i,j\in\{1,\dots,m+1\}$, $i\neq j$, with $\hat\delta(q_0,0^i)=\hat\delta(q_0,0^j)$. > 3. By Lemma 3.3, for all $z\in\Sigma_{\text{bool}}^*$: $0^iz\in L\iff 0^jz\in L$. > 4. Choose $z=1^{2i}$. Then $0^i1^{2i}\in L$, but $0^j1^{2i}\notin L$ because $2i\neq2j$. > 5. Contradiction, so no such $A$ exists and $L$ is not regular. ∎ **Question 2.** Prove with the **Pumping Lemma** that $L=\{a^nb^m\mid n,m\in\mathbb{N},\ n>m\}$ is not regular. Why does pumping **up** fail here, and what do you do instead? > [!question]- Solution to Question 2 > > 1. Suppose $L$ regular, with Pumping Lemma constant $n_0$ (any value). > 2. Choose $w=a^{n_0+1}b^{n_0}\in L$, with $\lvert w\rvert=2n_0+1\ge n_0$. > 3. Let $w=yxz$ be any decomposition with (i) and (ii). By (i), $\lvert yx\rvert\le n_0$, so $yx$ consists only of $a$'s and $x=a^m$. By (ii), $m\ge1$. > 4. Since $w\in L$, (iii) requires $yx^kz=a^{n_0+1+(k-1)m}b^{n_0}\in L$ for all $k$. > 5. **Pumping up** ($k\ge2$) only adds $a$'s, and $n>m$ stays true, so there is no contradiction. > 6. **Pump down** with $k=0$: $yz=a^{n_0+1-m}b^{n_0}$. Since $m\ge1$, $n_0+1-m\le n_0$, so $\#a\le\#b$ and $yz\notin L$. > 7. Contradiction to (iii), so $L$ is not regular. ∎ > > Lesson: choose $k$ according to which direction actually leaves $L$. $k=0$ is allowed. **Question 3.** A student "proves" that $L=\{0^{2n}\mid n\in\mathbb{N}\}$ is not regular: "Let $n_0$ be the constant, choose $w=0^{2n_0}$, take $y=\lambda$, $x=0$, $z=0^{2n_0-1}$. Then $yx^2z=0^{2n_0+1}\notin L$, a contradiction." Find the error, and show that the Pumping Lemma does hold for this $w$. > [!question]- Solution to Question 3 > > **Error:** the student **chose the decomposition**. The lemma only states that **some** decomposition with (i)–(iii) exists. To refute it you must show that **every** decomposition satisfying (i) and (ii) violates (iii). > > In fact $L=(00)^*$ is regular (2-state DFA, so $n_0=2$). For $w=0^{2n_0}$ the decomposition $y=\lambda$, $x=00$, $z=0^{2n_0-2}$ satisfies: > - (i) $\lvert yx\rvert=2\le n_0$; > - (ii) $\lvert x\rvert=2\ge1$; > - (iii) $yx^kz=0^{2n_0-2+2k}$ always has even length, so all pumped words are in $L$ ✓. > > A regular language can never be "refuted" by the Pumping Lemma. **Question 4.** Using Lemma 3.3 with the words $0^{1},0^{4},\dots,0^{(m+1)^2}$ (i.e. $0^{i^2}$ for $i=1,\dots,m+1$) to show $L_{sq}$ non-regular, a student picks $z=0^{2j+1}$ for the colliding pair $0^{i^2},0^{j^2}$ with $i<j$. Show that this choice can fail, and give a correct $z$ with full justification. > [!question]- Solution to Question 4 > > **Failure:** $0^{j^2}z=0^{(j+1)^2}\in L_{sq}$, but $0^{i^2}z=0^{i^2+2j+1}$ may also be a square. For $i=1,j=7$: $1+15=16=4^2$. Both words are then in $L_{sq}$, and there is no contradiction. Since $i,j$ are arbitrary (you don't control which pair collides), the argument must work for **all** $i<j$, and this one doesn't. > > **Correct choice:** $z=0^{2i+1}$. > - $0^{i^2}z=0^{i^2+2i+1}=0^{(i+1)^2}\in L_{sq}$. > - $0^{j^2}z=0^{j^2+2i+1}$, and $j^2<j^2+2i+1<j^2+2j+1=(j+1)^2$ because $0<2i+1$ and $i<j$. Strictly between consecutive squares, so not a square, so $0^{j^2}z\notin L_{sq}$. > > This contradicts Lemma 3.3. ∎ **Question 5.** Give an NFA with 3 states for $L=\{w\in\{0,1\}^*\mid w \text{ ends with } 01\}$. List **all** computations on $101$ and on $1010$, and decide acceptance. > [!question]- Solution to Question 5 > > **NFA:** > - $q_0$: $0\to\{q_0,q_1\}$, $1\to\{q_0\}$ > - $q_1$: $1\to\{q_2\}$, $0\to\emptyset$ > - $q_2$ (accepting): $0\to\emptyset$, $1\to\emptyset$ > > Idea: stay in $q_0$, and "guess" that the current $0$ starts the final $01$. > > **On $101$** (choices only arise when reading a $0$ in $q_0$): > - $q_0\xrightarrow{1}q_0\xrightarrow{0}q_0\xrightarrow{1}q_0$: ends in $q_0\notin F$, rejecting. > - $q_0\xrightarrow{1}q_0\xrightarrow{0}q_1\xrightarrow{1}q_2$: ends in $q_2\in F$, **accepting**. > > One accepting computation exists, so $101\in L$ ✓. > > **On $1010$:** > - stay in $q_0$ throughout: ends in $q_0$, rejecting; > - jump at the 2nd symbol: $q_0\to q_0\to q_1\to q_2$, then reading $0$ from $q_2$ gives $\emptyset$, stuck; > - jump at the 4th symbol: $q_0\to q_0\to q_0\to q_0\to q_1$, ends in $q_1\notin F$, rejecting. > > No computation accepts, so $1010\notin L$ ✓ (it ends with $10$).