Lexical Analysis: Formalism (Regular Expressions, NFAs, DFAs)

Lexical Analysis: Formalism

Phase 1 of the Compiler Construction pipeline, slides 19–51 (Univ. Duisburg-Essen, Janis Voigtländer, winter term 2026/27, slides version 28.10.2026).

The lecture’s triad for every phase: formalisms → algorithms → tools. For lexing:

Formalisms	regular expressions, finite automata
Algorithms	automata constructions (NFA from regex, DFA from NFA, minimization)
Tools	lexer generators (lex/flex, Alex, …)

The practical side (token streams, longest match, generators) is on practical-lexers. This page is only the mathematical machinery.

Exam relevance. The written exam is planned for 11 March 2027. “Build the NFA for this regex, then decide it by powerset construction, then minimize it” is the single most probable constructive task of the whole course. The exercises on slides 35 and 51 are the canonical drill.

0. Where lexing sits

Slide 13’s compiler structure, phase for phase, with the lecture’s annotations:

Phase	Input	Output	Note from the slides
lexical analysis	program text (characters)	sequence of tokens	”use simple means for simple tasks”
syntactical analysis	tokens	parse tree	works on tokens, never on characters
semantical analysis	parse tree	annotated tree	frontend ends here
intermediate code	annotated tree	IR	”often transformations on intermediate code”
register allocation	IR	IR + machine registers	not covered in this course
machine code	IR	assembly	not covered in this course
assembling & linking	assembly	executable	not covered

Two framing ideas from the slides worth keeping:

• well-defined interfaces, establishing invariants — each phase may assume what the previous one guarantees. The lexer guarantees “the token stream is well-formed w.r.t. the token classes”, so the parser never has to think about whitespace, comments, or characters.
• frontend vs. backend, and written by hand vs. generated. Lexers are the phase where “generated” wins most easily, because the theory section below gives a fully mechanical construction.

Why a separate phase at all (slide 24) — the five justifications:

1. efficiency — simple means for simple tasks; the DFA-driven scanner is a tight loop over a transition table.
2. simplification of subsequent phases — the parser sees ~40 token classes instead of 256 characters.
3. reduced programming effort through decoupling — lexer and parser evolve independently.
4. conceptual clarity — also in the language definition (the language spec has a token layer and a grammar layer).
5. modularity, reusability.

Naive hand-rolled lexing (“check whether a prefix is a number, a keyword, …”) fails on scalability (efficiency and maintainability) and on token boundaries (start/end of tokens resolved ad hoc). Instead: declarative description of lexeme classes + generation of the lexer from that description.

1. Vocabulary of formal languages

The slide-27 definitions, in standard notation:

$$\Sigma \text{nonempty, finite; elements are called symbols (or characters)}$$ $$w\in {\Sigma }^{\ast }\text{a word: a finite sequence of symbols}$$

• the empty word $\epsilon$ is the sequence of length $0$;
• ${\Sigma }^{\ast }$ = set of all words over $\Sigma$, and recursively:
  • $\epsilon \in {\Sigma }^{\ast }$
  • if $w\in {\Sigma }^{\ast }$ and $a\in \Sigma$, then $wa\in {\Sigma }^{\ast }$
  • no further words are in ${\Sigma }^{\ast }$ (i.e. ${\Sigma }^{\ast }$ is the smallest such set — the same “smallest set closed under …” pattern that returns for $\hat{\epsilon }$ and for $S^{\prime }$ below)
• ${\Sigma }^{+}={\Sigma }^{\ast }\setminus \{\epsilon \}$
• concatenation joins two words: $ab\cdot cca=abcca$, with $\epsilon w=w\epsilon =w$
• a language is a subset $L\subseteq {\Sigma }^{\ast }$

Example (slide 28) with $\Sigma =\{a,b,c\}$:

word	$abcca$
${\Sigma }^{\ast }$	$\{\epsilon ,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,\dots \}$
concatenation	$ab\cdot cca=abcca$
language	$\{a^{n}b{c}^n\mid n\ge 0\}$

Meta language vs. object language — the distinction that makes the whole chapter work:

• object language: the language being described — here the lexeme classes of the source language, over the character alphabet.
• meta language: the language used to describe it — here regular expressions, over an alphabet of characters plus the operator symbols ( ) | * ε.

Which is exactly why lexer tools need escaping/quoting (\., "if", [|]): one symbol can be both object and meta symbol. See practical-lexers §3.

Note the teaser on slide 28: $\{a^{n}b{c}^n\}$ — the meta language slot is deliberately left as ”???” and the language is not regular (a finite automaton cannot count). That is the boundary of this chapter, and the reason for the syntactic analysis chapter.

2. Regular expressions

2.1 Syntax (slide 30)

For a given alphabet $\Sigma$, the regular expressions are defined recursively:

1. $\epsilon$ is a regular expression.
2. every $a\in \Sigma$ is a regular expression.
3. if $r$ and $s$ are regular expressions, then $(r\mid s)$ is a regular expression.
4. if $r$ and $s$ are regular expressions, then $(rs)$ — usually written $rs$ — is a regular expression.
5. if $r$ is a regular expression, then $(r{)}^{\ast }$ is a regular expression.

