[HD] EECS4302 F26 - 2026-10-06 (Tuesday) - Lecture 8

Overview

Jackie Wang demonstrates lazy subset construction for converting an NFA to a DFA, then extends the procedure to ε-NFAs using ε-closure and explains how accepting subsets are identified. The lecture shifts to recursive software design and compiler-relevant object-oriented concepts: composite structures, static-type member checks, safe inheritance assignments, dynamic types, and dynamic binding.

Key takeaways

Subset construction needs only reachable subsets: the example NFA has three states and eight possible subsets, but exploring transitions from the initial subset discovers only the subsets required for its DFA.
A DFA subset is accepting exactly when it contains at least one accepting NFA state; therefore, any subset intersecting F is marked accepting.
For an ε-NFA, compute each DFA transition by taking the union of ordinary transitions for the input symbol and then applying ε-closure to every resulting state; the initial DFA state is also an ε-closure.
Static type controls compile-time member access: a Student reference cannot use subclass-only members such as ResidentStudent.premiumRate, even if the referenced object might be a ResidentStudent.
Allowing a parent-typed object to flow into a subclass reference can cause runtime failure, because subclass-only fields may not exist on the actual parent object.
Dynamic binding chooses an overridden method from the object's current dynamic type, while the reference's static type remains fixed; reassignment from C1 to C2 changes which implementation of m runs.

Chapters

0:00 Assignment Deadlines, Project Teams, and the Lecture Plan

Assignment 1 is due Wednesday; students should submit their best attempt even if the ε-NFA-to-DFA conversion is incomplete.
Assignment 2 and the project have been released, and Jackie Wang plans to review their instructions on Thursday before reading week.
Students are encouraged to form teams of two or three and raise project questions early.

2:37 Subset Construction: Representing DFA States as NFA-State Sets

Each state in the output DFA represents a subset of states from the input NFA.
An NFA with three states has up to 2³ = 8 possible subset states, but lazy evaluation explores only reachable subsets.
The example NFA uses Q0, Q1, and Q2, with Q2 as its accepting state.

7:10 Starting the DFA from {Q0} and Computing Its First Transitions

The output DFA begins in the singleton subset {Q0}, corresponding to the NFA's initial state.
For the example alphabet {0, 1}, taking 0 from Q0 reaches both Q0 and Q1, creating the subset {Q0, Q1}.
Taking 1 from Q0 returns to {Q0}, illustrating the distinction between an already discovered subset and a newly reached one.

11:40 Expanding {Q0, Q1} with Unioned NFA Transitions

For each symbol, compute the union of transitions from every NFA state in the current subset.
From {Q0, Q1} on 0, Q0 reaches {Q0, Q1} while Q1 has no 0-transition, so the resulting subset is {Q0, Q1}.
From {Q0, Q1} on 1, the combined transitions reach {Q0, Q2}, which is added as a newly discovered DFA state.

15:15 Marking Accepting Subsets and Completing the Reachable DFA

A DFA subset is accepting if its intersection with the original NFA accepting set is nonempty.
Because {Q0, Q2} contains Q2, it is accepting even though it also contains the nonaccepting state Q0.
Expanding {Q0, Q2} leads back to already discovered subsets, so the reachable-state construction is complete without enumerating all eight theoretical subsets.

18:20 Adding ε-Closure to the NFA-to-DFA Conversion

For an ε-NFA, the output DFA's initial subset is the ε-closure of the NFA's initial state; the example starts from {Q0, Q1}.
To compute a transition, first union the ordinary transitions for the input symbol across all states in the current subset.
Then take the ε-closure of every state in that result and union those closures to form the destination subset.

24:14 From Automata Conversion to Scanner Generation and Design Patterns

The course emphasizes applying the conversion procedure and understanding its notation rather than proving DFA equivalence.
ANTLR 4 turns token regular expressions into ε-NFAs, then DFAs, and can minimize the resulting DFA.
The next software-design topics are composite and visitor patterns, both relevant to recursive compiler structures.

26:10 Composite Design Motivation: Recursive Systems and Hardware Assemblies

Composite design treats individual components and larger assemblies through a structure that can be processed recursively.
The hardware example distinguishes base equipment such as hard drives and power supplies from containers such as chassis and cabinets.
Compiler syntax trees have the same recursive character: expressions and statements contain nested components that must be traversed repeatedly.

30:58 Leaves, Internal Nodes, and the Equipment Composite Tree

Video cards, hard drives, DVD/CD-ROM drives, and power supplies are leaf or external nodes because they cannot contain other equipment.
Chassis and cabinets are composite components that contain children; a cabinet may hold multiple components, so the structure is a general tree rather than necessarily binary.
The same distinction maps to data-structure terminology: base components are leaves, while composites are internal nodes.

34:01 Project Instructions, Team Coordination, and ANTLR 4 Preparation

The course site contains the project specification and examples from earlier course iterations that students can inspect for inspiration.
Each team must submit one file listing its members by the following Wednesday.
Jackie Wang recommends that teammates learn both ANTLR 4 and effective collaboration, and asks students to read the project guidance before Thursday.

37:19 Static Types Determine Which Members Compile

A variable's declared type is its static type, and the static type determines which attributes and methods are allowed after dot notation.
A Student reference can access inherited members such as name, courses, register, and getTuition, but not subclass-only members such as premiumRate.
ResidentStudent adds premium-rate members, while NonResidentStudent adds discount-rate members; neither sibling's unique members are available through the other sibling's static type.

46:56 Why Assigning a Parent Object to a Subclass Reference Is Unsafe

Assigning a ResidentStudent reference to a Student variable is valid, but assigning a Student reference to a ResidentStudent variable is not generally safe.
If the reverse assignment compiled, the subclass reference could point to a plain Student object that has no premiumRate field.
A compiler supporting inheritance must check assignment compatibility across the class hierarchy, including any chosen limits on inheritance depth.

55:19 Static Type, Dynamic Type, and Dynamic Binding in Overridden Methods

Static type comes from the variable declaration and remains fixed; dynamic type is the class of the object currently referenced and can change after reassignment.
In the example, a variable declared as C begins with no object, then points first to C1 and later to C2; method calls do not change its static type.
Dynamic binding selects the overridden method using the object's dynamic type, so calls to obj.m dispatch to C1's implementation before reassignment and C2's afterward.

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.