CS 181 Lecture 7 -- Fall 2026, UCLA
Watch on YouTube →
Overview
Eli Jaffe develops the definition and closure properties of nondeterministic finite automata (NFAs), showing how they simplify concatenation, reversal, and Kleene star constructions that are awkward for deterministic finite automata (DFAs). The lecture’s central result is that every NFA has an equivalent DFA: tracking subsets of NFA states gives a conversion, though it can require exponentially more states, as illustrated by a 10-state NFA versus a 1,024-state DFA.
Key takeaways
- NFAs simplify language operations that are awkward for DFAs: ε transitions from D1’s accepting states to D2’s start state let an NFA guess where a concatenated input splits.
- For the language where the tenth-to-last bit is 1, a 10-state NFA suffices, while the smallest DFA requires 1,024 states.
- Every NFA has an equivalent DFA because a DFA can track the set of all NFA states reachable after each input prefix; with k NFA states, at most 2^k subsets are needed.
- NFA acceptance is existential: one accepting branch is enough. Consequently, simply flipping accepting states does not complement an NFA’s language.
- NFAs and DFAs recognize the same languages, but NFAs can be more compact and easier to design; equivalence does not guarantee an efficient state-count conversion.
Chapters
- Eli Jaffe says the first exam is one week away and points students to five years of prior exams with solutions.
- Homework 2 is extended to Friday so students can use lecture material and office hours before submitting.
- The lecture revisits NFA composition and asks how NFAs relate to DFAs, which previously struggled with concatenation and reversal.
- An NFA transition takes a state and a label, 0, 1, or ε, and returns a subset of states rather than a single state.
- The accepting states remain a subset of the machine’s state set, as in a DFA.
- The power set of the state set represents all possible subsets that an NFA transition can reach.
- An NFA outputs 1 if at least one branch finishes in an accepting state; it outputs 0 if no branch accepts.
- A transition that leads to the empty set is treated as a dead path, and ε transitions must not form cycles.
- In the N1 example, the machine accepts strings whose fourth-to-last bit is 1 by branching whenever it reads a 1.
- The lecture generalizes the fourth-to-last-bit construction to an NFA that checks whether the tenth-to-last bit is 1.
- That NFA uses 10 states, while the smallest DFA for the same language requires 1,024 states, or 2^10.
- Jaffe identifies the state-count result as a corollary of the Myhill-Nerode theorem.
- Given DFAs D1 and D2, the target accepts strings that split into an X1 accepted by D1 followed by an X2 accepted by D2.
- Add ε transitions from every accepting state of D1 to the start state of D2, allowing the NFA to guess the split point.
- Use D2’s accepting states as the constructed NFA’s accepting states so a branch must complete the second part successfully.
- To recognize F on the reverse of an input, reverse every transition in the DFA for F.
- The reversed machine can have multiple outgoing edges with the same label, which is permitted in an NFA but not a DFA.
- A new start state uses ε transitions to all former accepting states, and the old start state becomes the new accepting state.
- Jaffe connects nondeterminism to familiar topics such as P versus NP and notes that its origins lie in the study of NFAs.
- NFAs are an abstraction rather than a physical device that literally explores parallel branches.
- The abstraction can make it easier to design practical algorithms, even when the final implementation is deterministic.
- F-star accepts an input if it can be divided into any finite number of pieces, each accepted by F.
- For a language L, L-star contains finite concatenations of strings from L.
- By convention, the empty string belongs to F-star, a detail needed for the construction.
- Add ε transitions from each original accepting state back to the original start state so the machine can begin another accepted piece.
- At each accepting state, an NFA branch can either continue the current piece or begin parsing the next one.
- A new accepting start state, connected to the old start by ε, ensures that the empty string is accepted without changing whether the original F accepts it.
- The class pauses at about 57:39 and resumes at about 62:21, with questions clarifying how ε transitions behave.
- An ε edge is an option to branch, not an automatic move that forces a path to leave its current state.
- Making the new start state accepting handles the empty string; simply marking the original start state could incorrectly accept other strings.
- For the AND of two NFAs, construct states as ordered pairs from the two original state sets.
- On a label, the new transition includes every pair whose first and second components are reachable through the corresponding original transitions.
- A product state accepts only when both component states accept, matching the requirement that both machines accept the input.
- For OR, a new start state can use ε transitions to the starts of both NFAs, letting a branch choose which machine to run.
- This branching construction uses the sum of the original state counts rather than their product.
- The product-state construction also works for OR by accepting when either component state is accepting.
- For an NFA, flipping accepting and rejecting states does not generally complement the recognized language.
- In the example on input 10, one branch reaches the original accepting state while another reaches a state that becomes accepting after the flip.
- Because NFA acceptance requires only one accepting branch, the flipped machine still accepts 10, even though the complement should reject it.
- The problem with direct complementation is that an input can have both accepting and rejecting branches in the original NFA.
- Jaffe relates this difficulty to NP versus co-NP, where the broader question is whether complements of nondeterministically computable problems remain in the same class.
- NFAs therefore do not simply dominate DFAs: intersection and union are straightforward, while negation is not.
- For every NFA N, there exists a DFA D such that N and D return the same result on every input.
- This establishes that NFAs add no computational power for finite automata, despite their ability to branch.
- Jaffe contrasts this settled automata result with the unresolved role of nondeterminism in the P versus NP question for Turing machines.
- An NFA can be a more natural description of a language than a DFA, especially for guessed split points and reversed paths.
- The NFA can then be converted into a DFA, much as a high-level Boolean circuit can be easier to design than an equivalent NAND-only circuit.
- Computational equivalence does not imply equal efficiency: the conversion may substantially increase the number of states.
- Since concatenation has an NFA construction, the equivalence theorem implies that concatenation is also computable by a DFA.
- The same conversion establishes DFA constructions for Kleene star and reversal.
- These results recover DFA closure properties by first using the more convenient NFA representation.
- To compute NOT F, first convert an NFA for F into an equivalent DFA.
- Complement the DFA by swapping accepting and non-accepting states, a valid operation because each input has a single deterministic run.
- The complemented DFA can be regarded as an NFA, or converted back to an NFA if desired.
- Jaffe begins the proof of NFA-to-DFA conversion using an NFA without ε transitions.
- In the example, reading the first 1 can reach states 1 and 3, and subsequent 0s create additional possible states.
- Rather than storing every branch separately, the DFA can record the set of NFA states reachable after each input prefix.
- Two branches that have read the same number of input bits and reach the same NFA state have identical futures.
- Repeated copies of a state in the branching tree can therefore be merged without changing whether an accepting state is eventually reached.
- For the sample input, the reachable-state sets evolve from {0} to {1,3}, then {1,2}, and later include states 1, 2, and 3.
- A DFA state can represent one subset of the original NFA’s states, with transitions updating the reachable subset after each bit.
- An NFA with k states has at most 2^k possible subsets, giving a finite DFA construction that may be exponentially larger.
- The lecture ends before the formal construction; the next class will complete the proof and extend it to ε transitions.
Transcript excerpt
0:01 Oh, excuse me. That's because my volume was off. Okay. Hello everybody. Happy midterm season to all those who celebrate. Uh, I'm sure probably some of you have already taken midterms. As a reminder, uh, our first exam is a week from today. Um, there I released some previous exam ones, all the exam ones from the past 5 years of Professor Mac's version of this class. So, if you're curious about what kind of questions will show up on the midterm, that's your best resource. They all have solutions there, too. Uh, and one other piece of logistics, I have extended the homework two deadline until Friday because I realized there's some stuff from lecture seven, which is
0:48 today's lecture, that you guys need to do the homework, and I didn't feel like two days was a fair time for that. And I want people to be able to attend office hours and ask questions. So, homework two deadline on Friday, but do be sure to like allocate your time wisely, right? Cuz you need to spend time studying for the exam on Monday, too. So, probably don't push it until like Um, any logistical questions before we get started? Beautiful. Okay, so as a reminder, where are we at? So, we're partway through our discussion of automata. Uh, we introduced the FAs a couple lectures ago, and last lecture we looked at properties of DFAs. So, specifically
1:38 these kinds of composition properties, can we compute the and of two functions using a DFA, the or of two functions, the not of a function. And we looked at some what seem like currently limitations of DFAs. So, some specific function compositions that seem tricky to compute. So, that is like the concatenation of two functions, the reverse of a function, which all seem a
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.