Round brackets clarify grouping. Otherwise the precedence is

$$\underset{\text{binds strongest}}{\underbrace{{}^{\ast }}}>\underbrace{\text{concatenation}}>\underset{\text{binds weakest}}{\underbrace{\mid }}$$

so $a\mid bc$ means $a\mid (bc)$ and not $(a\mid b)c$. This is the one thing that silently produces wrong hand-built NFAs in the exam.

2.2 Semantics, definition A: the language $L(r)$

The recursive set definition (slide 31):

$$\begin{array}{rlrl}L(\epsilon )& =\{\epsilon \}& & \\ L(a)& =\{a\}& & \text{for }a\in \Sigma \\ L(r\mid s)& =L(r)\cup L(s)& & \\ L(rs)& =\{uv\mid u\in L(r),v\in L(s)\}& & \\ L(r^{\ast })& =\{\epsilon \}\cup L(r)\cup L(rr)\cup L(rrr)\cup \dots & & \end{array}$$

Equivalently $L(r^{\ast })={\bigcup }_{n\ge 0}L(r{)}^n$ with $L(r{)}^0=\{\epsilon \}$ and $L(r{)}^{n+1}=L(r{)}^n\cdot L(r)$.

2.3 Semantics, definition B: the derivation relation

The lecture also gives the semantics operationally, as a relation $\Rightarrow$ between regular expressions extended by words. Full rule set (slide 32):

#	Rule	Reading
1	$\epsilon \Rightarrow \epsilon$	blank on the slide — the empty regex derives the empty word
2	$r\mid s\Rightarrow r$	pick the left branch
3	$r\mid s\Rightarrow s$	pick the right branch
4	$rs\Rightarrow r^{\prime }{s}^{\prime }$   if $r\Rightarrow r^{\prime }$ and $s\Rightarrow s^{\prime }$	congruence of concatenation
5	$r^{\ast }\Rightarrow \epsilon$	blank on the slide — a star may derive nothing
6	$r^{\ast }\Rightarrow r{r}^{\ast }$	unfold the star once
7	$r\Rightarrow r$	reflexivity
8	$r\Rightarrow t$   if $r\Rightarrow s$ and $s\Rightarrow t$	transitivity

On the two blanks. In the PDF, the right-hand sides of rules 1 and 5 are visibly empty (everything else on those two lines renders fine, so it is a deliberate in-lecture fill-in, not a font bug). Both are $\epsilon$.

Semantics: “continue deriving until only symbols from the alphabet of the object language remain” — and

$$L(r)=\{w\in {\Sigma }^{\ast }\mid r{\Rightarrow }^{\ast }w\}$$

Worked derivation for slide-35 exercise 1(a), $r=(a\mid b)(c\mid d\mid \epsilon )$, word $ac$:

$$(a\mid b)(c\mid d\mid \epsilon )\Rightarrow a(c\mid d\mid \epsilon )\text{(rule 4 on }rs\text{, then rule 2)}\Rightarrow ac\text{(rule 4 again, then rule 7 stops on the atoms)}$$

The final step legitimately applies rule 7 on the atomic symbols ($a\Rightarrow a$, $c\Rightarrow c$): “only symbols remain”, so nothing further happens.

Why two definitions at all? Definition A is the one you compute with (it is a set recursion, so it feeds directly into the automata constructions); definition B is the one that makes “acceptance of a word” a derivation — which is precisely what the NFA run of §3.2 formalizes. Both yield the same language; that they coincide is the informal statement of Kleene’s theorem (regex ⇔ finite automaton), which is what §4 and §5 prove constructively.

2.4 Abbreviations (slide 33)

The lecture’s abbreviation layer, in LaTeX:

Abbreviation	Meaning	Note
$[a_1{a}_2\dots a_n]$	$(a_1\mid a_2\mid \cdots \mid a_n)$	character class, $a_i\in \Sigma$
$[a-c]$	$(a\mid \cdots \mid c)$	range, requires a known order on $\Sigma$
$r?$	$r\mid \epsilon$	optional
$r^{+}$	$r{r}^{\ast }$	one or more
$r\{n,m\}$	$\underset{n}{\underbrace{r\dots r}}\underset{m-n}{\underbrace{r?\dots r?}}$	for $n\le m$; $r\{n\}$ = exactly $n$, $r\{n,\}$ = at least $n$
$.$	any symbol	tool notation (flex, Alex, …), not in the lecture’s core syntax
$\varnothing$	the empty language	not in the lecture’s syntax either — see the note below

Detail worth knowing. The lecture’s syntax has no $\varnothing$ constructor, only the atoms $\epsilon$ and $a\in \Sigma$. The standard textbook syntax adds $\varnothing$ because it is the neutral element of $\mid$ ($\varnothing \mid r=r$, see §2.6) and the zero of concatenation ($\varnothing r=r\varnothing =\varnothing$). In the exam, use it freely in the algebra part, but never inside an automaton construction — there is no slide-40 template for it.

Lexeme-class examples (slide 33):

