Save this video free

CSCD 420 Nov 18 2026

Chris Cain · 50:56 · Watch on YouTube

Part of Eastern Washington University CSCD 420. See all 33 lectures and search them

These notes were made with YouTube Collector. Paste any YouTube link and get the same: a summary, chapters and a searchable transcript.

Overview

Chris Cain connects undecidability and computational complexity to practical software decisions, using the Post correspondence problem and context-free grammars to explain why some language questions have no general algorithm. He then introduces compiler architecture, tracing source code through scanning, parsing, type checking, intermediate code optimization, and target-code generation, with examples involving Java bytecode, the JVM, and DFA-based token recognition.

Key takeaways

Chapters

0:00 Course Deadlines and Why Undecidability Matters
4:17 Post Correspondence Problem as a Reduction Target
7:27 Context-Free Grammar Ambiguity and PCP Reductions
12:47 Undecidable Questions About Context-Free Languages
17:06 Single-Tape Versus Two-Tape Turing Machine Efficiency
20:44 Compiler Targets, Assembly, and Java Bytecode
25:13 Compiler Pipeline: Parsing Through Code Generation
33:58 Tokens, Token Types, and Source-Code Examples
38:35 DFA-Based Scanning and Lexical Error Detection
47:27 Grammar Parsing and Building the Parse Tree

Keep these chapters and the full searchable transcript in your own library.

Transcript excerpt

0:03 All right, we're getting started. We have an assignment due tomorrow. We have a an exam coming up in the near future. I've released a study guide, but that will be for review for Monday and Tuesday of next week before we take an exam the day we get back from break. We're also barreling toward our final project. Remember that there will be one more project in here in addition to a final during violence week. So, there's a lot stacking up toward the end of the course. Be ready. Be prepared for a relatively busy last couple of weeks. Whatever you can do over break to get ahead, it'll serve you well before the end of the

0:51 quarter. questions about schedule before we dive into. All right, we last time were talking about undecidable problems. We had finished talking about really the halting problem and this idea of there are algorithms that touring machines can't solve. I guess algorithm is the wrong word here because algorithm is a recursive process. But there are languages out there that cannot be represented by touring machines. And one language would be touring machine string pairs where the string halts on that touring machine. And we found that we could reduce quite

1:40 a few other problems to the halting problem or similar problems. And we found out that a lot of interesting questions that we could ask about recursively innumerable languages were undecidable. Even the very basic questions like is this language empty or is the language finite? Questions that were very easy over every other language class that we've seen or talked about this quarter was impossible to answer for recursively innumerable languages. We're transitioning here into kind of why we care about those reductions because it seems like at this point in

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

In this course

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.

Want the full transcript?

Save this video in YouTube Collector to get its complete searchable transcript, your own AI summaries, and a library that keeps every video you collect in one place.