CSCD 420 Oct 27 2026
Watch on YouTube →
Overview
Chris Cain reviews how Greibach normal form (GNF) productions translate into NPDA transitions, then distinguishes deterministic pushdown automata from NPDAs and explains why some context-free languages lack deterministic parsers. The lecture connects deterministic context-free languages to simple and LL grammars, lookahead, and linear-time parsing, and closes with a worked GNF-conversion procedure plus guidance on homework and exam preparation.
Key takeaways
- A GNF production maps directly to an NPDA move: consume its leading terminal, pop its left-hand non-terminal, and push the right-hand non-terminals.
- A DPDA must have at most one available move for each input-symbol and stack-top combination; a lambda move must be exclusive for that stack-top symbol.
- NPDAs can explore multiple parsing branches on the same input, while DPDAs cannot; some context-free languages therefore have no deterministic pushdown representation.
- The language classes form a strict inclusion hierarchy: regular languages are deterministic context-free, and deterministic context-free languages are a proper subset of context-free languages.
- For suitable grammars, LL parsing uses bounded lookahead and runs in linear time, compared with CYK's cubic-time parsing.
- GNF conversion removes leading non-terminals by substituting their productions, eliminates unused symbols, and replaces later terminals with non-terminals that derive them.
Chapters
- Students can email Chris Cain by Friday with topics needing practice problems, helping determine whether Monday or Tuesday review is needed.
- For equity-distribution homework, begin with the given money amounts; when a derivation begins with a non-terminal, expand its productions before splitting.
- CYK questions require tables for each string; students may show the detailed process for one and state that they applied the same process to the others.
- Handwritten CYK tables may be photographed and included in a LaTeX submission, provided the images are legible.
- GNF productions have a terminal first, followed by zero or more non-terminals, enabling a direct NPDA construction.
- For each production, the NPDA reads the leading terminal, pops the production's left-hand non-terminal, and pushes the right-hand non-terminals.
- An initial epsilon transition replaces the bottom-of-stack marker with the start symbol above it.
- A final transition can accept once the input is consumed and only the bottom-of-stack marker remains; a separate final state is optional.
- The next grammar is already in GNF, so it can be used without a preliminary conversion.
- The construction needs only a small fixed set of states because the stack's top non-terminal determines which productions are available.
- Each grammar production becomes a transition, such as reading A while replacing S, or reading B while removing B from the stack.
- For a large grammar, a transition list is often clearer than drawing a graph with a self-edge for every production.
- The NPDA-to-grammar construction assumes a single final state and acceptance with an empty stack; multiple final states can be consolidated by adding transitions.
- The construction also assumes moves change stack size by one symbol, either increasing or decreasing it.
- Cain introduces deterministic pushdown automata (DPDAs) as the missing deterministic counterpart to the NPDA model used for context-free languages.
- A DPDA permits at most one move for each combination of current state, next input symbol, and top-of-stack symbol.
- Transitions may read the same input symbol when they apply to different stack-top symbols, because the stack distinguishes which move is available.
- A lambda transition is allowed, but for its stack-top symbol it must be the only outgoing option; it cannot compete with an input-consuming move.
- Unlike the familiar NFA-to-DFA conversion, there is no general procedure to convert every NPDA into an equivalent DPDA.
- Cain compares L1 = {aⁿbⁿ} with L2 = {aⁿb²ⁿ}; both are context-free and can be described with grammars.
- Their union can be represented by a new start production selecting either grammar, but the initial input symbol does not reveal which branch will ultimately accept.
- An NPDA can branch into both parsing paths on the same input, while a DPDA cannot choose two moves for the same input and stack-top combination.
- Cain presents this union example as intuition for nondeterminism, not as a formal proof that no equivalent DPDA exists.
- A deterministic context-free language is one accepted by some DPDA; deterministic parsing can be more efficient than general context-free parsing.
- A sentential form, such as S ⇒ aSb ⇒ aabbb, records the partially derived string, including its remaining non-terminals.
- Simple grammars constrain production choices so the current input symbol determines which production to apply.
- LL grammars use bounded lookahead to choose a leftmost derivation; looking ahead two characters can resolve choices that a single character cannot.
- Some grammars remain ambiguous under every finite amount of lookahead, while an equivalent rewritten grammar may allow deterministic parsing.
- The lecture distinguishes grammar-level determinism from language-level capability: some context-free languages have no deterministic representation.
- Regular languages lie inside deterministic context-free languages, which lie inside the context-free languages; each containment is strict.
- LL parsing runs in linear time for suitable grammars, compared with the cubic-time CYK algorithm discussed earlier.
- To remove a leading non-terminal from a production, substitute each of that non-terminal's possible derivations into the production.
- When substitution introduces multiple possible starting terminals, create separate productions for each starting option.
- Remove non-terminals that become unused, then replace any second terminal in a production with a non-terminal that derives that terminal.
- For homework, show enough intermediate steps to explain the substitutions and replacements, even if repetitive algebra is abbreviated.
- Students should include brief explanations of grammar-conversion steps, such as identifying which production was substituted.
- The next class begins the context-free pumping lemma; Cain notes that the upcoming exam will not include it.
- The lecture's grammar, NPDA, and determinism material completes the current context-free-language unit.
Transcript excerpt
0:02 Okay. We have an assignment due tomorrow. >> [clears throat] >> We settled on an exam for each firm tomorrow. So, as I posted on the Canvas announcement, I don't have practice problems as prepared for this exam as I did for the first exam. I have them prepared again for exam three. There's more challenging workflow problem-solving type problems there than there are here. I find that having the exact kinds of practice problems that we did wasn't quite as useful in the exam to prep. But, maybe it is and I just haven't made it yet. So, I
0:48 said, "Go ahead and give me Send me an email by Friday. The earlier, the better." with any topics that you'd like some practice problems on and I can see if I can dig up some practice problems or those kinds of content, those kinds of problems that you might see on the exam. That'll help me prepare for Monday and or Tuesday and determine if we need two days of review or if one day is going to cover it. Just questions. So, we'll make that decision closer to the end of the week as I get a sense of whether people want the extra time or not. >> Question. >> There was a comment yesterday about um equity distribution. >> Yeah. Yeah, I think given what we covered
1:38 yesterday in class, I think we can make the ones that are on the homework work. I double-checked how difficult those are and they're not completely insane. >> I only have one question regarding that home. How are you supposed to get carried in front of a non >> It's It's prepared with uh actual money. >> Okay. and then I didn't write from there. >> Yeah, if it starts with a non-terminal,
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.