• identifiers from lower case letters: $(a\mid b\mid c\mid \cdots \mid z)(a\mid b\mid c\mid \cdots \mid z{)}^{\ast }$
• decimal whole numbers: $0\mid (1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9)(0\mid 1\mid \cdots \mid 9{)}^{\ast }$ — note there is no leading-zero blob, so 007 is not a decimal number in this class; contrast slide 35 exercise 4 where leading zeros are allowed
• hexadecimal numbers, in tool notation: 0[xX][0-9a-fA-F]+
• a C₀ floating-point literal (not on the slides, but the slide-26 example of a “nontrivial” characterisation): [0-9]+ "." [0-9]* ([eE] [+-]? [0-9]+)?

2.5 What a regular expression cannot do

Slide 28 already named the boundary: $\{a^{n}b{c}^n\}$ needs unbounded counting, i.e. memory, i.e. a stack — not a finite automaton. Consequences you meet in real lexers:

• nested comments (Haskell {- {- -} -}, Rust /* /* */ */) are not regular; C-style /* … */ without nesting is regular, /\*([^*]|\*+[^*/])*\*+/ style
• balanced brackets, indentation-sensitive layout (Python), string interpolation with nesting — all beyond regex
• that is exactly where the lexer stops and the parser starts; the practical workarounds live in practical-lexers §5

2.6 Algebraic laws (the answer to slide-35 exercise 3)

The question: which of $\mid$, concatenation, ${}^{\ast }$, $?$, ${}^{+}$ are associative, commutative, idempotent, have a neutral element, satisfy a distributivity law?

Operation	Associative	Commutative	Idempotent	Neutral element	Distributive
$r\mid s$	yes: $(r\mid s)\mid t=r\mid (s\mid t)$	yes	yes: $r\mid r=r$	$\varnothing$	—
$rs$ (concatenation)	yes	no: $ab\ne ba$	no	$\epsilon$: $\epsilon r=r\epsilon =r$	yes over $\mid$, both sides
$r^{\ast }$	vacuous (unary)	vacuous	yes: $(r^{\ast }{)}^{\ast }=r^{\ast }$	—	see below
$r?$	vacuous (unary)	vacuous	yes: $(r?)?=r?$	—	—
$r^{+}$	vacuous (unary)	vacuous	yes: $(r^{+}{)}^{+}=r^{+}$	—	—

Distributivity, written out:

$$r(s\mid t)=rs\mid rt(r\mid s)t=rt\mid st$$

Careful: $\mid$ does not distribute over concatenation in general — $r\mid st\ne (r\mid s)(r\mid t)$.

Further identities that are handy in the exam when you must state “an equivalent, simpler regex”:

$$r\varnothing =\varnothing r=\varnothing {\varnothing }^{\ast }=\epsilon {\epsilon }^{\ast }=\epsilon (r\mid s{)}^{\ast }=(r^{\ast }{s}^{\ast }{)}^{\ast }{r}^{\ast }{r}^{\ast }=r^{\ast }(r^{\ast }{)}^{\ast }=r^{\ast }$$

${\epsilon }^{\ast }=\epsilon$ and ${\varnothing }^{\ast }=\epsilon$ are the two that get marked wrong most often.

2.7 Slide-35 exercises, worked

1. $r=(a\mid b)(c\mid d\mid \epsilon )$. (a) derivation in §2.3. (b) $L(r)=\{ac,ad,a,bc,bd,b\}$ — six words, i.e. $\{a,b\}\times \{c,d,\epsilon \}$.

2. Unfold the abbreviations in $((a^{+}b{)}^{+}c{)}^{+}$. With $r^{+}=r{r}^{\ast }$:

$$a^{+}=a{a}^{\ast }\Rightarrow (a^{+}b)=a{a}^{\ast }b\Rightarrow (a^{+}b{)}^{+}=(a{a}^{\ast }b)(a{a}^{\ast }b{)}^{\ast }$$

so

$$((a^{+}b{)}^{+}c{)}^{+}=((a{a}^{\ast }b)(a{a}^{\ast }b{)}^{\ast }c\left)\right((a{a}^{\ast }b)(a{a}^{\ast }b{)}^{\ast }c{)}^{\ast }$$

(${}^{\ast }$ is not an abbreviation — it is core syntax — so it stays.)

3. table in §2.6.

4. number words from $[0-9{]}^{+}$, leading zeros allowed:

	regex
(a) value $=42$	$0^{\ast }42$
(b) value $\ne 42$	$[0-9]\mid [0-9{]}^{+}[0-46-9]\mid [0-9{]}^{\ast }[01356789]2\mid [0-9{]}^{\ast }[1-9][0-9{]}^{\ast }42$
(c) value $>42$	$0^{\ast }([1-9][0-9][0-9{]}^{+}\mid [5-9][0-9]\mid 4[3-9])$

(b) case analysis: one digit; ending in a digit $\ne 2$; ending in $x2$ with $x\ne 4$; ending in $42$ but with a nonzero digit somewhere before. (c): more than two significant digits, or two significant digits $\ge 50$, or $\mathrm{43..49}$.

3. Finite automata

3.1 The three illustrative NFAs (slide 37)

Left (nondeterministic because state $C$ has both a $b$- and an $a$-edge, and $B$ is reachable by two different routes):

