CSCD 420 Oct 22 2026
Watch on YouTube →
Overview
Chris Cain introduces nondeterministic pushdown automata (NPDAs) as state machines that recognize context-free languages by augmenting finite control with an unbounded stack. He defines PDA transitions and acceptance, then constructs machines for aⁿbⁿ and for strings over {a, b} with equal counts of each symbol, using stack symbols to track unmatched letters.
Key takeaways
- A pushdown automaton extends finite-state control with an unbounded stack, giving it the memory needed for context-free patterns such as matching the number of a's with the number of b's.
- A PDA transition pops exactly one stack symbol but may push any finite string, so replacing one marker with two increases the stack depth by one.
- Acceptance requires a final state, complete input consumption, and an empty stack under a consistent convention for the bottom marker.
- For aⁿbⁿ, pushing once per a and popping once per b tracks equality, while separate control states enforce that all a's precede all b's.
- For strings with equal counts of a's and b's in any order, two stack-marker types track which symbol is currently in excess and by how much.
- Instantaneous descriptions (q, w, u) capture a PDA's state, unread input, and stack, making execution traces clearer when many transitions share the same state.
Chapters
- The CYK algorithm remains asymptotically cubic, Θ(n³), despite diagonal-table and substring-count factors reducing its constant.
- The next homework is expected that day, and the class will review exam problems in person the following day without recording that portion.
- DFAs and NFAs have only finite memory, so they cannot recognize languages requiring unbounded information about an input prefix.
- For aⁿbⁿ, a machine must remember how many a's appeared so it can match them against the later b's.
- Every regular language is context-free, but context-free languages also include nonregular languages such as aⁿbⁿ.
- A PDA retains the state set, input alphabet, initial state, and final states used by finite automata, while adding a separate stack alphabet.
- A transition depends on the current state, an input symbol or λ, and the stack-top symbol; it specifies a next state and a string of symbols to push.
- The initial stack marker, often Z, represents the stack bottom; transitions that pop it must restore it if the machine needs to preserve the marker.
- Unlike a DFA, a PDA need not define a transition for every possible input and stack-symbol combination.
- Each PDA transition pops exactly one stack symbol, but can push zero or more symbols.
- A stack no-op is represented by popping the top symbol and pushing that same symbol back.
- For example, a transition reading A while popping B may push CD, changing the stack by replacing B with CD.
- The example machine pushes one marker for each input a, then switches to reading b's and pops one marker per b.
- Its state structure enforces the order a* followed by b*, since there is no transition back to the a-reading state after entering the b-reading state.
- Nondeterministic branches can choose among transitions, with acceptance requiring at least one branch to succeed.
- A string is accepted only when the machine reaches a final state, consumes the entire input, and satisfies the chosen empty-stack convention.
- The stack may be considered empty when the bottom marker Z is removed, or when Z is the only symbol left, provided the convention is consistent.
- Cain identifies a textbook transition that incorrectly consumes an a when handling a⁰b⁰; that transition should read λ to accept the empty string.
- For aⁿbⁿ, the stack markers must be exhausted exactly when the input ends, preventing acceptance with unmatched a's or unread b's.
- PDA transition functions are partial: defining every input-symbol and stack-symbol combination would make machines unnecessarily large.
- An instantaneous description is a triple (q, w, u), recording the current state, unread input, and complete stack contents.
- A turnstile relation between descriptions represents one legal PDA transition and makes execution traces easier to follow than dense state diagrams.
- The target language contains strings over {a, b} with equal numbers of a's and b's, regardless of their order.
- A single stack symbol cannot represent both possible imbalances, so the stack needs one marker for excess a's and another for excess b's.
- The count of each marker records the current difference between the number of a's and b's.
- The PDA uses one working state because the order of a's and b's is unrestricted, plus a final state for acceptance.
- When the stack records excess a's, reading a adds a zero and reading b removes one; when it records excess b's, reading b adds a one and reading a removes one.
- The stack alphabet uses 0 and 1 for the two imbalances and Z for the bottom marker, distinct from input symbols a and b.
- The machine can nondeterministically try to finish when only Z remains, then accept only if the input is also fully consumed.
- Cain traces the string abba, updating the stack from Z to Z0, back to Z, then to Z1 and Z11 before the final a removes one marker.
- The trace ends with an unmatched b marker, so abba is rejected because it contains three b's and one a.
- A λ transition to the final state can accept the empty string, while taking that transition before the input ends cannot produce acceptance.
- Keeping input symbols a and b distinct from stack symbols 0, 1, and Z helps prevent confusion when specifying transitions.
Transcript excerpt
0:02 empty class this morning. Interesting. How are we all doing with you? Good. Right. We should be getting the next homework to you today. What else? We're going to be going over exams tomorrow. So, if that's something that you'd like to attend in person to be able to look at your exam, compare it to, I'll be going over all the problems and I will not be recording it. That's a good day to attend. Yeah. >> I'm going to skip that cuz I haven't taken the test yet. >> Yes. >> Is that all we have reserved for tomorrow? >> There may be a little bit of extra
0:48 content at the end of it depending on how long it takes to go over. I'll I'll transition to that, but I'll also start recording at that point so that if if you don't want to do that or if you can't do that, then there will be a recording of the rest of the class, a very short recording probably, but I typically can do it a little bit faster than the class period. All right, last time we talked about the CYK algorithm. We drew that out, went over that, saw that it was an interesting dynamic programming algorithm. And the last thing I wanted to say about it was reiterate that the complexity is cubic. It is a little bit better than cubic but not asinmtoically. So it's some fraction n cubed and that's because we have a diagonal table. So
1:37 that is a factor of 1/2. And then for each of the strings themselves, we're breaking them into some number of substrings that are not the same as the number of characters in the string. That's another multiplicative factor that's less than one. So we end up with
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.