CS 181 Lecture 8 -- Fall 2026, UCLA

Overview

Eli Jaffe proves that every nondeterministic finite automaton (NFA), including one with epsilon transitions, has an equivalent deterministic finite automaton (DFA), using subset construction and epsilon closure. He then connects automata to practical string matching: the KMP algorithm builds a pattern-specific DFA with m+1 states to search an n-bit string in O(n+m) time, before introducing the inductive syntax of regular expressions.

Key takeaways

An n-state NFA can be converted to an equivalent DFA whose states are subsets of NFA states, yielding at most 2^n states.
For epsilon-NFAs, the DFA starts in the epsilon closure of the NFA start state and applies epsilon closure after each input-symbol transition.
Directly simulating an NFA with c states on an n-bit input takes O(nc) time, while a DFA can be evaluated in O(n) time.
KMP builds a DFA with m+1 states for a fixed pattern of length m and searches an n-bit string in O(n+m) time.
Regular expressions are built inductively from 0, 1, epsilon, and the empty language using concatenation, alternation, and Kleene star.

Chapters

0:00 Lecture Goals, Homework Deadline, and Exam One

The lecture completes the equivalence between NFAs and DFAs, then introduces regular expressions.
Homework 2 is due Friday, October 23, at 9:59 p.m.; Exam 1 is scheduled for Monday, October 6.
Exam 1 covers lectures 1 through 8, is closed-note, and uses the lecture room; previous exams are available on Gradescope.

5:00 Why NFA Branches Can Be Compressed into Subsets

NFA execution branches into multiple paths, but paths that reach the same state after the same number of input bits have identical futures.
Instead of tracking every branch separately, a DFA can track the subset of NFA states reachable at each input position.
This subset representation offers a fixed state space even when the input length is unbounded.

7:24 Subset Construction: DFA States as NFA-State Sets

For an NFA with state set S, define the DFA state set as the power set of S.
An NFA with four states yields up to 2^4 = 16 DFA states, including the empty set.
Each DFA state represents all NFA states reachable after reading the same input prefix.

14:35 DFA Transitions and Accepting Subsets

For a subset I and input bit a, the DFA transition is the union of the NFA transitions from every state in I.
A DFA subset is accepting exactly when it contains at least one accepting state of the original NFA.
The construction preserves NFA acceptance because an NFA accepts when at least one possible branch reaches an accepting state.

23:36 Tracing Subset Transitions in a Four-State NFA

From the subset {1,3} on input 1, state 1 reaches state 2 while state 3 has no 1-transition, so the result is {2}.
From {1,2,3} on input 0, the component transitions produce {1,2}, {1,3}, and {1}; their union is {1,2,3}.
With state 3 accepting, every DFA subset containing 3 is accepting.

31:36 Epsilon Transitions and the Reachability-Level Problem

An epsilon edge changes the NFA state without consuming an input bit, so its destination must be accounted for at the current input level.
The construction handles this by including epsilon-reachable states immediately rather than waiting for another input symbol.
The DFA still represents collections of original NFA states.

34:30 Epsilon Closure: Reachable States Without Reading Input

Define the epsilon closure of state q as q itself plus every state reachable from q using only directed epsilon transitions.
In the example, an epsilon edge from state 0 to state 1 makes the closure of 0 equal to {0,1}.
Epsilon reachability can extend through chains of edges; it does not imply that transitions can be traversed backward.

42:32 Extending Subset Construction with Epsilon Closure

For a set I, its epsilon closure is the union of the closures of its member states.
The DFA transition on bit a takes all NFA transitions from states in I, then includes states reachable from those destinations by epsilon transitions.
The DFA start state is the epsilon closure of the NFA start state, and accepting subsets still contain an original accepting state.

49:01 Worked Epsilon-NFA Conversion: Five States, 32 Subsets

The example NFA has five states, so the full subset construction contains up to 2^5 = 32 DFA states.
Its epsilon edge makes the actual starting subset {0,1}, rather than just {0}.
After reading 0 from {0,1}, the ordinary transitions reach {0,2}; epsilon closure adds state 1, producing {0,1,2}.

55:32 Every NFA Has an Equivalent DFA

Subset construction proves that every NFA, including an epsilon-NFA, has an equivalent DFA.
The conversion may increase an n-state NFA to as many as 2^n DFA states; the result makes no efficiency claim.
Nondeterminism adds no extra computational power for finite automata, but can make machine construction easier.

59:43 Epsilon-Closure Conventions and Exam-Study Questions

Epsilon transitions can be incorporated before or after ordinary transitions, but the definitions of states and transitions must remain consistent.
The class discussion notes that the precise differences between alternative conventions deserve a worked comparison.
For exam preparation, Jaffe recommends attempting prior exams first, reviewing definitions as needed, and consulting solutions after struggling for about 10 to 20 minutes.