stateDiagram-v2
    direction LR
    [*] --> A
    A --> B : a
    B --> B : b
    B --> C : a
    C --> B : b
    C --> D : c
    D --> [*]

Right — nondeterminism via an $\epsilon$-edge and via the race on $c$:

stateDiagram-v2
    direction LR
    [*] --> 1
    1 --> 2 : ε
    2 --> 2 : b
    1 --> 3 : a
    2 --> 3 : c
    3 --> [*]

3.2 NFAs, formally (slide 38)

An NFA is a 4-tuple $(S,s_0,F,T)$:

• $S$ — finite set of states
• $s_0\in S$ — distinguished initial state
• $F\subseteq S$ — set of final states
• $T\subseteq S\times (\Sigma \cup \{\epsilon \})\times S$ — the transition relation, written $s\stackrel{a}{⟶}{s}^{\prime }$

The lecture’s running example — note the arrow into $q_0$ is the initial marker, the double ring is $F$:

stateDiagram-v2
    direction LR
    [*] --> q0
    q0 --> q1 : a
    q0 --> q2 : a
    q1 --> q3 : b
    q3 --> q2 : c
    q2 --> q2 : d
    q2 --> [*]

Formally, as on the slide:

$$S=\{q_0,q_1,q_2,q_3\}{s}_0=q_{0}F=\{q_2\}$$ $$T=\{q_0\stackrel{a}{\to }{q}_1,q_0\stackrel{a}{\to }{q}_2,q_1\stackrel{b}{\to }{q}_3,q_2\stackrel{d}{\to }{q}_2,q_3\stackrel{c}{\to }{q}_2\}$$

Nondeterminism has two independent sources, both visible here: two $a$-transitions out of $q_0$, and in general $\epsilon$-transitions (none in this particular example).

3.3 When does an NFA accept a word?

Not spelled out on the slide, but it is what the powerset construction later simulates, so it is worth having exactly:

$$w=a_1\dots a_n\in L(A)⟺\exists s_0\stackrel{a_1}{\to }{s}_1\stackrel{a_2}{\to }\dots \stackrel{a_n}{\to }{s}_n\text{ with }{s}_n\in F$$

i.e. there exists at least one accepting path. A word is rejected only if all paths die or end outside $F$. That existential quantifier is precisely what is expensive about NFAs (exponential search) and what the DFA removes.

3.4 DFAs, formally (slide 43)

A DFA is a 4-tuple $(S,s_0,F,\sigma )$ — same first three components, but the transition component is a (possibly partial) function

$$\sigma :S\rightharpoonup S$$

(lecture notation $\sigma :S\nrightarrow S$, “partial function”). Intuitively: an NFA without $\epsilon$-transitions in which “never $s\stackrel{a}{\to }s$ and $s\stackrel{a}{\to }{s}^{\prime }$ for $s\ne s^{\prime }$” holds — at most one successor per symbol.

Acceptance degenerates to a unique run: $w\in L(A)$ iff the (unique) path labelled $w$ exists and ends in $F$.

DFAs are obviously a special case of NFAs. The converse is the content of §5: for every NFA there is an equivalent DFA. Together with §4 that closes the loop

$$\text{regex}⟶\text{NFA}⟶\text{DFA}$$

with no loss of expressive power at any step (Kleene).

Notation drift warning. The lecture uses $S,s_0,F$ and $\sigma$ (DFA) / $T$ (NFA). Mogensen’s book and most literature write $Q,q_0,F,\delta$. In the exam use the lecture’s letters; mentally translate when reading the book.

4. Regular expression → NFA (Thompson construction)

The lecture calls it only “constructing an NFA from a regular expression”; in the literature it is the McNaughton–Yamada–Thompson construction (Thompson, CACM 1968).

4.1 The invariant: fragments with a single entry and a single exit

The construction produces, for each subexpression $r$, an NFA fragment with

• some states and transitions,
• an ingoing, unlabelled transition (the entry hook),
• an outgoing transition labelled with an element of $\Sigma \cup \{\epsilon \}$ (the exit hook).

That interface is exactly what makes the construction compositional: fragments are glued only through their hooks, never touching their internals. The classical statement of the invariant:

exactly one start state with no incoming arc, exactly one final state with no outgoing arc, and at most $2|r|$ states.

(The lecture’s presentation hides the final state until §4.4: “ultimately, completion to a whole NFA: the ingoing unlabelled transition marks the initial state; the outgoing labelled transition gets connected with a newly added final state.”)

4.2 Base cases

The slide draws each base case as two hook-arrows around a label — nothing more:

    ──>   ε   ──>              ──>   a   ──>

Read literally: a fragment for an atom is one transition, labelled $\epsilon$ or $a$, whose source is the entry hook (the ingoing unlabelled transition) and whose target is the exit hook (the outgoing labelled transition). So the smallest fragment has exactly two states. Concatenation then glues exit to entry; $\mid$ and ${}^{\ast }$ add states around existing fragments — that is the whole algorithm.

flowchart LR
    subgraph eps["ε-fragment"]
        direction LR
        i1(( )) -->|ε| e1(( ))
        e1 -.->|exit| o1(( ))
    end
    subgraph aa["a-fragment"]
        direction LR
        i2(( )) -->|a| a1(( ))
        a1 -.->|exit| o2(( ))
    end

