Week 2 (22. & 25. Sept. 2026)- Formal Languages, Decision Problems, Finite Automata

Covered:

• Lecture 3 (Tue 22.09.): recap of the canonical order; formal languages (Hromkovič Ch. 2, towards Def. 2.9); Lemma 2.1 and Lemma 2.2; algorithmic problems and decision problems; introduction to finite automata (Ch. 3, Def. 3.1, configurations, steps, computations, $L(M)$); exercise “ends with $aaa$ or $bba$” (left as a cliffhanger).
• Lecture 4 (Fri 25.09.): the $aaa$/$bba$ automaton completed; table representation; Def. 3.2 (${⊢}_M^{\ast }$, $\hat{\delta }$); regular languages; Lemma 3.1 with the class method; worked example $L_{0010}$ (infix, prefix, suffix); §3.3 Simulation (product automaton).

Organisational remarks from Week 2

• The handwritten notes are uploaded. The lecturer recommends not copying everything down but following along critically, since the book contains everything in typeset form.
• Week 1’s overview put the lecture about 30–45 minutes behind the usual schedule. This is being caught up; you are not expected to work ahead.
• Explicit exam hints (first midterm), stated as “very likely” but not promised:
  • given a language, construct a finite automaton;
  • give the class $Kl[p]$ of every state;
  • the product construction: “very mechanical, easy points”;
  • prove or disprove identities between languages (Lemma 2.1/2.2 style), as a “typical warm-up task”.
• Old midterms are available from the VIS (the transcript says “FIS”). The lecturer recommends looking at them.
• Automaton minimisation is not part of this course and will not be asked.

---

1. Executive Overview & Core Objectives

Week 2 builds the formal ground for “problem” and “computation”. A language is any set of words; a decision problem asks whether a given word belongs to a language. The first, deliberately very weak model of computation is the deterministic finite automaton (DFA): it reads the input exactly once, left to right, with a read-only head, and remembers only which of finitely many states it is in. You learn to describe its computations formally (configurations, steps, ${⊢}_M^{\ast }$, $\hat{\delta }$), to prove that an automaton accepts exactly a given language (class method plus induction), and to combine automata via the product construction.

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

• define language, complement, $L_{\varnothing }$, $L_{\lambda }$, concatenation $L_1{L}_2$, powers $L^i$, $L^{\ast }$, $L^{+}$, and compute them for small examples, including all edge cases with $\varnothing$ and $\{\lambda \}$;
• prove language identities by double inclusion, and refute false ones with a counterexample (Lemma 2.1, Lemma 2.2);
• define a decision problem $(\Sigma ,L)$ and what it means for an algorithm to solve (recognise) it;
• state Def. 3.1 (DFA as a 5-tuple), and define configuration, start/end configuration, step ${⊢}_M$, computation, accepting/rejecting computation, and $L(M)$;
• state Def. 3.2 (${⊢}_M^{\ast }$ and $\hat{\delta }$) and write $L(M)$ in both forms;
• construct complete DFAs for “contains / starts with / ends with a pattern” languages;
• define the classes $Kl[p]$, describe them for a given automaton, and use them in an induction proof (Lemma 3.1);
• build product automata for $L_1\cup L_2$, $L_1\cap L_2$ and $L_1-L_2$.

---

2. Core Concepts & Formal Definitions

2.1 Recap: canonical order (kanonische Ordnung)

Definition (kanonische Ordnung)

Let $\Sigma =\{s_1,\dots ,s_m\}$ with a total order $s_1<s_2<\cdots <s_m$. For $u,v\in {\Sigma }^{\ast }$:
$u<v⟺|u|<|v|\text{or}(|u|=|v|,u=x{s}_i{u}^{\prime },v=x{s}_j{v}^{\prime },s_i<s_j)$
where $x,u^{\prime },v^{\prime }\in {\Sigma }^{\ast }$ and $s_i,s_j\in \Sigma$. Criterion 1 is length; criterion 2 is lexicographic order at the first difference.
Example ($a<b$): $a<b$, $aab<aba$, $bb<aaa$.
Over ${\Sigma }_{\text{bool}}$: $\lambda ,0,1,00,01,10,11,000,\dots$

Why length first? Pure lexicographic order lists $0,00,000,\dots$ forever and never reaches a word containing a 1. The canonical order lists every word at a finite position.

Exam Trap: a misspoken example

The transcript says “the word $bb$ is smaller than the word $aa$”. That is wrong: both have length 2, they first differ at position 1, and $a<b$, so $aa<bb$. The handwritten notes have the correct example $bb<aaa$, which holds by length.

2.2 Formal languages (formale Sprachen, Hromkovič Ch. 2, Def. 2.9)

Definition 2.9 (Sprache, Komplement, leere Sprache)

Let $\Sigma$ be an alphabet.

• Every subset $L\subseteq {\Sigma }^{\ast }$ is a language (Sprache) over $\Sigma$.
• The complement (Komplement) of $L$ is $L^C={\Sigma }^{\ast }-L$. It is always taken with respect to the alphabet $\Sigma$.
• $L_{\varnothing }=\varnothing$ is the empty language (leere Sprache).
• $L_{\lambda }=\{\lambda \}$ is the language containing only the empty word.
• $L_{\varnothing }\ne L_{\lambda }$: the first has no word, the second has one word (of length 0).

Definition 2.9 continued (Konkatenation, Potenzen, Kleene-Stern)

For languages $L,L_1,L_2\subseteq {\Sigma }^{\ast }$:

• Concatenation (Konkatenation): $L_1{L}_2=L_1\cdot L_2=\{uv\mid u\in L_1,v\in L_2\}$.
• Powers: $L^0=L_{\lambda }=\{\lambda \}$, $L^1=L$, $L^{i+1}=L\cdot L^i$.
• Kleene star: $L^{\ast }={\bigcup }_{i\in \mathbb{N}}{L}^i$.
• Kleene plus: $L^{+}=L\cdot L^{\ast }$.

Convention: $\mathbb{N}$ always includes 0 in this course. “In a midterm or exam, $\mathbb{N}$ contains 0.”

Rules worth memorising (the edge cases came up repeatedly in the student questions):

Expression	Value	Reason
$L\cdot \varnothing =\varnothing \cdot L$	$\varnothing$	no $v$ can be taken from $\varnothing$
$L\cdot L_{\lambda }=L_{\lambda }\cdot L$	$L$	$u\lambda =u$ for every $u$
$L^0$ (for every $L$, including $\varnothing$)	$\{\lambda \}$	by definition
${\varnothing }^{\ast }$	$\{\lambda \}$	only ${\varnothing }^0$ is non-empty
${\varnothing }^{+}$	$\varnothing$	$\varnothing \cdot {\varnothing }^{\ast }=\varnothing$
$\{\lambda {\}}^{\ast }$ and $\{\lambda {\}}^{+}$	$\{\lambda \}$	$\lambda \lambda =\lambda$
$\lambda \in L^{\ast }$	always	$L^0\subseteq L^{\ast }$
$\lambda \in L^{+}$	iff $\lambda \in L$	see §3.3
$L_1{L}_2$ vs. $L_2{L}_1$	in general different	concatenation of words is not commutative