1:06:39 Running DFAs and NFAs: Time Complexity

A DFA runner starts at state 0, reads each of n input bits once, and performs one transition-table lookup per bit, for O(n) time.
An NFA runner tracks a set of current states and unions the transitions for each state on every input bit.
With c NFA states, the direct simulation takes O(nc) time in the worst case, while avoiding explicit enumeration of all possible paths.

1:14:31 Pattern Matching and the Sliding-Window Baseline

The pattern-matching problem asks whether an m-bit pattern P occurs anywhere inside an n-bit text X.
A sliding-window algorithm compares P with each length-m substring of X, taking O(nm) time.
For a 50,000-bit text and a 20-bit pattern, the basic approach may perform about one million bit comparisons.

1:21:21 KMP Uses a Pattern-Specific DFA for Linear Search

The Knuth-Morris-Pratt (KMP) algorithm constructs a DFA with m+1 states for a pattern of length m.
The DFA construction takes O(m) time, and running it on an n-bit input takes O(n), for total O(n+m) time.
KMP avoids rescanning overlapping text windows and is useful in text search, shell tools, and DNA-sequence analysis.

1:27:16 Building a DFA for the Pattern 1111

For the pattern 1111, states track progress after seeing zero, one, two, three, or four consecutive 1s.
A 0 before reaching the accepting state resets progress to the start state.
After four consecutive 1s, the DFA accepts and can remain accepting for the rest of the input.

1:30:03 Handling Overlapping Prefixes for the Pattern 101

For pattern 101, the DFA tracks how much of the pattern's prefix has been matched so far.
After reading 11, it retains state 1 because the final 1 could begin a new occurrence of 101.
After matching 10 and then reading 0, it returns to the start because no suffix preserves a useful matched prefix.

1:33:37 Regular Expressions for Variable-Length DNA Patterns

The fragile X syndrome example searches DNA strings over the alphabet A, C, G, and T.
The described high-risk pattern begins with GCG, ends with CTG, and allows repeated CG or AG units in between.
Because the middle region allows many possible strings, one fixed-pattern DFA is insufficient as a description; a compact pattern language is useful.

1:37:08 Where Regular Expressions Are Used

Regular expressions support pattern matching in text processors, programming tools, scripting, and search-and-replace workflows.
They can be extended from detecting a match to locating or finding every occurrence in a string.
Other applications include genomic sequence analysis and scanning for known virus patterns; grep is cited as a familiar command-line tool.

1:39:56 Regular Expressions: Inductive Base Cases

Regular expressions are defined inductively, starting with basic expressions and specifying rules for combining them.
The base expressions are 0, 1, epsilon, and the empty-language symbol.
At this stage, the definition establishes valid syntax; the meaning of matching is deferred.

1:41:30 Regular-Expression Composition: Concatenation, OR, and Star

If R1 and R2 are regular expressions, their concatenation R1R2 and alternation (R1|R2) are also regular expressions.
If R1 is a regular expression, its Kleene star R1* represents zero or more repetitions and is also a regular expression.
These operations can be nested, as in (01|1)*; the lecture postpones the semantics of such expressions until the next class.

Transcript excerpt

0:09 Let's start getting started. Uh let's see. >> All right. Hello everybody. Sorry for the delay. It's raining. Everything's slower. Um, I'm pretty excited for today's lecture. I guess while I'm uh sort of opening up my documents, a reminder of what we did last class. So, last class we did some NFA exploration. So we're in the larger context wrapping

0:57 up our discussion of NFAS and DFAS today. They'll come back, but I mean as a tool. And so we introduced this idea of NFAS to hopefully solve some problems that we encountered with DFAS. We used them to construct some uh NFAs for important composition functions. So we looked at concatenation. We looked at the clean star operation which was kind of an extension of concatenation in a way. And then we explored a limitation of NFAS which was the knots. And we talked

1:44 about how computing not was actually not so easy for non-deterministic machines. Somehow this threw a wrench in the game for NFA. And what we stated without proof and started to develop an intuition for is this fact that as it turns out every NFA actually has an equivalent DFI equivalence. So today our goal is to fully establish this equivalence between NFAs and DFAS.

2:40 We are going to use that to kind of put a almost cap on our discussion of finite automata and then we're going to bridge into a discussion of our next model of computation which is going to be regular expressions and we're going to see that we did it in this order for a reason. there is this kind of deep connection between finite automata and regular expressions and we're going to use that to see maybe our first real practical application of NFAS until now they've just kind of existed

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Eli Jaffe.