4.3 Recursive cases — the three gluing templates (slide 40)

flowchart LR
    i(( )) -->|ε| r[r]
    i -->|ε| s[s]
    r --> o(( ))
    s --> o

flowchart LR
    i(( )) --> r[r]
    r --> s[s]
    s --> o(( ))

flowchart LR
    i(( )) -->|ε| r[r]
    i -->|ε| o(( ))
    r -->|ε| i

Read them as state-machine surgery:

Case	New states	New $\epsilon$-edges
$r\mid s$	2 (a split and a join)	split → $r_{in}$, split → $s_{in}$, $r_{out}$ → join, $s_{out}$ → join
$rs$	0	$r_{out}\to s_{in}$ becomes the connection (exit hook = entry hook)
$r^{\ast }$	1 (a split, which is also the join)	split → $r_{in}$, split → exit, $r_{out}$ → split

$r^{\ast }$ is the case that needs a loop back: the star is the only unbounded construct, hence the only one producing a cycle. This is also why every star adds exactly one $\epsilon$-cycle, and why an NFA can loop forever on $\epsilon$-moves if a construction is wrong (a good self-check).

4.4 Worked example: $(a\mid b{)}^{\ast }ac$ (slide 42)

The slides skip the intermediate steps and show the finished 8-state NFA (“outcome of the construction concretely”). Reconstructed exactly:

stateDiagram-v2
    direction LR
    [*] --> 1
    1 --> 5 : ε
    1 --> 2 : ε
    5 --> 6 : ε
    5 --> 7 : ε
    6 --> 8 : a
    7 --> 8 : b
    8 --> 1 : ε
    2 --> 3 : a
    3 --> 4 : c
    4 --> [*]

Machine-readable form (this is the object the exam expects you to write down):

$$\begin{array}{rlrlrl}S& =\{1,\dots ,8\},& s_0& =1,& F& =\{4\}\\ T_{\epsilon }& =\{1\to 5,1\to 2,5\to 6,5\to 7,8\to 1\}& & & & \\ T_a& =\{6\to 8,2\to 3\}& T_b& =\{7\to 8\}& T_c& =\{3\to 4\}\end{array}$$

How each piece maps back to the syntax tree — this mapping is the thing to be able to recite:

States	Fragment	Rule used
5, 6, 7, 8	$(a\mid b)$	alternative: split 5, join 8, branching to the $a$-edge 6→8 and the $b$-edge 7→8
1, 2, 5–8	$(a\mid b{)}^{\ast }$	star: split 1 with $\epsilon$ to the body-entry 5 and $\epsilon$ to the continuation 2; body-exit 8 recurses with $\epsilon$ back to 1
2, 3	$a$ (concatenation)	exit hook of the star is the entry of the $a$-fragment
3, 4	$c$	concatenation again; 4 is the newly added final state

Why 8 states and not 11? Textbook Thompson on $(a\mid b{)}^{\ast }ac$ gives more states (each atom two states, each operator two more). The lecture’s variant is the standard optimisation the slide alludes to: “potentially discussion of optimizations, in particular for some of the abbreviations” —

• the branch node of $(a\mid b)$ is merged with the star’s body entry (5), and the join is merged with the star’s body exit (8), so $(a\mid b)$ costs 4 states instead of 6;
• the star costs 1 new state (1) instead of 2, because the split and the join of the star are the same state — legal because both the entry-$\epsilon$ and the exit-$\epsilon$ leave from it;
• the final state 4 is created once, at the very end, as §4.1 prescribes.

You may always answer the exam with either the literal textbook construction or this optimised one, as long as the language is right and you can name the fragments.

5. NFA → DFA: ε-closure and the powerset construction

The plan: simulate all NFA paths in parallel. A DFA state is a set of NFA states. Two technicalities make it work — ignoring $\epsilon$-transitions, and building only the reachable sets.

5.1 $\epsilon$-closure (slide 44)

For $M\subseteq S$:

$$\hat{\epsilon }(M)=\text{the smallest set }X\text{ with }\{\begin{array}{ll}\text{a)}& M\subseteq X\\ \text{b)}& \text{if }s\in X\text{ and }s\stackrel{\epsilon }{\to }t\text{, then }t\in X\end{array}$$

computable as the smallest fixpoint of

$$f(X)=M\cup \{t\mid s\in X,s\stackrel{\epsilon }{\to }t\}$$

Equivalently, the more usable form: $\hat{\epsilon }(M)$ = all states reachable from $M$ by a path of $\epsilon$-moves (including the empty path, hence $M\subseteq \hat{\epsilon }(M)$; and $\hat{\epsilon }(M)=\hat{\epsilon }(\hat{\epsilon }(M))$ — an idempotent, which is why the definition can say “smallest set with a) and b)” instead of “iterate until closed”).

Worklist implementation (what you actually code):

closure(M):
    X = M;  work = M
    while work not empty:
        s = pop(work)
        for t in eps_successors(s):
            if t not in X:  X.add(t);  push(work, t)
    return X

Cost: $O(|S|+|T_{\epsilon }|)$ per call, not “loop $|S|$ times until nothing changes” — same result, better constant.

