CSCD 420 Oct 01 2026

Overview

Chris Cain reviews nondeterministic finite automata (NFAs), showing how branching, missing transitions, and lambda transitions make some language-recognition designs easier than with deterministic finite automata (DFAs). He develops two union-language examples, then explains the subset construction for converting an NFA into an equivalent DFA, including a worked example whose reachable DFA uses three states out of a possible eight.

Key takeaways

NFA branching models alternative computations: a string is accepted if at least one explored path reaches an accepting state.
A missing NFA transition simply ends that path, while a DFA must route every state and input symbol somewhere, commonly to a trap state.
An NFA for a union should choose or branch between the complete language alternatives; allowing paths to switch alternatives can accept strings outside both languages.
Subset construction turns an NFA into a DFA by making each DFA state a subset of NFA states, yielding an upper bound of 2^k states for an NFA with k states.
In the worked three-state NFA, only {Q0}, {Q1, Q2}, and the empty set are reachable, so the equivalent DFA needs 3 states rather than all 8 possible subsets.

Chapters

0:00 Exam Timing, Assignment Turnaround, and Fall Scheduling

Chris Cain says the exam may shift by one week, with a schedule decision promised by the following day.
A new assignment is expected soon and is due the following Wednesday.
Whether the exam proceeds as scheduled depends partly on the grader returning assignment results within about 24 hours.

1:45 Nondeterminism as Choice, Parallelism, and Grammar Search

Cain presents nondeterminism as a magical choice that always selects a successful branch or as infinite parallelism that explores all branches simultaneously.
P versus NP asks whether deterministic polynomial-time problems equal nondeterministic polynomial-time problems; it remains unproved, and Cain says the answer is probably no.
Grammar alternatives create nondeterministic search: to test whether a string such as ABBA can be generated, a process can explore alternative productions.

4:54 Three NFA Features That DFAs Do Not Share

An NFA need not define an outgoing transition for every alphabet symbol at every state, unlike a DFA's total transition function.
Lambda transitions move between states without consuming an input character.
An NFA can have multiple outgoing edges with the same character from one state, representing alternative branches.

7:21 Planning an NFA for a Union of A-String Languages

The first design problem combines A^n for n ≥ 3 with strings of the form ABA^n.
Because both alternatives begin with A and no accepted string begins with B, the start state needs an A transition but no B transition.
Cain recommends designing one side of the union first, then incorporating the other branch.

12:22 Building the A^n and ABA^n Union NFA

For A^n where n ≥ 3, the construction uses states to count the first three As, then loops on A from an accepting state.
For the ABA^n branch, the automaton consumes A, then B, then at least one A; the final A state can loop to accept additional As.
Equivalent NFAs can share states or use separate states, but a loop at the start would lose track of whether three As had been read.

18:11 Starting the Odd-A and AB-B^n Union Problem

The second language is the union of A^n for odd n and ABB^n for n ≥ 0.
The empty string is not accepted: zero is not an odd exponent, while the second branch starts with A and B.
The initial A creates ambiguity because it may begin either an odd-length A string or the AB followed by Bs pattern.

23:17 Preventing Invalid Branch Switching in the Union NFA

A shared accepting state that loops between odd and even A counts can incorrectly accept AAABBB by combining part of each language's path.
Union means a complete string must belong to the left-hand language or the right-hand language; a path cannot switch languages halfway through.
The corrected NFA branches on the first A, tracking odd-length A strings separately from the A-then-B-and-more-Bs alternative.
For an input such as AB, the NFA explores both branches, rejects the A-only path, and accepts through the ABB^n path with n = 0.

33:20 Why NFA-to-DFA Conversion Uses the Power Set

NFAs and DFAs recognize the same regular languages, so an NFA design can be converted to an equivalent DFA.
A DFA state represents a set of NFA states that could be active after reading the same input.
An NFA with k states has at most 2^k possible state subsets, including the empty set, though unreachable subsets do not need to be included.

40:31 Converting a Lambda-Transition NFA into a Three-State DFA

The example starts with the subset {Q0}, since Q0 is the only state reachable without consuming input.
On A, the NFA reaches Q1 and then can take a lambda transition to Q2, so the DFA moves to {Q1, Q2}; that DFA state is accepting because Q1 is final.
On B from {Q0}, no NFA state is reachable, so the DFA enters the empty-set trap state, which loops on every alphabet symbol.
From {Q1, Q2}, A leads back to {Q1, Q2} and B leads to {Q0}; the reachable DFA has 3 states, compared with the 8 possible subsets of a 3-state NFA.

47:37 Binary NFA Conversion Practice and Class Follow-Up

The next exercise uses a binary NFA where Q0 has two 0-transitions, one returning to Q0 and one leading to Q1.
From Q1, either 0 or 1 leads to Q2, and Q2 loops on 1; the class will convert this NFA at the start of the next meeting.
Cain notes that unnecessary transitions can preserve a language but produce a larger, less clear automaton, so reachable and useful states should guide the construction.

Transcript excerpt

0:00 You know, what's taking up our plate? 30. All right, tonight we're going to get started. How's everybody doing? Silence. I would, according to the syllabus, owe you a study guide by Friday for an exam for next week. I am thoroughly considering with the TA pushing that back a week. So, I'm not 100% sure about that yet, but I will have an answer for you by tomorrow. We're looking at assignments, what we've covered so far, and we'll again have an answer for you tomorrow with regards to that. So, be prepared for either at this point and clarity tomorrow. New assignment, if it's not up, will be

0:48 up very soon. And that will be due next Wednesday. A lot of what whether this exam happens next week or not will be based on greater schedule, will the greater be able to turn around this assignment by within a day so that you will have the ability to see how you did and what you should be considering or studying before the exam. And he has what, 24 hours to do that, so it's Fall is the difficult quarter to run this class for that reason. We lose the Monday and Tuesday that we would otherwise have at the end of week three. So, there's always this crunch in fall that occasionally messes with things and changes things. So, I typically take it on a quarter-by-quarter basis. Questions about schedule before we dive

1:37 back into content? Okay. Last time we introduced the concept of non-determinism and we're starting to talk about what that means or how we could view non-determinism. I gave you three ways to think about it. You could think about it as magic whenever you're given a branching factor and you need to make a decision on that.

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, Chris Cain.