Exam Trap: two statements made in the lecture and corrected

1. Before the break the lecturer said firmly that $\lambda$ is never in $L^{+}$. After the break he retracted this (“that is simply wrong”). With $L^{+}=L\cdot L^{\ast }$: $\lambda \in L^{+}⟺\lambda \in L$. So $L^{+}=L^{\ast }-\{\lambda \}$ holds only if $\lambda \notin L$.
2. Answering a student, he said ”$L_{\lambda }^{\ast }$ is empty”. That is a slip: $L_{\lambda }^{\ast }=\{\lambda \}=L_{\lambda }$, which is non-empty. ($L_{\lambda }$ is a non-empty language whose only word is empty.)

Also, the first version on the board wrote $L^{\ast }=\bigcup L$; a student pointed out it must be ${\bigcup }_i{L}^i$.

2.3 Algorithmic problems and decision problems

Algorithm (still informal): a deterministic procedure (no randomness, no quantum states) that computes, for every input, an output. Formally, it describes a map
$A:{\Sigma }_{\text{in}}^{\ast }\to {\Sigma }_{\text{out}}^{\ast }.$
What exactly counts as an algorithm stays open until Turing machines are defined. Python, C++, recipes and directions are all intuitive examples.

Definition (Entscheidungsproblem)

Let $\Sigma$ be an alphabet and $L\subseteq {\Sigma }^{\ast }$. The decision problem $(\Sigma ,L)$ is: for every $x\in {\Sigma }^{\ast }$, decide whether $x\in L$ or $x\notin L$.
An algorithm $A$ solves $(\Sigma ,L)$ if for all $x\in {\Sigma }^{\ast }$:
$A(x)=\{\begin{array}{ll}1& \text{if }x\in L\\ 0& \text{if }x\notin L\end{array}$
We then say ”$A$ recognises (erkennt) / decides (entscheidet) the language $L$”.
The lecture did not give this a number; look it up in Ch. 2 after Def. 2.9.

Examples:

• $L_{\text{Prim}}=\{x\in {\Sigma }_{\text{bool}}^{\ast }\mid \text{Nummer}(x)\text{ is a prime}\}$ (primality testing as a decision problem).
• $L_{\text{TSP}}$: binary encodings of adjacency matrices of graphs with a Hamiltonian cycle.
• Analogous languages for spanning trees, cliques, independent sets, …

Remarks:

• Finite languages are “boring” (you can list them). ${\Sigma }^{\ast }$ is trivial (always answer 1). The interesting languages are infinite, and some of them are undecidable (later).
• This is exactly the “Entscheidungsproblem” from the title of Turing’s 1936 paper.

Exam Trap: leading zeros depend on the definition

In Lecture 3 the lecturer said that for decimal encodings of primes, strings with leading zeros (e.g. $000000000013$) should not count as encoding 13. They would then belong to the complement.
But the notes define $L_{\text{Prim}}$ via Nummer(x), and $\text{Nummer}(00101)=5$ is prime, so $00101\in L_{\text{Prim}}$ under that definition.
These are two different languages. In an exam, use the definition exactly as stated in the task.

2.4 Finite automata (endliche Automaten, Hromkovič Ch. 3)

Model (a strongly restricted Turing machine):

• A finite control (endliche Kontrolle): the “logic”, i.e. finitely many states.
• An input tape with one symbol per cell, read by a read-only head (Lesekopf):
  • no writing (unlike a TM’s read/write head);
  • only left to right, one cell per step, never backwards;
  • the input is read exactly once, and the computation ends after the last symbol.
• The only memory is which state it is in.
• Output is only yes/no: did it end in an accepting state?

Why study such a weak model?

1. It formalises computation cleanly. Configuration, step and computation all reappear for TMs.
2. Nondeterminism is easy to understand here first.
3. DFAs are exactly as expressive as regular expressions (not proved in this course).

Definition 3.1 (deterministischer endlicher Automat, EA)

A (deterministic) finite automaton is a 5-tuple $M=(Q,\Sigma ,\delta ,q_0,F)$ where:

• $Q$ is a finite set of states (Zustände), usually $q_0,\dots ,q_{n-1}$;
• $\Sigma$ is an alphabet, the input alphabet (Eingabealphabet);
• $q_0\in Q$ is the unique start state (Anfangszustand);
• $F\subseteq Q$ is the set of accepting states (akzeptierende Zustände, also final states or Endzustände);
• $\delta :Q\times \Sigma \to Q$ is the transition function (Übergangsfunktion, Transitionsfunktion). It is a total function, e.g. $\delta (q_1,0)=q_2$.

“Finite” because all components are finite, in particular $|Q|$.

Diagram conventions (Zustandsdiagramm):

• a state is a circle;
• the start state has an incoming arrow from nowhere;
• accepting states have a double circle;
• an edge $q\stackrel{a}{\to }p$ means $\delta (q,a)=p$;
• several letters may share one edge ("$0,1$").

Table representation (Tabellendarstellung): one row per state, one column per letter, and the entry in row $q$, column $a$ is $\delta (q,a)$.

Exam Trap: rules for drawing DFAs

• Complete: from every state, for every letter, there is exactly one outgoing edge. Not zero (the automaton would get stuck) and not two (ambiguity). Nondeterministic automata come later and do allow this.
• Only letters on edges, never $\lambda$ and never words. ($\lambda$-automata exist as an extension but are not DFAs.)
• To label “all letters”, list them ($0,1$). Don’t write $\ast$, which already means Kleene star. (The lecturer’s remarks about a $\Sigma$ label were contradictory in the transcript, so listing the letters is the safe choice.)
• Mark the start state, which must be unique.
• The lecturer’s sanity check “at least one accepting state, otherwise it’s strange” is a heuristic, not a rule. $F=\varnothing$ is a valid DFA; it accepts $\varnothing$.
• Useful fact: $\lambda \in L(M)⟺q_0\in F$.

Definitions (Konfiguration, Schritt, Berechnung — part of Def. 3.1 in the notes)

Let $M=(Q,\Sigma ,\delta ,q_0,F)$ be a DFA.

• A configuration (Konfiguration) of $M$ is an element of $Q\times {\Sigma }^{\ast }$: the current state, plus the remaining input still to be read.
• $(q_0,x)$ is the start configuration (Startkonfiguration) of $M$ on $x$.
• Every configuration in $Q\times \{\lambda \}$ is an end configuration (Endkonfiguration). It is accepting if it is in $F\times \{\lambda \}$ and rejecting (verwerfend) if it is in $(Q-F)\times \{\lambda \}$.
• A step (Schritt) of $M$ is the relation ${⊢}_M\subseteq (Q\times {\Sigma }^{\ast })\times (Q\times {\Sigma }^{\ast })$ defined by
  $(q,w){⊢}_M(p,x)⟺w=ax,a\in \Sigma ,\delta (q,a)=p$
• A computation (Berechnung) $C$ of $M$ is a finite sequence $C=C_0,C_1,\dots ,C_n$ of configurations with $C_i{⊢}_M{C}_{i+1}$ for all $0\le i<n$.
• It is a computation of $M$ on input $x\in {\Sigma }^{\ast }$ if $C_0=(q_0,x)$ and $C_n\in Q\times \{\lambda \}$.
• If $C_n\in F\times \{\lambda \}$, $C$ is an accepting computation and $M$ accepts $x$. Otherwise it is a rejecting computation (verwerfende Berechnung).
• The language accepted by $M$ is
  $L(M)=\{w\in {\Sigma }^{\ast }\mid \text{the computation of }M\text{ on }w\text{ ends in an end configuration }(q,\lambda )\text{ with }q\in F\}$

Remarks:

• For a DFA, the computation on $x$ is unique and has exactly $|x|$ steps, so it is automatically finite. For TMs, finiteness will not be automatic.
• Student question: is $(q_0,\text{suffix})$, reached in the middle of a run, a start configuration? Only for the suffix as an input of its own, not for the original word.

Definition 3.2 ( ${⊢}_M^{\ast }$ und $\hat{\delta }$)

Let $M=(Q,\Sigma ,\delta ,q_0,F)$ be a DFA.

1. ${⊢}_M^{\ast }$ is the reflexive and transitive closure (reflexive und transitive Hülle) of ${⊢}_M$:
   $(q,w){⊢}_M^{\ast }(p,u)⟺(p=q\text{ and }w=u)\text{ or }\exists k\in \mathbb{N}-\{0\}:$
   • (i) $w=a_1\cdots a_{k}u$ with $a_i\in \Sigma$, and
   • (ii) there exist $r_1,\dots ,r_{k-1}\in Q$ with $(q,w){⊢}_M(r_1,a_2\cdots a_{k}u){⊢}_M(r_2,a_3\cdots a_{k}u){⊢}_M\cdots {⊢}_M(p,u)$.
2. $\hat{\delta }:Q\times {\Sigma }^{\ast }\to Q$ (extended transition function) is defined by:
   • (i) $\hat{\delta }(q,\lambda )=q$ for all $q\in Q$;
   • (ii) $\hat{\delta }(q,wa)=\delta (\hat{\delta }(q,w),a)$ for all $a\in \Sigma$, $w\in {\Sigma }^{\ast }$, $q\in Q$.

Intuitively: ${⊢}_M$ is one step with one letter; ${⊢}_M^{\ast }$ is any number of steps (including zero); $\hat{\delta }$ gives the state reached after reading a whole word.

The language of a DFA, two equivalent forms

$L(M)=\{w\in {\Sigma }^{\ast }\mid \hat{\delta }(q_0,w)\in F\}=\{w\in {\Sigma }^{\ast }\mid (q_0,w){⊢}_M^{\ast }(p,\lambda )\text{ with }p\in F\}$
Because $\delta$ is total, $\hat{\delta }(q_0,w)$ is defined for every $w$: the automaton never gets stuck. It ends in a state that is either in $F$ (accept) or not (reject).

Exam Trap: $\hat{\delta }$ recurses on the LAST letter

A student first proposed a version that splits off the first letter. The book’s (and lecture’s) recursion splits off the last letter: $\hat{\delta }(q,wa)=\delta (\hat{\delta }(q,w),a)$. A front-splitting version $\hat{\delta }(q,aw)=\hat{\delta }(\delta (q,a),w)$ defines the same function, but induction proofs in this course (Lemma 3.1) use the back-splitting form. Use the book’s.

Definition (reguläre Sprachen)

A language $L$ is regular (regulär) if there is a DFA $M$ with $L(M)=L$. The class of all regular languages is $\mathcal{L}(EA)=\{L(M)\mid M\text{ is a DFA}\}$; check the book’s exact symbol.
Facts:

• every DFA accepts exactly one language;
• a language has many DFAs (different sizes and structures), and “the” correct automaton does not exist;
• non-regular languages exist (proved later);
• regular languages = languages describable by regular expressions (mentioned only, not covered).

2.5 Classes of an automaton (Klassen)

Definition ( $Kl[p]$)

For a DFA $M$ and a state $p\in Q$:
$Kl[p]=\{w\in {\Sigma }^{\ast }\mid \hat{\delta }(q_0,w)=p\}=\{w\in {\Sigma }^{\ast }\mid (q_0,w){⊢}_M^{\ast }(p,\lambda )\}$
the set of all words that lead from the start state to $p$.

Properties

• The classes are pairwise disjoint, because $\delta$ is a function and so every word ends in exactly one state.
• ${\bigcup }_{p\in Q}Kl[p]={\Sigma }^{\ast }$, so $M$ partitions ${\Sigma }^{\ast }$ into classes, one per state.
• $L(M)={\bigcup }_{p\in F}Kl[p]$.
• (The lecture did not use the name “Nerode congruence” and it is not needed here.)

Exam Trap: classes need not be infinite or non-empty

The lecturer said the classes are “obviously infinite, because ${\Sigma }^{\ast }$ is infinite”. That holds for the examples shown, but not in general:

• in the prefix automaton for $0010$ (§4.3), $Kl[p_0]=\{\lambda \}$, which is finite;
• a state unreachable from $q_0$ has an empty class.

So ”$M$ partitions ${\Sigma }^{\ast }$ into $|Q|$ classes” is strictly true only if all states are reachable; otherwise some classes are empty. Only $\bigcup Kl[p]={\Sigma }^{\ast }$ (the classes cover everything) is guaranteed.

2.6 Simulation: the product automaton (Produktautomat, §3.3)

Idea: to decide membership in a combination of $L_1=L(M_1)$ and $L_2=L(M_2)$ (same alphabet), run both automata simultaneously on the input. A state of the new automaton is a pair (state of $M_1$, state of $M_2$).

Definition (product automaton — formalised in the next lecture)

Let $M_1=(Q_1,\Sigma ,{\delta }_1,q_0,F_1)$ and $M_2=(Q_2,\Sigma ,{\delta }_2,p_0,F_2)$ be DFAs over the same $\Sigma$. The product automaton is
$M=(Q_1\times Q_2,\Sigma ,\delta ,(q_0,p_0),F)$
$\delta ((q,p),a)=({\delta }_1(q,a),{\delta }_2(p,a))$
and the choice of $F$ decides the language:

Target language	Accepting states $F$
$L_1\cup L_2$	$\{(q,p)\mid q\in F_1\text{ or }p\in F_2\}$ (inclusive or)
$L_1\cap L_2$	$F_1\times F_2$
$L_1-L_2$	$F_1\times (Q_2-F_2)$ (lecturer deferred this to next week)

$|Q|=|Q_1|\cdot |Q_2|$; unreachable pairs may be omitted.

In the drawing: $M_1$‘s state determines the row, $M_2$‘s state the column. Each transition moves “vertically” as $M_1$ does and “horizontally” as $M_2$ does, at the same time.

---

3. Step-by-Step Derivations & Mathematical Proofs

3.1 Lemma 2.1: concatenation distributes over union

Lemma 2.1

For languages $L_1,L_2,L_3$ over $\Sigma$:
$L_1{L}_2\cup L_1{L}_3=L_1(L_2\cup L_3)$

Standard method: equality of sets by double inclusion.

(1) "$\subseteq$". It suffices to show $L_1{L}_2\subseteq L_1(L_2\cup L_3)$ and $L_1{L}_3\subseteq L_1(L_2\cup L_3)$.
$L_1{L}_2=\{xy\mid x\in L_1\wedge y\in L_2\}\subseteq \{xy\mid x\in L_1\wedge y\in L_2\cup L_3\}=L_1(L_2\cup L_3)$

• The first equality is the definition of concatenation.
• The inclusion holds because $y\in L_2$ implies $y\in L_2\cup L_3$: we only weaken the condition.
• The last equality is the definition of concatenation again.

$L_1{L}_3\subseteq L_1(L_2\cup L_3)$ is analogous. A union of two subsets is a subset, so $L_1{L}_2\cup L_1{L}_3\subseteq L_1(L_2\cup L_3)$.

(2) "$\supseteq$". This was skipped in the lecture as “trivial”; here it is in full. Let $w\in L_1(L_2\cup L_3)$. By definition $w=xy$ with $x\in L_1$ and $y\in L_2\cup L_3$.

• Case $y\in L_2$: then $w=xy\in L_1{L}_2$.
• Case $y\in L_3$: then $w=xy\in L_1{L}_3$.

In both cases $w\in L_1{L}_2\cup L_1{L}_3$. ∎

3.2 Lemma 2.2: concatenation and intersection (only one inclusion)

Lemma 2.2

$L_1(L_2\cap L_3)\subseteq L_1{L}_2\cap L_1{L}_3$
and in general not "$\supseteq$".

Proof of "$\subseteq$": let $w\in L_1(L_2\cap L_3)$, so $w=xy$ with $x\in L_1$, $y\in L_2$ and $y\in L_3$. Then $w=xy\in L_1{L}_2$ and $w=xy\in L_1{L}_3$, so $w$ is in the intersection. ∎

Counterexample for "$\supseteq$". This one is my own; the book’s may differ. Over ${\Sigma }_{\text{bool}}$ take $L_1=\{\lambda ,0\}$, $L_2=\{0\}$, $L_3=\{00\}$.

• $L_2\cap L_3=\varnothing$, so $L_1(L_2\cap L_3)=L_1\cdot \varnothing =\varnothing$.
• $L_1{L}_2=\{0,00\}$ and $L_1{L}_3=\{00,000\}$, so $L_1{L}_2\cap L_1{L}_3=\{00\}\ne \varnothing$.

So $L_1{L}_2\cap L_1{L}_3⊈L_1(L_2\cap L_3)$.

Intuition: why intersection breaks

A word can have several factorisations. $00=\lambda \cdot 00$ (using $00\in L_3$) and $00=0\cdot 0$ (using $0\in L_2$). Being in both $L_1{L}_2$ and $L_1{L}_3$ may be witnessed by different splits. $L_1(L_2\cap L_3)$ needs one split whose second part is in both. For union this problem does not arise, because you only need one split anyway.

Exam Trap: proving vs. refuting language identities

• To prove an identity: show both inclusions, element by element, using the definitions.
• To refute one: one concrete counterexample (specific finite languages plus one word) is enough and is the expected answer.

3.3 $\lambda \in L^{+}⟺\lambda \in L$

• "$\Leftarrow$": if $\lambda \in L$, then $\lambda =\lambda \cdot \lambda$ with $\lambda \in L$ and $\lambda \in L^0\subseteq L^{\ast }$. So $\lambda \in L\cdot L^{\ast }=L^{+}$.
• "$\Rightarrow$": if $\lambda \in L^{+}=L\cdot L^{\ast }$, then $\lambda =uv$ with $u\in L$, $v\in L^{\ast }$. Since $|u|+|v|=0$, $u=\lambda$. So $\lambda \in L$. ∎

3.4 Lemma 3.1 (class method plus induction)

The automaton $M$ over ${\Sigma }_{\text{bool}}$ (labels as in the Friday lecture and the book):

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

Reading a $1$ toggles $q_0\leftrightarrow q_1$ and $q_2\leftrightarrow q_3$; reading a $0$ toggles $q_0\leftrightarrow q_2$ and $q_1\leftrightarrow q_3$. $F=\{q_0,q_3\}$.

Lemma 3.1

$L(M)=\{w\in \{0,1{\}}^{\ast }\mid |w{|}_0+|w{|}_1\equiv 0(\mathrm{mod}2)\}$

Proof idea: for each state, guess its class, prove the guess by induction on $|w|$, then take the union over $F$.

Step 1: claim the classes.

• $Kl[q_0]=\{w\mid |w{|}_0\text{ even and }|w{|}_1\text{ even}\}$
• $Kl[q_1]=\{w\mid |w{|}_0\text{ even and }|w{|}_1\text{ odd}\}$
• $Kl[q_2]=\{w\mid |w{|}_0\text{ odd and }|w{|}_1\text{ even}\}$
• $Kl[q_3]=\{w\mid |w{|}_0\text{ odd and }|w{|}_1\text{ odd}\}$

Step 2: the claim implies the lemma.
$L(M)=Kl[q_0]\cup Kl[q_3]=\{w\mid \text{both parities even, or both odd}\}=\{w\mid |w{|}_0+|w{|}_1\equiv 0(\text{mod }2)\}$
since even + even and odd + odd are even, while mixed parities give odd.

Step 3: prove the claim by induction on $|w|$.

Base case (Induktionsanfang). The lecture checked all words of length $\le 2$. Only length 0 is actually needed (see the remark below), but the table is a useful check:

$w$	$\hat{\delta }(q_0,w)$	parities $(|w{|}_0,|w{|}_1)$	class matches?
$\lambda$	$q_0$	(even, even)	✓ $Kl[q_0]$
$1$	$q_1$	(even, odd)	✓ $Kl[q_1]$
$0$	$q_2$	(odd, even)	✓ $Kl[q_2]$
$00$	$q_0$	(even, even)	✓
$01$	$q_3$	(odd, odd)	✓
$10$	$q_3$	(odd, odd)	✓
$11$	$q_0$	(even, even)	✓

Induction hypothesis (Induktionsannahme): the claim holds for all $x\in {\Sigma }_{\text{bool}}^{\ast }$ with $|x|\le i$.

Induction step (Induktionsschritt): let $w\in ({\Sigma }_{\text{bool}}{)}^{i+1}$, written $w=za$ with $|z|=i$ and $a\in \{0,1\}$. By Def. 3.2(ii),
$\hat{\delta }(q_0,za)=\delta (\hat{\delta }(q_0,z),a)$
By the hypothesis, $\hat{\delta }(q_0,z)$ is the state matching $z$‘s parities. Appending $a$ flips exactly one parity: the 0-parity if $a=0$, the 1-parity if $a=1$. There are four cases by the parities of $z$; the lecture did (a) and left the others as “analogous”.

• (a) $|z{|}_0$, $|z{|}_1$ both even, so $\hat{\delta }(q_0,z)=q_0$. Then $\hat{\delta }(q_0,za)=\delta (q_0,a)$, which is $q_1$ if $a=1$ (now $|z1{|}_0$ even, $|z1{|}_1$ odd ✓) and $q_2$ if $a=0$ ($|z0{|}_0$ odd, $|z0{|}_1$ even ✓).
• (b) $|z{|}_0$ even, $|z{|}_1$ odd, so the state is $q_1$. $\delta (q_1,1)=q_0$: both even ✓. $\delta (q_1,0)=q_3$: both odd ✓.
• (c) $|z{|}_0$ odd, $|z{|}_1$ even, so the state is $q_2$. $\delta (q_2,0)=q_0$: both even ✓. $\delta (q_2,1)=q_3$: both odd ✓.
• (d) both odd, so the state is $q_3$. $\delta (q_3,0)=q_1$: (even, odd) ✓. $\delta (q_3,1)=q_2$: (odd, even) ✓.

In every case $w$ lands in the correct class. ∎

Intuition: why the example is "too big"

Several students noticed (and the lecturer agreed) that the statement only depends on $|w|$ being even, so a 2-state automaton suffices. The base case $\lambda$ alone would also suffice, and simple (not strong) induction is enough. The 4-state version and the extended base case were kept for didactic reasons, to show the method with four genuinely different classes. Later automata will not be proved at this low level.

Exam Trap: different state labels in the two lectures

The Tuesday lecture used the same automaton shape with $q_2$ and $q_3$ swapped:

• Tuesday: $\delta (q_0,0)=q_3$, $\delta (q_1,0)=q_2$, $F=\{q_0,q_2\}$;
• Friday (and above): $\delta (q_0,0)=q_2$, $\delta (q_1,0)=q_3$, $F=\{q_0,q_3\}$.

Both accept the same language. The Friday version matches the book and the class names in Lemma 3.1. In the Tuesday trace (§4.1), "$q_2$" means “both parities odd”.

3.5 Correctness of the product construction

The lecturer called this “trivial” and will formalise it next lecture. The precise argument:

Claim: for all $w\in {\Sigma }^{\ast }$, $\hat{\delta }((q_0,p_0),w)=({\hat{\delta }}_1(q_0,w),{\hat{\delta }}_2(p_0,w))$.

Induction on $|w|$:

• $w=\lambda$: both sides are $(q_0,p_0)$.
• Step $w=za$:
  $\hat{\delta }((q_0,p_0),za)=\delta (\hat{\delta }((q_0,p_0),z),a)\stackrel{\text{IH}}{=}\delta (({\hat{\delta }}_1(q_0,z),{\hat{\delta }}_2(p_0,z)),a)=({\delta }_1({\hat{\delta }}_1(q_0,z),a),{\delta }_2({\hat{\delta }}_2(p_0,z),a))=({\hat{\delta }}_1(q_0,za),{\hat{\delta }}_2(p_0,za))$

Consequence (union):
$w\in L(M)⟺\hat{\delta }((q_0,p_0),w)\in F⟺{\hat{\delta }}_1(q_0,w)\in F_1\vee {\hat{\delta }}_2(p_0,w)\in F_2⟺w\in L_1\cup L_2$
Intersection ($\wedge$, $F_1\times F_2$) and difference ($F_1\times (Q_2-F_2)$) are proved the same way. ∎

Corollary: regular languages are closed under $\cup$, $\cap$ and $-$.

---

4. Worked Examples & Applications

4.1 Running a DFA: configurations (Lecture 3)

Tuesday’s automaton (labels as described in the trap above): $\delta (q_0,1)=q_1$, $\delta (q_1,0)=q_2$, $\delta (q_2,0)=q_1$, $\delta (q_1,1)=q_0$, $\delta (q_0,0)=q_3$, $F=\{q_0,q_2\}$. Input $10010$:
$(q_0,10010){⊢}_M(q_1,0010){⊢}_M(q_2,010){⊢}_M(q_1,10){⊢}_M(q_0,0){⊢}_M(q_3,\lambda )$

• 5 letters give exactly 5 steps.
• The end configuration is $(q_3,\lambda )$ with $q_3\notin F$, so this is a rejecting computation: $10010\notin L(M)$.
• Consistent with the language: $|10010|=5$ is odd.

4.2 DFA for “ends with $aaa$ or $bba$” (Lecture 3 exercise, completed in Lecture 4)

$L=\{w\in \{a,b{\}}^{\ast }\mid w\text{ ends with }aaa\text{ or }bba\}=\{xaaa,xbba\mid x\in \{a,b{\}}^{\ast }\}$

Design idea (suffix tracking). The state index stores the longest suffix of the input read so far that is a prefix of $aaa$ or $bba$. Storing the whole word is impossible (finitely many states, unboundedly long words) and also unnecessary.

Components:

• $Q=\{q_0,q_a,q_b,q_{aa},q_{bb},q_{aaa},q_{bba}\}$
• $\Sigma =\{a,b\}$
• start state $q_0$
• $F=\{q_{aaa},q_{bba}\}$

$\delta$	$a$	$b$
$\to q_0$	$q_a$	$q_b$
$q_a$	$q_{aa}$	$q_b$
$q_{aa}$	$q_{aaa}$	$q_b$
$q_{aaa}$ (accepting)	$q_{aaa}$ (loop)	$q_b$
$q_b$	$q_a$	$q_{bb}$
$q_{bb}$	$q_{bba}$	$q_{bb}$ (loop)
$q_{bba}$ (accepting)	$q_{aa}$	$q_b$

Why the non-obvious edges are right:

• $q_{aaa}\stackrel{b}{\to }{q}_b$: after $\dots aaab$ the accumulated $a$‘s are useless, but the last $b$ is a prefix of $bba$. Going back to $q_0$ would be wrong: after $aaab$, the input $ba$ must still lead to acceptance ($aaabba$ ends with $bba$). This was the cliffhanger at the end of Lecture 3.
• $q_{aaa}\stackrel{a}{\to }{q}_{aaa}$: still ends with $aaa$.
• $q_{bba}\stackrel{a}{\to }{q}_{aa}$: after $\dots bbaa$, the longest useful suffix is $aa$, since $baa$ and $bbaa$ are not prefixes of either pattern.
• $q_{bba}\stackrel{b}{\to }{q}_b$: after $\dots bbab$, only the final $b$ is useful.
• $q_{bb}\stackrel{b}{\to }{q}_{bb}$: $bbb$ still ends with $bb$.
• $q_b\stackrel{a}{\to }{q}_a$: after $\dots ba$, $ba$ is not a prefix of $bba$, but $a$ is a prefix of $aaa$.
• $q_a\stackrel{b}{\to }{q}_b$ and $q_{aa}\stackrel{b}{\to }{q}_b$: as for $q_{aaa}$.

Final check: every state has exactly one $a$-edge and one $b$-edge ✓; unique start ✓; accepting states marked ✓.

Example: traces

• $aaab$: $q_0\to q_a\to q_{aa}\to q_{aaa}\to q_b$, so reject ✓ (does not end with $aaa$ or $bba$).
• $aaabba$: $\cdots \to q_b\to q_{bb}\to q_{bba}$, so accept ✓.
• $bbaaa$: $q_0\to q_b\to q_{bb}\to q_{bba}\to q_{aa}\to q_{aaa}$, so accept ✓ (ends with $aaa$).

Intuition: suffix patterns are the hard case

Prefix conditions are easy: once you fail, go to a sink state. Infix conditions are medium: after success, stay in an absorbing accepting state. Suffix conditions are the hardest, because after reaching an accepting state you can fall out again, and on a mismatch you must jump back to the right “partial match” state. Never jump back to $q_0$ blindly.

4.3 Pattern $0010$: infix, suffix, prefix (Lecture 4, group exercise)

(a) Infix (Teilwort): $L_{0010}=\{x0010y\mid x,y\in \{0,1{\}}^{\ast }\}$.

$\delta$	$0$	$1$
$\to p_0$	$p_1$	$p_0$
$p_1$	$p_2$	$p_0$
$p_2$	$p_2$	$p_3$
$p_3$	$p_4$	$p_0$
$p_4$ (accepting)	$p_4$	$p_4$

• $p_i$ = “the longest suffix that is a prefix of $0010$ has length $i$”.
• $p_2\stackrel{0}{\to }{p}_2$: $\dots 000$ still ends with $00$.
• $p_3\stackrel{1}{\to }{p}_0$: $\dots 0011$ ends with no prefix of $0010$.
• $p_0\stackrel{1}{\to }{p}_0$: this loop was forgotten on the board and added after a student’s remark.
• $p_4$ is absorbing: once $0010$ has been seen, the word is in $L$ whatever follows.

(b) Suffix ($y=\lambda$): words ending in $0010$. Same as (a) but $p_4$ is not absorbing:

• $p_4\stackrel{0}{\to }{p}_2$: $\dots 00100$ ends with $00$.
• $p_4\stackrel{1}{\to }{p}_0$: $\dots 00101$ ends with no prefix of $0010$.

The lecturer first drew the $0$-edge wrongly and corrected it to $p_2$ during the lecture.

(c) Prefix ($x=\lambda$): words starting with $0010$. Add a sink state (Senke) $q_x$ (“Abfall”):

$\delta$	$0$	$1$
$\to p_0$	$p_1$	$q_x$
$p_1$	$p_2$	$q_x$
$p_2$	$q_x$	$p_3$
$p_3$	$p_4$	$q_x$
$p_4$ (accepting)	$p_4$	$p_4$
$q_x$	$q_x$	$q_x$

There is exactly one chance, the first four letters; any mismatch goes to the non-accepting sink forever. The sink is needed because DFAs must be complete. This is the easiest of the three cases.

Classes for the infix automaton (a). The lecture’s wording is completed here with the condition "$\notin L_{0010}$":

• $Kl[p_0]=\{x\notin L_{0010}\mid$ no non-empty prefix of $0010$ is a suffix of $x\}$ $=\{x\notin L_{0010}\mid x=\lambda$, or $x$ ends with $1$ but not with $001\}$
• $Kl[p_1]=\{x\notin L_{0010}\mid x$ ends with $0$ and no longer prefix of $0010$ is a suffix$\}$ $=\{x\notin L_{0010}\mid x$ ends with $0$ but not with $00\}$
• $Kl[p_2]=\{x\notin L_{0010}\mid x$ ends with $00\}$
• $Kl[p_3]=\{x\notin L_{0010}\mid x$ ends with $001\}$
• $Kl[p_4]=L_{0010}$

Exam Trap: absorbing states and class descriptions

Because $p_4$ is absorbing, every word containing $0010$ ends in $p_4$, including words like $00100$ that also “end with $00$”. So $Kl[p_0],\dots ,Kl[p_3]$ must explicitly exclude $L_{0010}$. Otherwise the classes overlap and the answer is wrong. On the board this condition was written for $p_2$ and $p_3$ but omitted for $p_0$ and $p_1$.
Check that your classes are disjoint, cover ${\Sigma }^{\ast }$, and are consistent with the edges.

4.4 Product automaton (Lecture 4, §3.3)

$M_1$ accepts $L_1=\{w\mid |w{|}_0\text{ even}\}$; the 1s are ignored.

${\delta }_1$	$0$	$1$
$\to q_0$ (accepting)	$q_1$	$q_0$
$q_1$	$q_0$	$q_1$

$M_2$ counts 1s up to 3.

${\delta }_2$	$0$	$1$
$\to p_0$ (accepting)	$p_0$	$p_1$
$p_1$	$p_1$	$p_2$
$p_2$	$p_2$	$p_3$
$p_3$ (accepting)	$p_3$	$p_3$

So $L_2=\{w\mid |w{|}_1=0\text{ or }|w{|}_1\ge 3\}$.

Exam Trap: "three 1s" means "at least three"

The lecture described $M_2$ as accepting “no 1 or three 1s”. Because $p_3$ loops on $1$, it accepts at least three 1s. Always derive the language from the automaton itself, not from a spoken summary.

Product $M$ (rows from $M_1$, columns from $M_2$), start $(q_0,p_0)$:

$\delta$	$0$	$1$
$\to (q_0,p_0)$	$(q_1,p_0)$	$(q_0,p_1)$
$(q_0,p_1)$	$(q_1,p_1)$	$(q_0,p_2)$
$(q_0,p_2)$	$(q_1,p_2)$	$(q_0,p_3)$
$(q_0,p_3)$	$(q_1,p_3)$	$(q_0,p_3)$
$(q_1,p_0)$	$(q_0,p_0)$	$(q_1,p_1)$
$(q_1,p_1)$	$(q_0,p_1)$	$(q_1,p_2)$
$(q_1,p_2)$	$(q_0,p_2)$	$(q_1,p_3)$
$(q_1,p_3)$	$(q_0,p_3)$	$(q_1,p_3)$

$0$ switches the row (as $M_1$ does) and keeps the column ($M_2$ loops on 0, except that from $p_3$ it loops anyway). $1$ keeps the row ($M_1$ loops on 1) and advances the column. In column $p_3$, $1$ loops in both components and $0$ still switches rows.

Trace of $1001$:

• $M_1$: $q_0\to q_0\to q_1\to q_0\to q_0$
• $M_2$: $p_0\to p_1\to p_1\to p_1\to p_2$
• $M$: $(q_0,p_0)\to (q_0,p_1)\to (q_1,p_1)\to (q_0,p_1)\to (q_0,p_2)$

Accepting states:

• $L_1\cup L_2$: the whole $q_0$ row plus $(q_1,p_0)$ and $(q_1,p_3)$. $1001$ ends in $(q_0,p_2)$, so it is accepted (two 0s).
• $L_1\cap L_2$: $F_1\times F_2=\{(q_0,p_0),(q_0,p_3)\}$. $1001$ is rejected (only two 1s).
• $L_1-L_2$ (deferred to next week): $F_1\times (Q_2-F_2)=\{(q_0,p_1),(q_0,p_2)\}$. $1001$ is accepted.

Exam Trap: union means inclusive or

For the union you need all pairs where $M_1$ or $M_2$ accepts, including both, so both accepting columns ($p_0$ and $p_3$) in the non-accepting row. In the lecture only one column was mentioned explicitly (“and then the column”); both are required.

4.5 Student questions

Q: Is $L_1{L}_2$ the same as $L_2{L}_1$?

In general no. The order matters, because words are concatenated in that order. Example: $\{a\}\{b\}=\{ab\}\ne \{ba\}=\{b\}\{a\}$. (For a set such as $\{aa,b\}$ the order of listing elements doesn’t matter; that is a different question.)

Q: May a language contain $\lambda$?

Yes. $\lambda \in L^{\ast }$ always, and $\lambda \in L^{+}$ iff $\lambda \in L$ (see the trap in §2.2).

Q: In $\hat{\delta }(q,wa)$, is $a$ a single letter?

Yes. $a\in \Sigma$, and $\hat{\delta }$ processes the word letter by letter via $\delta$.

---

5. Intuition & Conceptual Bridges

Intuition: a DFA is a program with constant memory

Think of a loop for c in input: state = delta[state][c] followed by return state in F. No counters that grow, no lists, no going back. Designing a DFA means deciding what finite summary of the past is enough for the future: the parity of counts, the longest partial match, “seen the pattern already?”. The classes $Kl[p]$ are exactly these summaries written as sets of words.

Intuition: why parities work but counting does not

$M$ in Lemma 3.1 only needs parities (2 × 2 possibilities). A language like $\{0^n{1}^n\mid n\in \mathbb{N}\}$ would need to remember an unbounded count. That is impossible with finitely many states, which is the preview of non-regular languages next.

Intuition: the product automaton is parallel execution

Running two programs in lockstep on the same input stream needs memory for both states, i.e. a pair. The cost is multiplicative ($|Q_1|\cdot |Q_2|$ states), but the construction is completely mechanical.

Connections:

• Back to Week 1: decision problems as languages are now fully formal ($(\Sigma ,L)$, ”$A$ recognises $L$”). The concatenation and iteration of words lifts directly to languages.
• Regular expressions: the Kleene star $L^{\ast }$ is the regex *. Regular languages are exactly the regex-describable ones (not proved here).
• Ahead:
  • proving languages non-regular (limits of DFAs);
  • nondeterministic finite automata (several or zero edges per letter);
  • extending the model step by step to the Turing machine, where configurations, steps and computations are defined analogously, but computations need not be finite;
  • the formal proof of the product construction and the $L_1-L_2$ case (next lecture);
  • next week: an alternative, more intuitive but larger automaton for infix recognition.

---

6. Summary & Self-Assessment Questions

Cheat table

Concept	Key statement
Language	any $L\subseteq {\Sigma }^{\ast }$
Complement	$L^C={\Sigma }^{\ast }-L$
$L_{\varnothing }$ vs. $L_{\lambda }$	$\varnothing$ vs. $\{\lambda \}$, which are different
Concatenation	$L_1{L}_2=\{uv\mid u\in L_1,v\in L_2\}$, not commutative
Absorbing / neutral	$L\varnothing =\varnothing$, $L\{\lambda \}=L$
Powers	$L^0=\{\lambda \}$, $L^{i+1}=L\cdot L^i$
Star / plus	$L^{\ast }={\bigcup }_{i\in \mathbb{N}}{L}^i$, $L^{+}=L\cdot L^{\ast }$; $\lambda \in L^{+}$ iff $\lambda \in L$
Lemma 2.1	$L_1{L}_2\cup L_1{L}_3=L_1(L_2\cup L_3)$
Lemma 2.2	$L_1(L_2\cap L_3)\subseteq L_1{L}_2\cap L_1{L}_3$, and not $\supseteq$
Decision problem	$(\Sigma ,L)$: decide $x\in L$; $A$ solves it iff $A(x)=1\iff x\in L$
DFA (Def. 3.1)	$(Q,\Sigma ,\delta ,q_0,F)$ with total $\delta :Q\times \Sigma \to Q$
Configuration	element of $Q\times {\Sigma }^{\ast }$; start $(q_0,x)$; end $(q,\lambda )$
Step	$(q,ax){⊢}_M(\delta (q,a),x)$
${⊢}_M^{\ast }$ (Def. 3.2)	reflexive-transitive closure of ${⊢}_M$
$\hat{\delta }$ (Def. 3.2)	$\hat{\delta }(q,\lambda )=q$, $\hat{\delta }(q,wa)=\delta (\hat{\delta }(q,w),a)$
$L(M)$	$\{w\mid \hat{\delta }(q_0,w)\in F\}=\{w\mid (q_0,w){⊢}_M^{\ast }(p,\lambda ),p\in F\}$
Regular	$L=L(M)$ for some DFA $M$
Class	$Kl[p]=\{w\mid \hat{\delta }(q_0,w)=p\}$; the classes partition ${\Sigma }^{\ast }$; $L(M)={\bigcup }_{p\in F}Kl[p]$
Lemma 3.1	the 4-state parity DFA accepts $\{w\mid |w{|}_0+|w{|}_1\text{ even}\}$
Product	$\delta ((q,p),a)=({\delta }_1(q,a),{\delta }_2(p,a))$; $F$ by “or” / “and” / “and not”
DFA checklist	complete, deterministic, letters only on edges, unique marked start, accepting states double-circled

Self-assessment questions

Question 1. Compute: ${\varnothing }^{\ast }$, ${\varnothing }^{+}$, $\{\lambda {\}}^{\ast }$, $\{\lambda {\}}^{+}$, $\{a\}\cdot \varnothing$, $\{a\}\cdot \{\lambda \}$, and $L^3$ for $L=\{aa,b\}$. Then decide: is $\lambda \in \{a,\lambda {\}}^{+}$? Is $\lambda \in \{a{\}}^{+}$?

Solution to Question 1

• ${\varnothing }^{\ast }={\bigcup }_i{\varnothing }^i={\varnothing }^0\cup \varnothing \cup \varnothing \cup \cdots =\{\lambda \}$. Here ${\varnothing }^0=\{\lambda \}$ by definition, and ${\varnothing }^i=\varnothing \cdot {\varnothing }^{i-1}=\varnothing$ for $i\ge 1$.
• ${\varnothing }^{+}=\varnothing \cdot {\varnothing }^{\ast }=\varnothing$ (concatenating with $\varnothing$ gives $\varnothing$).
• $\{\lambda {\}}^{\ast }=\{\lambda \}$ and $\{\lambda {\}}^{+}=\{\lambda \}\cdot \{\lambda \}=\{\lambda \}$, since $\lambda \lambda =\lambda$.
• $\{a\}\cdot \varnothing =\varnothing$ and $\{a\}\cdot \{\lambda \}=\{a\}$.
• $L^2=L\cdot L=\{aaaa,aab,baa,bb\}$.
• $L^3=L\cdot L^2$: prepend $aa$ to get $aaaaaa,aaaab,aabaa,aabb$; prepend $b$ to get $baaaa,baab,bbaa,bbb$. So $L^3=\{aaaaaa,aaaab,aabaa,aabb,baaaa,baab,bbaa,bbb\}$, 8 words, all distinct.
• $\lambda \in \{a,\lambda {\}}^{+}$: yes, because $\lambda \in \{a,\lambda \}$.
• $\lambda \in \{a{\}}^{+}$: no, because $\lambda \notin \{a\}$; every word of $\{a{\}}^{+}$ is $a^i$ with $i\ge 1$.

Question 2. True or false? Prove or give a counterexample.
(a) $(L_1\cup L_2)L_3=L_1{L}_3\cup L_2{L}_3$.
(b) $L^{\ast }{L}^{\ast }=L^{\ast }$.
(c) $(L_1{L}_2{)}^C=L_1^C{L}_2^C$.

Solution to Question 2

(a) True (right distributivity, the mirror of Lemma 2.1).

• $\subseteq$: $w=xy$ with $x\in L_1\cup L_2$, $y\in L_3$. If $x\in L_1$ then $w\in L_1{L}_3$, else $w\in L_2{L}_3$.
• $\supseteq$: $L_1{L}_3=\{xy\mid x\in L_1,y\in L_3\}\subseteq \{xy\mid x\in L_1\cup L_2,y\in L_3\}=(L_1\cup L_2)L_3$, and the same for $L_2{L}_3$.

(b) True.

• $\supseteq$: $w=w\cdot \lambda$ with $w\in L^{\ast }$ and $\lambda \in L^0\subseteq L^{\ast }$.
• $\subseteq$: $w=uv$ with $u\in L^i$, $v\in L^j$. Then $uv\in L^{i+j}\subseteq L^{\ast }$. (That $L^i{L}^j=L^{i+j}$ follows by induction on $i$ from associativity of concatenation.)

(c) False. Take $\Sigma =\{a\}$, $L_1=L_2=\{\lambda \}$. Then $L_1{L}_2=\{\lambda \}$ and $(L_1{L}_2{)}^C=\{a{\}}^{+}$. But $L_1^C=L_2^C=\{a{\}}^{+}$, and $L_1^C{L}_2^C=\{a^i\mid i\ge 2\}$, which does not contain $a$, while $a\in (L_1{L}_2{)}^C$.

Question 3. Construct a complete DFA over $\{a,b\}$ for $L=\{w\mid w\text{ ends with }ab\}$. Give all classes $Kl[p]$ and check that they partition $\{a,b{\}}^{\ast }$. Then give the configuration sequence on input $abb$.

Solution to Question 3

States: $s_0$ (no useful suffix), $s_1$ (ends with $a$), $s_2$ (ends with $ab$, accepting). Transitions:

• $s_0$: $a\to s_1$, $b\to s_0$
• $s_1$: $a\to s_1$, $b\to s_2$
• $s_2$: $a\to s_1$, $b\to s_0$

Why $s_2\stackrel{b}{\to }{s}_0$: after $\dots abb$ the suffix $bb$ contains no prefix of $ab$.
Why $s_2\stackrel{a}{\to }{s}_1$: after $\dots aba$ the suffix $a$ is the prefix of $ab$.

Classes:

• $Kl[s_1]=\{w\mid w\text{ ends with }a\}$
• $Kl[s_2]=\{w\mid w\text{ ends with }ab\}$
• $Kl[s_0]=\{\lambda ,b\}\cup \{w\mid w\text{ ends with }bb\}$, i.e. every other word: $\lambda$, or ending with $b$ but not with $ab$.

These are disjoint (they are distinguished by the last one or two letters) and cover all words: every word is $\lambda$, ends with $a$, or ends with $b$; in the last case its last two letters are $ab$, $bb$, or the word is just $b$. $L(M)=Kl[s_2]$ ✓.

Configurations on $abb$:
$(s_0,abb){⊢}_M(s_1,bb){⊢}_M(s_2,b){⊢}_M(s_0,\lambda )$
$s_0\notin F$, so this is a rejecting computation ✓ ($abb$ does not end with $ab$).

Question 4 (the lecturer’s voluntary task). Let $L_{10}=\{w\in \{0,1{\}}^{\ast }\mid w\text{ contains }10\}$ and $L_{011}=\{w\in \{0,1{\}}^{\ast }\mid w\text{ starts with }011\}$. Build a DFA for each, then use the product construction for $L_{10}\cup L_{011}$.

Solution to Question 4

$M_{10}$: $s_0$ ($0\to s_0$, $1\to s_1$); $s_1$ = “last letter 1, no 10 yet” ($1\to s_1$, $0\to s_2$); $s_2$ accepting and absorbing ($0,1\to s_2$).

$M_{011}$: $t_0$ ($0\to t_1$, $1\to t_x$); $t_1$ ($1\to t_2$, $0\to t_x$); $t_2$ ($1\to t_3$, $0\to t_x$); $t_3$ accepting and absorbing; $t_x$ non-accepting sink.

Product. The full product has $3\cdot 5=15$ states. Starting from $(s_0,t_0)$, only 8 are reachable:

• $(s_0,t_0)$: $0\to (s_0,t_1)$, $1\to (s_1,t_x)$
• $(s_0,t_1)$: $0\to (s_0,t_x)$, $1\to (s_1,t_2)$
• $(s_1,t_2)$: $0\to (s_2,t_x)$, $1\to (s_1,t_3)$
• $(s_1,t_3)$: $0\to (s_2,t_3)$, $1\to (s_1,t_3)$
• $(s_2,t_3)$: $0,1\to (s_2,t_3)$
• $(s_0,t_x)$: $0\to (s_0,t_x)$, $1\to (s_1,t_x)$
• $(s_1,t_x)$: $0\to (s_2,t_x)$, $1\to (s_1,t_x)$
• $(s_2,t_x)$: $0,1\to (s_2,t_x)$

Union: accept where $s_2$ or $t_3$ occurs: $(s_2,t_x)$, $(s_2,t_3)$, $(s_1,t_3)$.

Checks:

• $011$: $(s_0,t_0)\to (s_0,t_1)\to (s_1,t_2)\to (s_1,t_3)$, accept ✓ (starts with $011$, contains no $10$).
• $0001$: ends in $(s_1,t_x)$, reject ✓.
• $110$: $(s_1,t_x)\to (s_1,t_x)\to (s_2,t_x)$, accept ✓ (contains $10$).

Writing all 15 states with the correct accepting set is equally correct; dropping unreachable states is optional.

Question 5. Using the classes of the 4-state parity automaton $M$ from Lemma 3.1, give $\hat{\delta }(q_0,0110100)$ without simulating. Then explain why the induction step must use $\hat{\delta }(q_0,za)=\delta (\hat{\delta }(q_0,z),a)$ and what exactly the induction hypothesis provides.

Solution to Question 5

$w=0110100$: $|w{|}_0=4$ (even) and $|w{|}_1=3$ (odd). The class with (even, odd) is $Kl[q_1]$, so $\hat{\delta }(q_0,w)=q_1$. Since $q_1\notin F$, $w$ is rejected; consistent with $|w|=7$ being odd.

Why that form of the step: Def. 3.2(ii) defines $\hat{\delta }$ by splitting off the last letter. Writing $w=za$ with $|z|=i$ lets you apply the hypothesis to $z$ (length $\le i$). That hypothesis gives $\hat{\delta }(q_0,z)$ = the state matching $z$‘s parities. One application of $\delta$ (a single table lookup) then gives the state for $w$. You must check that $a$ flips exactly the right parity and that the table entry is the matching state, in all four parity cases.