[HD] EECS4302 F26 - 2026-10-01 (Thursday) - Lecture 7

Overview

Jackie Wang reviews NFA execution and epsilon-NFA techniques in EECS4302, showing how sets of possible states and epsilon-closures determine whether strings are accepted. The lecture then develops a recursive construction from regular expressions to epsilon-NFAs—covering empty string, empty language, symbols, union, concatenation, and Kleene star—with examples relevant to Assignment 1.

Key takeaways

An NFA processes an input by maintaining a set of possible states; a string is accepted if the final set contains at least one accepting state.
An epsilon-NFA can join independently constructed machines with transitions that consume no input, making regular-expression union and concatenation straightforward to model.
An epsilon-closure must include its starting state and every state reachable through zero or more epsilon transitions; for the worked Q0 graph, the closure is {Q0, Q1, Q2, Q3, Q5}.
To process an epsilon-NFA input symbol, first take transitions for that symbol from every state in the current set, then take and union the epsilon-closures of the destinations.
The lecture's recursive regular-expression construction maintains exactly one start and one accepting state, using epsilon links to implement union, concatenation, and Kleene star.
The Kleene-star construction needs an epsilon route that accepts zero repetitions as well as a route through the pattern that permits repeated matches.

Chapters

0:00 EECS4302 Deadlines, Assignment 2, and Reading Week

Assignment 1 is due the following week; students who have not started should begin soon.
Jackie Wang plans to release the project and Assignment 2 before Wednesday and discuss how to approach both in Thursday's class.
The programming test is planned for November 5, and Assignment 2 and tutorials will help students prepare.

2:18 Tracing an NFA with Parallel Sets of States

The example NFA recognizes binary strings ending in 01 and processes the input 00101 from left to right.
After each input symbol, track a set of possible states rather than a single state; for example, the first 0 can lead to both Q0 and Q1.
A branch with no transition for the next character dies, but other branches continue processing.

12:03 NFA Acceptance and the Back to the Future Analogy

After processing 00101, the example NFA can be in Q0 or Q2; because Q2 is accepting, the string is accepted.
The acceptance test is whether the resulting state set intersects the accepting-state set in at least one state.
Jackie Wang uses Back to the Future's alternate timelines as an analogy for NFA nondeterminism: multiple possible paths can be explored in parallel.

18:42 Epsilon Transitions for Regular-Expression Concatenation and Union

An epsilon transition changes state without consuming an input symbol, making epsilon-NFAs convenient for building larger patterns.
For concatenated patterns X followed by Y, connect the accepting states of the X machine to the initial state of the Y machine with epsilon transitions; only Y's accepting states accept the full string.
For a language matching either pattern, introduce an initial state with epsilon transitions to the separate X and Y machines.

26:21 Modeling Floating-Point Strings with an Epsilon-NFA

The example format allows an optional plus or minus sign, decimal digits before a dot, and decimal digits after it.
The constraint that the digit strings on both sides cannot both be empty rejects a bare dot and a sign followed only by a dot.
The string .23 is accepted by taking epsilon for the absent sign and absent integer part, then reading the dot and digits; +46. is also accepted.

32:06 Epsilon-Closure: Include Every State Reachable Without Input

The epsilon-closure of a state contains the state itself, even when no epsilon transitions leave it.
Compute the closure recursively by following every reachable epsilon transition and adding the closures of those destination states.
The traversal ends when all reachable states have been examined and no further epsilon transitions add new states.

35:49 Computing the Epsilon-Closure of Q0

In the worked graph, Q0 has immediate epsilon transitions to Q1 and Q2.
Following Q1 reaches Q3 and then Q5; Q2 and Q5 have no further epsilon transitions.
The resulting closure is {Q0, Q1, Q2, Q3, Q5}, with Q0 included as the starting state.

40:54 Processing Epsilon-NFA Input in Two Phases

Before reading the first character, begin with the epsilon-closure of the initial state; in the 5.6 example, that starting set is {Q0, Q1}.
For input 5, Q0 has no digit transition, while Q1 can reach Q1 and Q4, so the direct destination set is {Q1, Q4}.
After consuming each character, take the epsilon-closure of every destination and union the results; students are asked to complete the remaining characters of 5.6.

47:44 Regular-Expression-to-Epsilon-NFA Construction Rules

The recursive construction supports epsilon, the empty language, alphabet symbols, union (+), concatenation, and Kleene star (*).
Each constructed epsilon-NFA has exactly one start state and one accepting state, with no transition entering the start or leaving the accepting state.
The conversion is a component-building technique and is one of the transformations required for Assignment 1.

52:27 Base Cases, Union, and Concatenation Constructions

The regular expression epsilon accepts only the empty string, so its base-case machine connects its start to its accepting state with an epsilon transition.
The empty-language expression has start and accepting states but no connecting transition; a symbol such as 0 gets a single transition labeled 0.
For R + S, a new start branches by epsilon into the R and S machines and their accepting paths lead to one new accepting state.
For concatenation RS, connect R's accepting state to S's start with epsilon, reusing R's start and S's accepting state.

56:24 Kleene Star with Epsilon Paths for Zero or More Repetitions

The R* construction adds a new start and accepting state and makes R's former accepting state non-accepting.
An epsilon path from the new start directly to the new accepting state allows zero repetitions.
Epsilon transitions into R and back from R's former accepting state allow one or more repetitions; the construction follows the specific mechanism given in the course slides.

1:00:25 Constructing the Epsilon-NFA for (0 + 1)*

First build separate one-transition machines for 0 and 1, then combine them with the union construction for 0 + 1.
Apply the Kleene-star construction to the union machine by adding new start and accepting states.
The direct epsilon path accepts zero repetitions, while the loop through the union machine permits any sequence of 0s and 1s.

1:03:55 Combining (0 + 1)*, a Literal 1, and (0 + 1)

The worked expression is (0 + 1)*1(0 + 1), built from the already constructed starred machine, a single-symbol 1 machine, and a final union machine.
Use explicit epsilon transitions between concatenated components to match the construction method specified in the lecture slides.
For concatenation, the leftmost machine supplies the overall start state and the rightmost machine supplies the overall accepting state.

1:08:41 Next Steps: Epsilon-NFA Conversion and Object-Oriented Design

Jackie Wang plans to cover the critical steps for converting epsilon-NFAs to DFAs in the next class.
The upcoming course detour introduces object-oriented concepts and design patterns to support studying ANTLR 4 tutorial material.
Topics previewed include polymorphism, dynamic binding, Composite, and Visitor.

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