The distributivity fact behind the identity we need later. $f$ above is distributive with respect to $\cup$, because $M\subseteq f(X)\cup f(Y)$ whenever $M\subseteq f(X)$. Hence

$$\hat{\epsilon }(M_1\cup M_2)=\hat{\epsilon }(M_1)\cup \hat{\epsilon }(M_2)\text{and in particular}\hat{\epsilon }(M)=\bigcup _{s\in M}\hat{\epsilon }(\{s\})$$

This is exactly the step handwritten on slide 48, and it is what lets you precompute $\hat{\epsilon }(\{s\})$ once per state instead of once per subset. Spot-check on the example of §4.4:

$$\hat{\epsilon }(\{3,8\})=\hat{\epsilon }(\{3\})\cup \hat{\epsilon }(\{8\})=\{3\}\cup \{1,2,5,6,7,8\}=\{1,2,3,5,6,7,8\}$$

which is precisely the slide-47 label.

5.2 Background: fixpoint iteration (slide 45)

Let $U$ be a finite set and $f:\mathcal{P}(U)\to \mathcal{P}(U)$ monotone with respect to $\subseteq$. Then:

1. there is a smallest pre-fixpoint of $f$, i.e. the (unique) smallest set $X\in \mathcal{P}(U)$ with $f(X)\subseteq X$;
2. it is even a (smallest) fixpoint: for this $X$, $f(X)=X$ holds;
3. it can be computed by evaluating $f(\varnothing ),f(f(\varnothing )),f(f(f(\varnothing ))),\dots$ until no changes occur;
4. if $f$ is moreover distributive with respect to $\cup$, then additionally $f^{n+1}(\varnothing )=f^n(\varnothing )\cup f(f^n(\varnothing )\setminus f^{n-1}(\varnothing ))$

Why it holds (the intuition the slide leaves implicit): $\mathcal{P}(U)$ is a finite lattice, so the ascending chain $\varnothing \subseteq f(\varnothing )\subseteq f^2(\varnothing )\subseteq \dots$ cannot grow more than $|U|$ times; monotonicity guarantees the chain is ascending, finiteness guarantees termination, and the last element is simultaneously the least pre-fixpoint and the least fixpoint. Point 4 is the “only look at what is new this round” optimisation — precisely the worklist/new states only trick used by both $\hat{\epsilon }$ and the powerset construction.

The same pattern shows up three times in this chapter — worth noticing once: ${\Sigma }^{\ast }$ as the smallest set closed under appending a symbol, $\hat{\epsilon }(M)$ as the smallest set closed under $\epsilon$-steps, and $S^{\prime }$ as the smallest set of reachable DFA states.

5.3 The construction (slide 46)

Given an NFA $(S,s_0,F,T)$, define the DFA $(S^{\prime },s_0^{\prime },F^{\prime },{\sigma }^{\prime })$:

$$\begin{array}{rl}{s}_0^{\prime }& =\hat{\epsilon }(\{s_0\})\\ {\sigma }^{\prime }(s^{\prime },a)& =\hat{\epsilon }(\{t\mid s\in s^{\prime },s\stackrel{a}{\to }t\}),\text{only if }\ne \varnothing \\ S^{\prime }& =\text{smallest (pre-)fixpoint of }f(X)=\{s_0^{\prime }\}\cup \{{\sigma }^{\prime }(s^{\prime },a)\mid s^{\prime }\in X,a\in \Sigma \}\\ F^{\prime }& =\{s^{\prime }\in S^{\prime }\mid s^{\prime }\cap F\ne \varnothing \}\end{array}$$

Three things to be able to justify:

• $s_0^{\prime }$ is closed under $\epsilon$ — otherwise the DFA would “forget” states the NFA could already be in before consuming anything.
• ${\sigma }^{\prime }$ takes a second closure — after an $a$-step, the NFA may move on with any number of $\epsilon$-steps before the next real symbol.
• $F^{\prime }$ uses $\cap F\ne \varnothing$, not $\subseteq F$ — reaching any final state in the simulated set counts as accepting, because NFA acceptance is existential (§3.3).
• ${\sigma }^{\prime }$ is only defined when the move set is non-empty: the result is a partial DFA, exactly the $\sigma :S\rightharpoonup S$ of §3.4. Some textbooks add a sink state to totalise it; the lecture does not, and that choice is what makes the minimization example below interesting.

5.4 Worked example on $(a\mid b{)}^{\ast }ac$ (slide 47)

Order of discovery: start closure, then BFS over symbols $a,b,c$.

DFA state	NFA subset	on $a$	on $b$	on $c$
A $=\hat{\epsilon }(\{1\})$	$\{1,2,5,6,7\}$	B	C	–
B $=\hat{\epsilon }(\{3,8\})$	$\{1,2,3,5,6,7,8\}$	B	C	D
C $=\hat{\epsilon }(\{8\})$	$\{1,2,5,6,7,8\}$	B	C	–
D $=\hat{\epsilon }(\{4\})$	$\{4\}$	–	–	–

Spot-checks that the table is right:

• ${\sigma }^{\prime }(A,a)$: from $\{1,2,5,6,7\}$ the only $a$-edges are $2\stackrel{a}{\to }3$ and $6\stackrel{a}{\to }8$, giving $\{3,8\}$, whose closure is B. ✔ (this is why A on $a$ jumps to B, not to C — the $a$-edge out of 2 is easy to miss)
• ${\sigma }^{\prime }(B,c)$: only $3\stackrel{c}{\to }4$, closure $\{4\}$ = D. ✔
• $D\in F^{\prime }$ since $4\in F$. ✔

Rendered (DOT rather than Mermaid: the labels are sets and B/C need a self-loop each):

stateDiagram-v2
    direction LR
    [*] --> A
    state "A = {1,2,5,6,7}" as A
    state "B = {1,2,3,5,6,7,8}" as B
    state "C = {1,2,5,6,7,8}" as C
    state "D = {4}" as D
    A --> B : a
    A --> C : b
    B --> B : a
    B --> C : b
    B --> D : c
    C --> B : a
    C --> C : b
    D --> [*]

The language check by eye: $B$ is “the last symbol was $a$”, $D$ is “…followed by $c$”, A/C are “no $a$ pending”.

The fixpoint trace (slide 48). The slide’s handwriting computes $\hat{\epsilon }(\{1\})$ as the fixpoint iteration of $f(X)=\{1\}\cup \{t\mid s\in X,s\stackrel{\epsilon }{\to }t\}$:

$$\begin{array}{rl}f(\varnothing )& =\{1\}\\ f^2(\varnothing )& =\{1\}\cup \{2,5\}=\{1,2,5\}\\ f^3(\varnothing )& =\{1,2,5\}\cup \{6,7\}=\{1,2,5,6,7\}\text{(stable: no new states)}\end{array}$$

so $\hat{\epsilon }(\{1\})=\{1,2,5,6,7\}$ — three rounds, and it is $f^{|S|}(\varnothing )$-safe because the chain is monotone and $S$ is finite. The same slide writes $\Sigma =\{\text{a},\text{b},\text{c}\}$ and the concrete step function $f(X)=M\cup \{t\mid s\in X,s\stackrel{\epsilon }{\to }t\}$, then notes the distributivity $f(X\cup Y)=f(X)\cup f(Y)$ used in §5.1.

5.5 Cost of the construction

Worst case: $2^{|S|}$ DFA states, and it is attained (classic family: $(a\mid b{)}^{\ast }a(a\mid b{)}^n$ needs $2^n$ states). For real lexers this is a non-issue:

• lexeme classes are “shallow” — no nested structure, so subsets stay small;
• the construction only visits reachable subsets (the fixpoint, not $\mathcal{P}(S)$);
• if a lexer spec ever blows up, that is a diagnostic: the language is being over-specified (e.g. accidental backtracking-like patterns).

Also: the resulting DFA is correct by construction but not necessarily small — hence §6.

6. DFA minimization

6.1 When are two states the same?

Two states $p,q$ of a DFA are equivalent ($p\equiv q$) iff for all words $w\in {\Sigma }^{\ast }$:

$$\hat{\sigma }(p,w)\in F⟺\hat{\sigma }(q,w)\in F$$

with $\hat{\sigma }$ the extended transition function ($\hat{\sigma }(s,\epsilon )=s$, $\hat{\sigma }(s,aw)=\hat{\sigma }(\sigma (s,a),w)$, undefined if the partial function gets stuck). Equivalence is the Nerode congruence; the minimal DFA is unique up to isomorphism.

The practical formulation is contrapositive and is what the table-filling algorithm uses: $p\not\equiv q$ iff $p$ and $q$ are distinguishable, i.e. there is a word $w$ such that exactly one of $\hat{\sigma }(p,w)$, $\hat{\sigma }(q,w)$ is in $F$.

6.2 Algorithm: partition refinement (“Moore”)

1. Initial partition — final states vs. non-final states. (If the DFA is partial, add one dead state $\perp$ and complete it; $\perp$ is non-final.)
2. Refine: split a block whenever two of its states go to different blocks for some symbol $a\in \Sigma$.
3. Repeat until no block splits. Blocks = states of the minimal DFA; $F^{\prime }$ = blocks containing a final state.

Termination: each round only splits, the block count is bounded by $|S|$. Complexity of this naive refinement: $O(|S{|}^2|\Sigma |)$; Hopcroft’s algorithm (1971) gets $O(|S|\log |S|\cdot |\Sigma |)$ with a worklist of splitters.

The lecture introduces minimization on slide 46 only as “discussion of minimization” and then shows the result (slide 49) rather than the algorithm — so the algorithm is the main gap to fill from literature.

6.3 Worked minimization of the slide-47 DFA

Start from the 4-state DFA of §5.4, completed with $\perp$:

	$a$	$b$	$c$
A	B	C	$\perp$
B	B	C	D
C	B	C	$\perp$
D	$\perp$	$\perp$	$\perp$
$\perp$	$\perp$	$\perp$	$\perp$

Round 0: $\{\{A,B,C,\perp \},\{D\}\}$ (final vs. non-final).

Round 1: look at the block $\{A,B,C,\perp \}$ and symbol $c$:

state	$\sigma (\cdot ,c)$	lands in block
A	$\perp$	non-final
B	D	final
C	$\perp$	non-final
$\perp$	$\perp$	non-final

→ $B$ separates: $\{\{A,C,\perp \},\{B\},\{D\}\}$.

Round 2: block $\{A,C,\perp \}$ on symbol $a$: A→B, C→B (block $\{B\}$) but $\perp$→$\perp$ (still this block) → $\perp$ separates: $\{\{A,C\},\{\perp \},\{B\},\{D\}\}$.

Round 3: $\{A,C\}$: $a$→B/B ✔ same block, $b$→C/C ✔ same, $c$→$\perp$/$\perp$ ✔ same. No more splits. Stable.

Result: A ≡ C, and nothing else. This is the interesting part of the example — $A$ and $C$ look different (C = “just finished an $a$-or-$b$ iteration”, its subset contains state 8) but they are behaviourally identical: from both, only $a$ and $b$ lead anywhere, $c$ cannot follow. The distinction is an artefact of the subset construction, which is exactly what minimization removes.

The slide’s handwritten solution writes the same thing, with its classes named $M_1=\{A,B,C\}$, $M_2=\{D\}$ first and then $M_3=\{A,C\}$, $M_4=\{B\}$ — i.e. the two refinement rounds above, and a table of the split criterion “on $c$: $M_2$ vs. none”.

stateDiagram-v2
    direction LR
    [*] --> AC
    state "{A,C}" as AC
    state "{B}" as B
    state "{D}" as DD
    AC --> B : a
    AC --> AC : b
    B --> B : a
    B --> AC : b
    B --> DD : c
    DD --> [*]

Partial vs. complete — the honest bookkeeping. If you keep the dead state $\perp$ (needed for the partition refinement to be well defined), the minimal complete DFA has 4 states: $\{A,C\},\{B\},\{D\},\{\perp \}$. If you drop $\perp$ again — legal, because a partial DFA may omit transitions — you get the 3-state partial automaton above, which is what the slide draws, and its transition table needs no $\perp$-column:

	$a$	$b$	$c$
$\{A,C\}$	$\{B\}$	$\{A,C\}$	–
$\{B\}$	$\{B\}$	$\{A,C\}$	$\{D\}$
$\{D\}$	–	–	–

Sanity check against the intuition for $(a\mid b{)}^{\ast }ac$: the minimal DFA is exactly “no $a$ pending” / “last symbol was $a$” / “done”, which is obviously right and obviously irreducible.

6.4 Why minimize at all

• the transition table is the hot data structure of the scanner: smaller table = better cache behaviour;
• dead/duplicate states are the most common artefact of the subset construction (§5), so removing them is cheap correctness hygiene;
• minimal gives a canonical form — two regexes with the same language yield the same minimal DFA, so minimization doubles as an equivalence test (used by tools that warn about duplicate/overlapping lexer rules).

7. Exam checklist

Constructive tasks, in the order they are likely to be asked:

1. Regex → NFA. Draw the syntax tree first, attach the fragment table of §4.3 to each node, then merge. Check: single start state, single final state, number of states, and that only $\ast$ creates cycles.
2. NFA → DFA. Write $T_{\epsilon }$ / $T_a$ / $T_b$ / $T_c$ as sets (not as a drawing) — the arithmetic is much harder to get wrong that way. Then BFS: $\hat{\epsilon }$ of the start set, then for each new state and each symbol, move then close. Fill the table before drawing.
3. Minimize. Complete with $\perp$, round 0 = final vs. non-final, refine by symbol until stable, then drop $\perp$ if the exercise wants a partial DFA.
4. Justify (short-answer): why $\hat{\epsilon }$ needs a fixpoint (idempotence/least-closure); why $F^{\prime }$ uses $\cap F\ne \varnothing$ (existential acceptance); why the powerset construction can blow up ($2^{|S|}$); why $\epsilon$-transitions are harmless (they can always be eliminated by the construction).

Self-check questions that are cheap to grade yourself on:

• Does your NFA accept $\epsilon$? (Only if the start closure hits a final state — check the closure again.)
• Did you apply the precedence ${}^{\ast }>\cdot >\mid$ correctly in $a\mid bc$?
• Is every DFA state a closed subset? An unclosed subset in an exam answer is the classic deduction.
• Did you forget that $\hat{\epsilon }$ of a set includes the set itself?

8. Sources

Source	Used for
slides 19–51 (raw/compilerbau/compilerbau-slides-55.md, version 28.10.2026)	all formal definitions, notation, the examples redrawn above
Torben Ægidius Mogensen, Introduction to Compiler Design, Springer 2017 — ch. 2 (lexical analysis)	the book the lecture aligns with; notation $Q,q_0,F,\delta$
Ken Thompson, “Programming Techniques: Regular expression search algorithm”, CACM 11(6), 1968	the regex→NFA construction and its single-entry/single-final invariant, $\le 2n$ states
Hopcroft, “An $n\log n$ algorithm for minimizing states in a finite automaton”, 1971 (PDF)	partition-refinement minimization and its complexity
DFA minimization (Wikipedia)	Moore vs. Hopcroft, table-filling formulation, Nerode congruence

Related: practical-lexers (what a real lexer does with all this), Compiler Construction course page, concept map.