\documentclass[11pt]{article}
\usepackage{mathnotes}
\discipline{UCLA COMPUTER SCIENCE FIELD NOTES}
\course{CS 181}{Theory of Computing and Automata}{Regular languages, context-free languages, Turing machines, decidability, and computability}

\begin{document}
\makemathcover
\coursefrontmatter{
\begin{curriculumtable}
\unitline{1}{Languages, proofs, and finite automata}{Explain the model, apply it to a concrete case, and defend the relevant correctness or design decision.}
\unitline{2}{Regular expressions and closure}{Explain the model, apply it to a concrete case, and defend the relevant correctness or design decision.}
\unitline{3}{Nonregularity and pumping}{Explain the model, apply it to a concrete case, and defend the relevant correctness or design decision.}
\unitline{4}{Context-free grammars and parse structure}{Explain the model, apply it to a concrete case, and defend the relevant correctness or design decision.}
\unitline{5}{Pushdown automata and CFL properties}{Explain the model, apply it to a concrete case, and defend the relevant correctness or design decision.}
\unitline{6}{Turing machines and recognizability}{Explain the model, apply it to a concrete case, and defend the relevant correctness or design decision.}
\unitline{7}{Reductions and undecidability}{Explain the model, apply it to a concrete case, and defend the relevant correctness or design decision.}
\unitline{8}{Computability boundaries and classification}{Explain the model, apply it to a concrete case, and defend the relevant correctness or design decision.}
\unitline{9}{Integration workshop}{Connect at least three chapters in one end-to-end problem and explain where their contracts meet.}
\unitline{10}{Synthesis and project review}{Audit assumptions and explain a complete solution from interface to failure handling.}
\end{curriculumtable}
}{\curriculumsource{https://catalog.registrar.ucla.edu/course/2025/COMSCI181}}

\section{Languages, proofs, and finite automata}

\begin{idea}
A language is a set of strings. DFAs have one transition per symbol; NFAs permit several and epsilon moves but recognize the same regular languages. Extended transition functions formalize complete-string behavior.
\end{idea}
% MASTERCLASS EXPANSION
\subsection{Rebuild the chapter from first principles}
The claim I need to own is this: A language is a set of strings. DFAs have one transition per symbol; NFAs permit several and epsilon moves but recognize the same regular languages. Extended transition functions formalize complete-string behavior. I do not count that as learned just because the sentence looks familiar. I should be able to name the objects, state what changes and what stays fixed, recover the rule from the definitions, and explain why the result is allowed.

\begin{move}
\textbf{My working sequence}
\begin{enumerate}
  \item \textbf{Translate.} Rewrite the prompt in the language of languages, proofs, and finite automata. List the known quantities, the unknown, the units or types, and any hidden constraint.
  \item \textbf{Choose.} State the theorem, model, algorithm, accounting rule, or physical law before substituting values. This is where I make the assumption visible.
  \item \textbf{Execute.} Work one justified step at a time and keep intermediate state readable enough that I can audit it later.
  \item \textbf{Verify.} Check a boundary case, sign, unit, invariant, order of magnitude, or alternative derivation. Then translate the result back into an ordinary sentence.
\end{enumerate}
\end{move}

\subsection{Details I would refuse to skip}
\begin{itemize}
  \item \textbf{Definitions:} I should be able to define every technical noun in the chapter without using that same noun in the definition.
  \item \textbf{Assumptions:} I write the condition that makes the method legal beside the method itself. A correct procedure under the wrong assumptions is still a wrong answer.
  \item \textbf{Representation:} I move freely among words, equations or code, a diagram, and a small numerical example. If one representation disagrees with another, that disagreement is useful evidence.
  \item \textbf{Failure modes:} I keep the nearest counterexample in mind: the boundary where the rule changes, the invariant breaks, or the model stops matching reality.
  \item \textbf{Communication:} My final answer names what the result means and what it does not establish. I do not let notation do the explanatory work for me.
\end{itemize}

\begin{sanitybox}
\textbf{Closed-note check.} Can I teach languages, proofs, and finite automata on a blank page, derive or reconstruct its main rule, work a fresh example, and diagnose a deliberately broken solution? If I can only recognize the finished work, I am not done.
\end{sanitybox}

\subsection{How this chapter connects}
I read this chapter as the bridge from the course foundations to regular expressions and closure. The earlier material supplies the language and constraints; this chapter adds a new reasoning move; the later material asks me to use that move without being told its name. That connection matters because exams and real projects mix chapters on purpose.


\subsection{What I need to be able to do}
For this chapter, I should be able to define the objects and state involved, state the governing invariant or contract, trace a small example without hand-waving, and explain which assumption makes the method valid. I should also be able to compare this model with the nearest alternative and say what failure would make me switch approaches.

\subsection{Deep notes}
\begin{itemize}
\item \textbf{Model.} A language is a set of strings.
\item \textbf{Mechanism.} DFAs have one transition per symbol; NFAs permit several and epsilon moves but recognize the same regular languages.
\item \textbf{Boundary.} Extended transition functions formalize complete-string behavior.
\item \textbf{Decision test.} I should be able to say when languages, proofs, and finite automata is the right model, when its assumptions fail, and what evidence would change my choice.
\end{itemize}

\begin{studenttake}
I separate the machine drawing from the proof of what its state means.
\end{studenttake}

\begin{plainbox}
A language is a set of strings.
\end{plainbox}

\begin{examplebox}
A useful way to work this chapter is to make the smallest concrete instance, write the state or contract explicitly, and then scale the reasoning only after that instance behaves correctly. The worked question below makes that reasoning concrete: Convert an NFA to a DFA. The conclusion is Each DFA state is a set of possible NFA states. Start with epsilon closure, transition the whole set on each symbol, close again, and mark sets containing an accepting NFA state.
\end{examplebox}

\begin{warningbox}
The common mistake is to memorize the visible procedure while dropping its precondition. I write the assumption beside the method and test one boundary case before trusting the result.
\end{warningbox}

\begin{chapterpractice}
\textbf{Practice.} Convert an NFA to a DFA.

\textbf{Solution.} Each DFA state is a set of possible NFA states. Start with epsilon closure, transition the whole set on each symbol, close again, and mark sets containing an accepting NFA state.

\medskip
\textbf{Practice 2.} Give a short oral explanation of languages, proofs, and finite automata that includes its model, one assumption, one failure mode, and one comparison with a neighboring method.

\textbf{Solution.} A strong answer begins with the model in the blue box, names the assumption that licenses the method, uses the common miss above as the failure mode, and chooses the comparison according to the decision test in the deep notes. The goal is not one memorized sentence; it is a four-part explanation I can reproduce on a new example.

\medskip
\textbf{Mastery practice A.} Reconstruct languages, proofs, and finite automata from a blank page. Include the central definition, the governing rule, one required assumption, and one boundary case.

\textbf{Solution.} Start from the blue idea box, but rewrite it in my own words. Identify the objects and state, name the rule before using it, copy the relevant assumption from the details audit, and choose a boundary where that assumption becomes equality or fails. A complete solution explains why each part belongs; a list of vocabulary is not enough.

\medskip
\textbf{Mastery practice B.} A classmate gets a polished-looking answer to a languages, proofs, and finite automata problem but never states a model or checks the result. Write the shortest useful review of that solution.

\textbf{Solution.} I would ask four concrete questions: What exactly are the inputs and desired output? Which rule licenses the main step? Which assumption could invalidate it? Which independent check supports the conclusion? If the answer cannot survive those four questions, I treat the numerical or verbal result as unverified.

\end{chapterpractice}

\section{Regular expressions and closure}

\begin{idea}
Regular expressions, DFAs, and NFAs are equivalent descriptions. Product constructions prove closure under union, intersection, and difference; state elimination or structural construction moves between regex and machines.
\end{idea}
% MASTERCLASS EXPANSION
\subsection{Rebuild the chapter from first principles}
The claim I need to own is this: Regular expressions, DFAs, and NFAs are equivalent descriptions. Product constructions prove closure under union, intersection, and difference; state elimination or structural construction moves between regex and machines. I do not count that as learned just because the sentence looks familiar. I should be able to name the objects, state what changes and what stays fixed, recover the rule from the definitions, and explain why the result is allowed.

\begin{move}
\textbf{My working sequence}
\begin{enumerate}
  \item \textbf{Translate.} Rewrite the prompt in the language of regular expressions and closure. List the known quantities, the unknown, the units or types, and any hidden constraint.
  \item \textbf{Choose.} State the theorem, model, algorithm, accounting rule, or physical law before substituting values. This is where I make the assumption visible.
  \item \textbf{Execute.} Work one justified step at a time and keep intermediate state readable enough that I can audit it later.
  \item \textbf{Verify.} Check a boundary case, sign, unit, invariant, order of magnitude, or alternative derivation. Then translate the result back into an ordinary sentence.
\end{enumerate}
\end{move}

\subsection{Details I would refuse to skip}
\begin{itemize}
  \item \textbf{Definitions:} I should be able to define every technical noun in the chapter without using that same noun in the definition.
  \item \textbf{Assumptions:} I write the condition that makes the method legal beside the method itself. A correct procedure under the wrong assumptions is still a wrong answer.
  \item \textbf{Representation:} I move freely among words, equations or code, a diagram, and a small numerical example. If one representation disagrees with another, that disagreement is useful evidence.
  \item \textbf{Failure modes:} I keep the nearest counterexample in mind: the boundary where the rule changes, the invariant breaks, or the model stops matching reality.
  \item \textbf{Communication:} My final answer names what the result means and what it does not establish. I do not let notation do the explanatory work for me.
\end{itemize}

\begin{sanitybox}
\textbf{Closed-note check.} Can I teach regular expressions and closure on a blank page, derive or reconstruct its main rule, work a fresh example, and diagnose a deliberately broken solution? If I can only recognize the finished work, I am not done.
\end{sanitybox}

\subsection{How this chapter connects}
I read this chapter as the bridge from languages, proofs, and finite automata to nonregularity and pumping. The earlier material supplies the language and constraints; this chapter adds a new reasoning move; the later material asks me to use that move without being told its name. That connection matters because exams and real projects mix chapters on purpose.


\subsection{What I need to be able to do}
For this chapter, I should be able to define the objects and state involved, state the governing invariant or contract, trace a small example without hand-waving, and explain which assumption makes the method valid. I should also be able to compare this model with the nearest alternative and say what failure would make me switch approaches.

\subsection{Deep notes}
\begin{itemize}
\item \textbf{Model.} Regular expressions, DFAs, and NFAs are equivalent descriptions.
\item \textbf{Mechanism.} Product constructions prove closure under union, intersection, and difference; state elimination or structural construction moves between regex and machines.
\item \textbf{Boundary.} The useful test is whether I can apply regular expressions and closure to a new case and explain the assumption that makes the answer valid.
\item \textbf{Decision test.} I should be able to say when regular expressions and closure is the right model, when its assumptions fail, and what evidence would change my choice.
\end{itemize}

\begin{studenttake}
My shorthand for this chapter is: my shorthand for this chapter is: closure proofs are recipes for building a recognizer, not just facts to memorize.
\end{studenttake}

\begin{plainbox}
Regular expressions, DFAs, and NFAs are equivalent descriptions.
\end{plainbox}

\begin{examplebox}
A useful way to work this chapter is to make the smallest concrete instance, write the state or contract explicitly, and then scale the reasoning only after that instance behaves correctly. The worked question below makes that reasoning concrete: Build a DFA for intersection of L1 and L2. The conclusion is Use state pairs (q1,q2), advance both components on each symbol, and accept only pairs where both component states accept.
\end{examplebox}

\begin{warningbox}
The common mistake is to memorize the visible procedure while dropping its precondition. I write the assumption beside the method and test one boundary case before trusting the result.
\end{warningbox}

\begin{chapterpractice}
\textbf{Practice.} Build a DFA for intersection of L1 and L2.

\textbf{Solution.} Use state pairs (q1,q2), advance both components on each symbol, and accept only pairs where both component states accept.

\medskip
\textbf{Practice 2.} Give a short oral explanation of regular expressions and closure that includes its model, one assumption, one failure mode, and one comparison with a neighboring method.

\textbf{Solution.} A strong answer begins with the model in the blue box, names the assumption that licenses the method, uses the common miss above as the failure mode, and chooses the comparison according to the decision test in the deep notes. The goal is not one memorized sentence; it is a four-part explanation I can reproduce on a new example.

\medskip
\textbf{Mastery practice A.} Reconstruct regular expressions and closure from a blank page. Include the central definition, the governing rule, one required assumption, and one boundary case.

\textbf{Solution.} Start from the blue idea box, but rewrite it in my own words. Identify the objects and state, name the rule before using it, copy the relevant assumption from the details audit, and choose a boundary where that assumption becomes equality or fails. A complete solution explains why each part belongs; a list of vocabulary is not enough.

\medskip
\textbf{Mastery practice B.} A classmate gets a polished-looking answer to a regular expressions and closure problem but never states a model or checks the result. Write the shortest useful review of that solution.

\textbf{Solution.} I would ask four concrete questions: What exactly are the inputs and desired output? Which rule licenses the main step? Which assumption could invalidate it? Which independent check supports the conclusion? If the answer cannot survive those four questions, I treat the numerical or verbal result as unverified.

\end{chapterpractice}

\section{Nonregularity and pumping}

\begin{idea}
The pumping lemma states a necessary repetition property of every infinite regular language. To disprove regularity, choose a witness after the pumping length and defeat every legal split and pump choice.
\end{idea}
% MASTERCLASS EXPANSION
\subsection{Rebuild the chapter from first principles}
The claim I need to own is this: The pumping lemma states a necessary repetition property of every infinite regular language. To disprove regularity, choose a witness after the pumping length and defeat every legal split and pump choice. I do not count that as learned just because the sentence looks familiar. I should be able to name the objects, state what changes and what stays fixed, recover the rule from the definitions, and explain why the result is allowed.

\begin{move}
\textbf{My working sequence}
\begin{enumerate}
  \item \textbf{Translate.} Rewrite the prompt in the language of nonregularity and pumping. List the known quantities, the unknown, the units or types, and any hidden constraint.
  \item \textbf{Choose.} State the theorem, model, algorithm, accounting rule, or physical law before substituting values. This is where I make the assumption visible.
  \item \textbf{Execute.} Work one justified step at a time and keep intermediate state readable enough that I can audit it later.
  \item \textbf{Verify.} Check a boundary case, sign, unit, invariant, order of magnitude, or alternative derivation. Then translate the result back into an ordinary sentence.
\end{enumerate}
\end{move}

\subsection{Details I would refuse to skip}
\begin{itemize}
  \item \textbf{Definitions:} I should be able to define every technical noun in the chapter without using that same noun in the definition.
  \item \textbf{Assumptions:} I write the condition that makes the method legal beside the method itself. A correct procedure under the wrong assumptions is still a wrong answer.
  \item \textbf{Representation:} I move freely among words, equations or code, a diagram, and a small numerical example. If one representation disagrees with another, that disagreement is useful evidence.
  \item \textbf{Failure modes:} I keep the nearest counterexample in mind: the boundary where the rule changes, the invariant breaks, or the model stops matching reality.
  \item \textbf{Communication:} My final answer names what the result means and what it does not establish. I do not let notation do the explanatory work for me.
\end{itemize}

\begin{sanitybox}
\textbf{Closed-note check.} Can I teach nonregularity and pumping on a blank page, derive or reconstruct its main rule, work a fresh example, and diagnose a deliberately broken solution? If I can only recognize the finished work, I am not done.
\end{sanitybox}

\subsection{How this chapter connects}
I read this chapter as the bridge from regular expressions and closure to context-free grammars and parse structure. The earlier material supplies the language and constraints; this chapter adds a new reasoning move; the later material asks me to use that move without being told its name. That connection matters because exams and real projects mix chapters on purpose.


\subsection{What I need to be able to do}
For this chapter, I should be able to define the objects and state involved, state the governing invariant or contract, trace a small example without hand-waving, and explain which assumption makes the method valid. I should also be able to compare this model with the nearest alternative and say what failure would make me switch approaches.

\subsection{Deep notes}
\begin{itemize}
\item \textbf{Model.} The pumping lemma states a necessary repetition property of every infinite regular language.
\item \textbf{Mechanism.} To disprove regularity, choose a witness after the pumping length and defeat every legal split and pump choice.
\item \textbf{Boundary.} The useful test is whether I can apply nonregularity and pumping to a new case and explain the assumption that makes the answer valid.
\item \textbf{Decision test.} I should be able to say when nonregularity and pumping is the right model, when its assumptions fail, and what evidence would change my choice.
\end{itemize}

\begin{studenttake}
I keep the quantifier order visible; choosing the split myself proves nothing.
\end{studenttake}

\begin{plainbox}
The pumping lemma states a necessary repetition property of every infinite regular language.
\end{plainbox}

\begin{examplebox}
A useful way to work this chapter is to make the smallest concrete instance, write the state or contract explicitly, and then scale the reasoning only after that instance behaves correctly. The worked question below makes that reasoning concrete: Use pumping to show \{0\textasciicircum{}n1\textasciicircum{}n\} is not regular. The conclusion is Choose 0\textasciicircum{}p1\textasciicircum{}p. Any first p-symbol pump segment contains only zeros. Pumping changes the zero count without changing ones, leaving the language and contradicting the lemma.
\end{examplebox}

\begin{warningbox}
The common mistake is to memorize the visible procedure while dropping its precondition. I write the assumption beside the method and test one boundary case before trusting the result.
\end{warningbox}

\begin{chapterpractice}
\textbf{Practice.} Use pumping to show \{0\textasciicircum{}n1\textasciicircum{}n\} is not regular.

\textbf{Solution.} Choose 0\textasciicircum{}p1\textasciicircum{}p. Any first p-symbol pump segment contains only zeros. Pumping changes the zero count without changing ones, leaving the language and contradicting the lemma.

\medskip
\textbf{Practice 2.} Give a short oral explanation of nonregularity and pumping that includes its model, one assumption, one failure mode, and one comparison with a neighboring method.

\textbf{Solution.} A strong answer begins with the model in the blue box, names the assumption that licenses the method, uses the common miss above as the failure mode, and chooses the comparison according to the decision test in the deep notes. The goal is not one memorized sentence; it is a four-part explanation I can reproduce on a new example.

\medskip
\textbf{Mastery practice A.} Reconstruct nonregularity and pumping from a blank page. Include the central definition, the governing rule, one required assumption, and one boundary case.

\textbf{Solution.} Start from the blue idea box, but rewrite it in my own words. Identify the objects and state, name the rule before using it, copy the relevant assumption from the details audit, and choose a boundary where that assumption becomes equality or fails. A complete solution explains why each part belongs; a list of vocabulary is not enough.

\medskip
\textbf{Mastery practice B.} A classmate gets a polished-looking answer to a nonregularity and pumping problem but never states a model or checks the result. Write the shortest useful review of that solution.

\textbf{Solution.} I would ask four concrete questions: What exactly are the inputs and desired output? Which rule licenses the main step? Which assumption could invalidate it? Which independent check supports the conclusion? If the answer cannot survive those four questions, I treat the numerical or verbal result as unverified.

\end{chapterpractice}

\section{Context-free grammars and parse structure}

\begin{idea}
CFGs generate strings through variables and productions. Leftmost derivations and parse trees expose hierarchical structure; ambiguity means one string has multiple parse trees. Normal forms support proofs and parsing algorithms.
\end{idea}
% MASTERCLASS EXPANSION
\subsection{Rebuild the chapter from first principles}
The claim I need to own is this: CFGs generate strings through variables and productions. Leftmost derivations and parse trees expose hierarchical structure; ambiguity means one string has multiple parse trees. Normal forms support proofs and parsing algorithms. I do not count that as learned just because the sentence looks familiar. I should be able to name the objects, state what changes and what stays fixed, recover the rule from the definitions, and explain why the result is allowed.

\begin{move}
\textbf{My working sequence}
\begin{enumerate}
  \item \textbf{Translate.} Rewrite the prompt in the language of context-free grammars and parse structure. List the known quantities, the unknown, the units or types, and any hidden constraint.
  \item \textbf{Choose.} State the theorem, model, algorithm, accounting rule, or physical law before substituting values. This is where I make the assumption visible.
  \item \textbf{Execute.} Work one justified step at a time and keep intermediate state readable enough that I can audit it later.
  \item \textbf{Verify.} Check a boundary case, sign, unit, invariant, order of magnitude, or alternative derivation. Then translate the result back into an ordinary sentence.
\end{enumerate}
\end{move}

\subsection{Details I would refuse to skip}
\begin{itemize}
  \item \textbf{Definitions:} I should be able to define every technical noun in the chapter without using that same noun in the definition.
  \item \textbf{Assumptions:} I write the condition that makes the method legal beside the method itself. A correct procedure under the wrong assumptions is still a wrong answer.
  \item \textbf{Representation:} I move freely among words, equations or code, a diagram, and a small numerical example. If one representation disagrees with another, that disagreement is useful evidence.
  \item \textbf{Failure modes:} I keep the nearest counterexample in mind: the boundary where the rule changes, the invariant breaks, or the model stops matching reality.
  \item \textbf{Communication:} My final answer names what the result means and what it does not establish. I do not let notation do the explanatory work for me.
\end{itemize}

\begin{sanitybox}
\textbf{Closed-note check.} Can I teach context-free grammars and parse structure on a blank page, derive or reconstruct its main rule, work a fresh example, and diagnose a deliberately broken solution? If I can only recognize the finished work, I am not done.
\end{sanitybox}

\subsection{How this chapter connects}
I read this chapter as the bridge from nonregularity and pumping to pushdown automata and cfl properties. The earlier material supplies the language and constraints; this chapter adds a new reasoning move; the later material asks me to use that move without being told its name. That connection matters because exams and real projects mix chapters on purpose.


\subsection{What I need to be able to do}
For this chapter, I should be able to define the objects and state involved, state the governing invariant or contract, trace a small example without hand-waving, and explain which assumption makes the method valid. I should also be able to compare this model with the nearest alternative and say what failure would make me switch approaches.

\subsection{Deep notes}
\begin{itemize}
\item \textbf{Model.} CFGs generate strings through variables and productions.
\item \textbf{Mechanism.} Leftmost derivations and parse trees expose hierarchical structure; ambiguity means one string has multiple parse trees.
\item \textbf{Boundary.} Normal forms support proofs and parsing algorithms.
\item \textbf{Decision test.} I should be able to say when context-free grammars and parse structure is the right model, when its assumptions fail, and what evidence would change my choice.
\end{itemize}

\begin{studenttake}
I ask what substring each variable is responsible for generating.
\end{studenttake}

\begin{plainbox}
CFGs generate strings through variables and productions.
\end{plainbox}

\begin{examplebox}
A useful way to work this chapter is to make the smallest concrete instance, write the state or contract explicitly, and then scale the reasoning only after that instance behaves correctly. The worked question below makes that reasoning concrete: Give a grammar for balanced parentheses. The conclusion is S -\textgreater{} SS | (S) | epsilon generates concatenation and nesting. Prove soundness by induction on derivations and completeness by splitting any nonempty balanced string at its matching structure.
\end{examplebox}

\begin{warningbox}
The common mistake is to memorize the visible procedure while dropping its precondition. I write the assumption beside the method and test one boundary case before trusting the result.
\end{warningbox}

\begin{chapterpractice}
\textbf{Practice.} Give a grammar for balanced parentheses.

\textbf{Solution.} S -\textgreater{} SS | (S) | epsilon generates concatenation and nesting. Prove soundness by induction on derivations and completeness by splitting any nonempty balanced string at its matching structure.

\medskip
\textbf{Practice 2.} Give a short oral explanation of context-free grammars and parse structure that includes its model, one assumption, one failure mode, and one comparison with a neighboring method.

\textbf{Solution.} A strong answer begins with the model in the blue box, names the assumption that licenses the method, uses the common miss above as the failure mode, and chooses the comparison according to the decision test in the deep notes. The goal is not one memorized sentence; it is a four-part explanation I can reproduce on a new example.

\medskip
\textbf{Mastery practice A.} Reconstruct context-free grammars and parse structure from a blank page. Include the central definition, the governing rule, one required assumption, and one boundary case.

\textbf{Solution.} Start from the blue idea box, but rewrite it in my own words. Identify the objects and state, name the rule before using it, copy the relevant assumption from the details audit, and choose a boundary where that assumption becomes equality or fails. A complete solution explains why each part belongs; a list of vocabulary is not enough.

\medskip
\textbf{Mastery practice B.} A classmate gets a polished-looking answer to a context-free grammars and parse structure problem but never states a model or checks the result. Write the shortest useful review of that solution.

\textbf{Solution.} I would ask four concrete questions: What exactly are the inputs and desired output? Which rule licenses the main step? Which assumption could invalidate it? Which independent check supports the conclusion? If the answer cannot survive those four questions, I treat the numerical or verbal result as unverified.

\end{chapterpractice}

\section{Pushdown automata and CFL properties}

\begin{idea}
A PDA adds an unbounded stack to finite control and recognizes context-free languages. Nondeterminism matters for PDAs. CFLs have their own pumping lemma and are closed under some, but not all, Boolean operations.
\end{idea}
% MASTERCLASS EXPANSION
\subsection{Rebuild the chapter from first principles}
The claim I need to own is this: A PDA adds an unbounded stack to finite control and recognizes context-free languages. Nondeterminism matters for PDAs. CFLs have their own pumping lemma and are closed under some, but not all, Boolean operations. I do not count that as learned just because the sentence looks familiar. I should be able to name the objects, state what changes and what stays fixed, recover the rule from the definitions, and explain why the result is allowed.

\begin{move}
\textbf{My working sequence}
\begin{enumerate}
  \item \textbf{Translate.} Rewrite the prompt in the language of pushdown automata and cfl properties. List the known quantities, the unknown, the units or types, and any hidden constraint.
  \item \textbf{Choose.} State the theorem, model, algorithm, accounting rule, or physical law before substituting values. This is where I make the assumption visible.
  \item \textbf{Execute.} Work one justified step at a time and keep intermediate state readable enough that I can audit it later.
  \item \textbf{Verify.} Check a boundary case, sign, unit, invariant, order of magnitude, or alternative derivation. Then translate the result back into an ordinary sentence.
\end{enumerate}
\end{move}

\subsection{Details I would refuse to skip}
\begin{itemize}
  \item \textbf{Definitions:} I should be able to define every technical noun in the chapter without using that same noun in the definition.
  \item \textbf{Assumptions:} I write the condition that makes the method legal beside the method itself. A correct procedure under the wrong assumptions is still a wrong answer.
  \item \textbf{Representation:} I move freely among words, equations or code, a diagram, and a small numerical example. If one representation disagrees with another, that disagreement is useful evidence.
  \item \textbf{Failure modes:} I keep the nearest counterexample in mind: the boundary where the rule changes, the invariant breaks, or the model stops matching reality.
  \item \textbf{Communication:} My final answer names what the result means and what it does not establish. I do not let notation do the explanatory work for me.
\end{itemize}

\begin{sanitybox}
\textbf{Closed-note check.} Can I teach pushdown automata and cfl properties on a blank page, derive or reconstruct its main rule, work a fresh example, and diagnose a deliberately broken solution? If I can only recognize the finished work, I am not done.
\end{sanitybox}

\subsection{How this chapter connects}
I read this chapter as the bridge from context-free grammars and parse structure to turing machines and recognizability. The earlier material supplies the language and constraints; this chapter adds a new reasoning move; the later material asks me to use that move without being told its name. That connection matters because exams and real projects mix chapters on purpose.


\subsection{What I need to be able to do}
For this chapter, I should be able to define the objects and state involved, state the governing invariant or contract, trace a small example without hand-waving, and explain which assumption makes the method valid. I should also be able to compare this model with the nearest alternative and say what failure would make me switch approaches.

\subsection{Deep notes}
\begin{itemize}
\item \textbf{Model.} A PDA adds an unbounded stack to finite control and recognizes context-free languages.
\item \textbf{Mechanism.} Nondeterminism matters for PDAs.
\item \textbf{Boundary.} CFLs have their own pumping lemma and are closed under some, but not all, Boolean operations.
\item \textbf{Decision test.} I should be able to say when pushdown automata and cfl properties is the right model, when its assumptions fail, and what evidence would change my choice.
\end{itemize}

\begin{studenttake}
My shorthand for this chapter is: my shorthand for this chapter is: the stack is memory with one accessible end, which is exactly enough for nested structure.
\end{studenttake}

\begin{plainbox}
A PDA adds an unbounded stack to finite control and recognizes context-free languages.
\end{plainbox}

\begin{examplebox}
A useful way to work this chapter is to make the smallest concrete instance, write the state or contract explicitly, and then scale the reasoning only after that instance behaves correctly. The worked question below makes that reasoning concrete: Describe a PDA for 0\textasciicircum{}n1\textasciicircum{}n. The conclusion is Push one marker per zero, nondeterministically or on first one switch phases, pop one per one, and accept only when input and marker stack finish together.
\end{examplebox}

\begin{warningbox}
The common mistake is to memorize the visible procedure while dropping its precondition. I write the assumption beside the method and test one boundary case before trusting the result.
\end{warningbox}

\begin{chapterpractice}
\textbf{Practice.} Describe a PDA for 0\textasciicircum{}n1\textasciicircum{}n.

\textbf{Solution.} Push one marker per zero, nondeterministically or on first one switch phases, pop one per one, and accept only when input and marker stack finish together.

\medskip
\textbf{Practice 2.} Give a short oral explanation of pushdown automata and cfl properties that includes its model, one assumption, one failure mode, and one comparison with a neighboring method.

\textbf{Solution.} A strong answer begins with the model in the blue box, names the assumption that licenses the method, uses the common miss above as the failure mode, and chooses the comparison according to the decision test in the deep notes. The goal is not one memorized sentence; it is a four-part explanation I can reproduce on a new example.

\medskip
\textbf{Mastery practice A.} Reconstruct pushdown automata and cfl properties from a blank page. Include the central definition, the governing rule, one required assumption, and one boundary case.

\textbf{Solution.} Start from the blue idea box, but rewrite it in my own words. Identify the objects and state, name the rule before using it, copy the relevant assumption from the details audit, and choose a boundary where that assumption becomes equality or fails. A complete solution explains why each part belongs; a list of vocabulary is not enough.

\medskip
\textbf{Mastery practice B.} A classmate gets a polished-looking answer to a pushdown automata and cfl properties problem but never states a model or checks the result. Write the shortest useful review of that solution.

\textbf{Solution.} I would ask four concrete questions: What exactly are the inputs and desired output? Which rule licenses the main step? Which assumption could invalidate it? Which independent check supports the conclusion? If the answer cannot survive those four questions, I treat the numerical or verbal result as unverified.

\end{chapterpractice}

\section{Turing machines and recognizability}

\begin{idea}
A Turing machine has finite control and an unbounded read-write tape. Deciders halt on every input; recognizers may loop on nonmembers. Multitape, nondeterministic, and high-level variants preserve computability.
\end{idea}
% MASTERCLASS EXPANSION
\subsection{Rebuild the chapter from first principles}
The claim I need to own is this: A Turing machine has finite control and an unbounded read-write tape. Deciders halt on every input; recognizers may loop on nonmembers. Multitape, nondeterministic, and high-level variants preserve computability. I do not count that as learned just because the sentence looks familiar. I should be able to name the objects, state what changes and what stays fixed, recover the rule from the definitions, and explain why the result is allowed.

\begin{move}
\textbf{My working sequence}
\begin{enumerate}
  \item \textbf{Translate.} Rewrite the prompt in the language of turing machines and recognizability. List the known quantities, the unknown, the units or types, and any hidden constraint.
  \item \textbf{Choose.} State the theorem, model, algorithm, accounting rule, or physical law before substituting values. This is where I make the assumption visible.
  \item \textbf{Execute.} Work one justified step at a time and keep intermediate state readable enough that I can audit it later.
  \item \textbf{Verify.} Check a boundary case, sign, unit, invariant, order of magnitude, or alternative derivation. Then translate the result back into an ordinary sentence.
\end{enumerate}
\end{move}

\subsection{Details I would refuse to skip}
\begin{itemize}
  \item \textbf{Definitions:} I should be able to define every technical noun in the chapter without using that same noun in the definition.
  \item \textbf{Assumptions:} I write the condition that makes the method legal beside the method itself. A correct procedure under the wrong assumptions is still a wrong answer.
  \item \textbf{Representation:} I move freely among words, equations or code, a diagram, and a small numerical example. If one representation disagrees with another, that disagreement is useful evidence.
  \item \textbf{Failure modes:} I keep the nearest counterexample in mind: the boundary where the rule changes, the invariant breaks, or the model stops matching reality.
  \item \textbf{Communication:} My final answer names what the result means and what it does not establish. I do not let notation do the explanatory work for me.
\end{itemize}

\begin{sanitybox}
\textbf{Closed-note check.} Can I teach turing machines and recognizability on a blank page, derive or reconstruct its main rule, work a fresh example, and diagnose a deliberately broken solution? If I can only recognize the finished work, I am not done.
\end{sanitybox}

\subsection{How this chapter connects}
I read this chapter as the bridge from pushdown automata and cfl properties to reductions and undecidability. The earlier material supplies the language and constraints; this chapter adds a new reasoning move; the later material asks me to use that move without being told its name. That connection matters because exams and real projects mix chapters on purpose.


\subsection{What I need to be able to do}
For this chapter, I should be able to define the objects and state involved, state the governing invariant or contract, trace a small example without hand-waving, and explain which assumption makes the method valid. I should also be able to compare this model with the nearest alternative and say what failure would make me switch approaches.

\subsection{Deep notes}
\begin{itemize}
\item \textbf{Model.} A Turing machine has finite control and an unbounded read-write tape.
\item \textbf{Mechanism.} Deciders halt on every input; recognizers may loop on nonmembers.
\item \textbf{Boundary.} Multitape, nondeterministic, and high-level variants preserve computability.
\item \textbf{Decision test.} I should be able to say when turing machines and recognizability is the right model, when its assumptions fail, and what evidence would change my choice.
\end{itemize}

\begin{studenttake}
I distinguish 'does not accept' from 'halts and rejects'; that difference drives recognizability.
\end{studenttake}

\begin{plainbox}
A Turing machine has finite control and an unbounded read-write tape.
\end{plainbox}

\begin{examplebox}
A useful way to work this chapter is to make the smallest concrete instance, write the state or contract explicitly, and then scale the reasoning only after that instance behaves correctly. The worked question below makes that reasoning concrete: Why are deciders closed under complement? The conclusion is Run the decider and swap accept with reject. Because it always halts, the complemented machine also decides and cannot get stuck on a former nonmember.
\end{examplebox}

\begin{warningbox}
The common mistake is to memorize the visible procedure while dropping its precondition. I write the assumption beside the method and test one boundary case before trusting the result.
\end{warningbox}

\begin{chapterpractice}
\textbf{Practice.} Why are deciders closed under complement?

\textbf{Solution.} Run the decider and swap accept with reject. Because it always halts, the complemented machine also decides and cannot get stuck on a former nonmember.

\medskip
\textbf{Practice 2.} Give a short oral explanation of turing machines and recognizability that includes its model, one assumption, one failure mode, and one comparison with a neighboring method.

\textbf{Solution.} A strong answer begins with the model in the blue box, names the assumption that licenses the method, uses the common miss above as the failure mode, and chooses the comparison according to the decision test in the deep notes. The goal is not one memorized sentence; it is a four-part explanation I can reproduce on a new example.

\medskip
\textbf{Mastery practice A.} Reconstruct turing machines and recognizability from a blank page. Include the central definition, the governing rule, one required assumption, and one boundary case.

\textbf{Solution.} Start from the blue idea box, but rewrite it in my own words. Identify the objects and state, name the rule before using it, copy the relevant assumption from the details audit, and choose a boundary where that assumption becomes equality or fails. A complete solution explains why each part belongs; a list of vocabulary is not enough.

\medskip
\textbf{Mastery practice B.} A classmate gets a polished-looking answer to a turing machines and recognizability problem but never states a model or checks the result. Write the shortest useful review of that solution.

\textbf{Solution.} I would ask four concrete questions: What exactly are the inputs and desired output? Which rule licenses the main step? Which assumption could invalidate it? Which independent check supports the conclusion? If the answer cannot survive those four questions, I treat the numerical or verbal result as unverified.

\end{chapterpractice}

\section{Reductions and undecidability}

\begin{idea}
A mapping reduction computes f such that x is in A exactly when f(x) is in B. It transfers impossibility: if A is undecidable and A reduces to B, then B is undecidable. Diagonalization and self-reference power canonical proofs.
\end{idea}
% MASTERCLASS EXPANSION
\subsection{Rebuild the chapter from first principles}
The claim I need to own is this: A mapping reduction computes f such that x is in A exactly when f(x) is in B. It transfers impossibility: if A is undecidable and A reduces to B, then B is undecidable. Diagonalization and self-reference power canonical proofs. I do not count that as learned just because the sentence looks familiar. I should be able to name the objects, state what changes and what stays fixed, recover the rule from the definitions, and explain why the result is allowed.

\begin{move}
\textbf{My working sequence}
\begin{enumerate}
  \item \textbf{Translate.} Rewrite the prompt in the language of reductions and undecidability. List the known quantities, the unknown, the units or types, and any hidden constraint.
  \item \textbf{Choose.} State the theorem, model, algorithm, accounting rule, or physical law before substituting values. This is where I make the assumption visible.
  \item \textbf{Execute.} Work one justified step at a time and keep intermediate state readable enough that I can audit it later.
  \item \textbf{Verify.} Check a boundary case, sign, unit, invariant, order of magnitude, or alternative derivation. Then translate the result back into an ordinary sentence.
\end{enumerate}
\end{move}

\subsection{Details I would refuse to skip}
\begin{itemize}
  \item \textbf{Definitions:} I should be able to define every technical noun in the chapter without using that same noun in the definition.
  \item \textbf{Assumptions:} I write the condition that makes the method legal beside the method itself. A correct procedure under the wrong assumptions is still a wrong answer.
  \item \textbf{Representation:} I move freely among words, equations or code, a diagram, and a small numerical example. If one representation disagrees with another, that disagreement is useful evidence.
  \item \textbf{Failure modes:} I keep the nearest counterexample in mind: the boundary where the rule changes, the invariant breaks, or the model stops matching reality.
  \item \textbf{Communication:} My final answer names what the result means and what it does not establish. I do not let notation do the explanatory work for me.
\end{itemize}

\begin{sanitybox}
\textbf{Closed-note check.} Can I teach reductions and undecidability on a blank page, derive or reconstruct its main rule, work a fresh example, and diagnose a deliberately broken solution? If I can only recognize the finished work, I am not done.
\end{sanitybox}

\subsection{How this chapter connects}
I read this chapter as the bridge from turing machines and recognizability to computability boundaries and classification. The earlier material supplies the language and constraints; this chapter adds a new reasoning move; the later material asks me to use that move without being told its name. That connection matters because exams and real projects mix chapters on purpose.


\subsection{What I need to be able to do}
For this chapter, I should be able to define the objects and state involved, state the governing invariant or contract, trace a small example without hand-waving, and explain which assumption makes the method valid. I should also be able to compare this model with the nearest alternative and say what failure would make me switch approaches.

\subsection{Deep notes}
\begin{itemize}
\item \textbf{Model.} A mapping reduction computes f such that x is in A exactly when f(x) is in B.
\item \textbf{Mechanism.} It transfers impossibility: if A is undecidable and A reduces to B, then B is undecidable.
\item \textbf{Boundary.} Diagonalization and self-reference power canonical proofs.
\item \textbf{Decision test.} I should be able to say when reductions and undecidability is the right model, when its assumptions fail, and what evidence would change my choice.
\end{itemize}

\begin{studenttake}
I read the reduction direction as a hypothetical solver: a B solver would give me an A solver.
\end{studenttake}

\begin{plainbox}
A mapping reduction computes f such that x is in A exactly when f(x) is in B.
\end{plainbox}

\begin{examplebox}
A useful way to work this chapter is to make the smallest concrete instance, write the state or contract explicitly, and then scale the reasoning only after that instance behaves correctly. The worked question below makes that reasoning concrete: Outline the halting-problem contradiction. The conclusion is Assume H decides whether machine M halts on input w. Construct D that loops when H says D halts on itself and halts otherwise. Running D on D contradicts either answer.
\end{examplebox}

\begin{warningbox}
The common mistake is to memorize the visible procedure while dropping its precondition. I write the assumption beside the method and test one boundary case before trusting the result.
\end{warningbox}

\begin{chapterpractice}
\textbf{Practice.} Outline the halting-problem contradiction.

\textbf{Solution.} Assume H decides whether machine M halts on input w. Construct D that loops when H says D halts on itself and halts otherwise. Running D on D contradicts either answer.

\medskip
\textbf{Practice 2.} Give a short oral explanation of reductions and undecidability that includes its model, one assumption, one failure mode, and one comparison with a neighboring method.

\textbf{Solution.} A strong answer begins with the model in the blue box, names the assumption that licenses the method, uses the common miss above as the failure mode, and chooses the comparison according to the decision test in the deep notes. The goal is not one memorized sentence; it is a four-part explanation I can reproduce on a new example.

\medskip
\textbf{Mastery practice A.} Reconstruct reductions and undecidability from a blank page. Include the central definition, the governing rule, one required assumption, and one boundary case.

\textbf{Solution.} Start from the blue idea box, but rewrite it in my own words. Identify the objects and state, name the rule before using it, copy the relevant assumption from the details audit, and choose a boundary where that assumption becomes equality or fails. A complete solution explains why each part belongs; a list of vocabulary is not enough.

\medskip
\textbf{Mastery practice B.} A classmate gets a polished-looking answer to a reductions and undecidability problem but never states a model or checks the result. Write the shortest useful review of that solution.

\textbf{Solution.} I would ask four concrete questions: What exactly are the inputs and desired output? Which rule licenses the main step? Which assumption could invalidate it? Which independent check supports the conclusion? If the answer cannot survive those four questions, I treat the numerical or verbal result as unverified.

\end{chapterpractice}

\section{Computability boundaries and classification}

\begin{idea}
Decidable, recognizable, co-recognizable, and unrecognizable languages form different classes. Rice's theorem makes every nontrivial semantic property of recognized languages undecidable; syntactic properties may remain decidable.
\end{idea}
% MASTERCLASS EXPANSION
\subsection{Rebuild the chapter from first principles}
The claim I need to own is this: Decidable, recognizable, co-recognizable, and unrecognizable languages form different classes. Rice's theorem makes every nontrivial semantic property of recognized languages undecidable; syntactic properties may remain decidable. I do not count that as learned just because the sentence looks familiar. I should be able to name the objects, state what changes and what stays fixed, recover the rule from the definitions, and explain why the result is allowed.

\begin{move}
\textbf{My working sequence}
\begin{enumerate}
  \item \textbf{Translate.} Rewrite the prompt in the language of computability boundaries and classification. List the known quantities, the unknown, the units or types, and any hidden constraint.
  \item \textbf{Choose.} State the theorem, model, algorithm, accounting rule, or physical law before substituting values. This is where I make the assumption visible.
  \item \textbf{Execute.} Work one justified step at a time and keep intermediate state readable enough that I can audit it later.
  \item \textbf{Verify.} Check a boundary case, sign, unit, invariant, order of magnitude, or alternative derivation. Then translate the result back into an ordinary sentence.
\end{enumerate}
\end{move}

\subsection{Details I would refuse to skip}
\begin{itemize}
  \item \textbf{Definitions:} I should be able to define every technical noun in the chapter without using that same noun in the definition.
  \item \textbf{Assumptions:} I write the condition that makes the method legal beside the method itself. A correct procedure under the wrong assumptions is still a wrong answer.
  \item \textbf{Representation:} I move freely among words, equations or code, a diagram, and a small numerical example. If one representation disagrees with another, that disagreement is useful evidence.
  \item \textbf{Failure modes:} I keep the nearest counterexample in mind: the boundary where the rule changes, the invariant breaks, or the model stops matching reality.
  \item \textbf{Communication:} My final answer names what the result means and what it does not establish. I do not let notation do the explanatory work for me.
\end{itemize}

\begin{sanitybox}
\textbf{Closed-note check.} Can I teach computability boundaries and classification on a blank page, derive or reconstruct its main rule, work a fresh example, and diagnose a deliberately broken solution? If I can only recognize the finished work, I am not done.
\end{sanitybox}

\subsection{How this chapter connects}
I read this chapter as the bridge from reductions and undecidability to the cumulative course model. The earlier material supplies the language and constraints; this chapter adds a new reasoning move; the later material asks me to use that move without being told its name. That connection matters because exams and real projects mix chapters on purpose.


\subsection{What I need to be able to do}
For this chapter, I should be able to define the objects and state involved, state the governing invariant or contract, trace a small example without hand-waving, and explain which assumption makes the method valid. I should also be able to compare this model with the nearest alternative and say what failure would make me switch approaches.

\subsection{Deep notes}
\begin{itemize}
\item \textbf{Model.} Decidable, recognizable, co-recognizable, and unrecognizable languages form different classes.
\item \textbf{Mechanism.} Rice's theorem makes every nontrivial semantic property of recognized languages undecidable; syntactic properties may remain decidable.
\item \textbf{Boundary.} The useful test is whether I can apply computability boundaries and classification to a new case and explain the assumption that makes the answer valid.
\item \textbf{Decision test.} I should be able to say when computability boundaries and classification is the right model, when its assumptions fail, and what evidence would change my choice.
\end{itemize}

\begin{studenttake}
I ask whether a property concerns program text or what the program ultimately computes.
\end{studenttake}

\begin{plainbox}
Decidable, recognizable, co-recognizable, and unrecognizable languages form different classes.
\end{plainbox}

\begin{examplebox}
A useful way to work this chapter is to make the smallest concrete instance, write the state or contract explicitly, and then scale the reasoning only after that instance behaves correctly. The worked question below makes that reasoning concrete: Why is 'does this TM recognize an empty language?' undecidable? The conclusion is Emptiness is a nontrivial semantic property of the recognized language, so Rice's theorem applies. It can also be shown by reduction from acceptance.
\end{examplebox}

\begin{warningbox}
The common mistake is to memorize the visible procedure while dropping its precondition. I write the assumption beside the method and test one boundary case before trusting the result.
\end{warningbox}

\begin{chapterpractice}
\textbf{Practice.} Why is 'does this TM recognize an empty language?' undecidable?

\textbf{Solution.} Emptiness is a nontrivial semantic property of the recognized language, so Rice's theorem applies. It can also be shown by reduction from acceptance.

\medskip
\textbf{Practice 2.} Give a short oral explanation of computability boundaries and classification that includes its model, one assumption, one failure mode, and one comparison with a neighboring method.

\textbf{Solution.} A strong answer begins with the model in the blue box, names the assumption that licenses the method, uses the common miss above as the failure mode, and chooses the comparison according to the decision test in the deep notes. The goal is not one memorized sentence; it is a four-part explanation I can reproduce on a new example.

\medskip
\textbf{Mastery practice A.} Reconstruct computability boundaries and classification from a blank page. Include the central definition, the governing rule, one required assumption, and one boundary case.

\textbf{Solution.} Start from the blue idea box, but rewrite it in my own words. Identify the objects and state, name the rule before using it, copy the relevant assumption from the details audit, and choose a boundary where that assumption becomes equality or fails. A complete solution explains why each part belongs; a list of vocabulary is not enough.

\medskip
\textbf{Mastery practice B.} A classmate gets a polished-looking answer to a computability boundaries and classification problem but never states a model or checks the result. Write the shortest useful review of that solution.

\textbf{Solution.} I would ask four concrete questions: What exactly are the inputs and desired output? Which rule licenses the main step? Which assumption could invalidate it? Which independent check supports the conclusion? If the answer cannot survive those four questions, I treat the numerical or verbal result as unverified.

\end{chapterpractice}

\section*{Final study check}
I should be able to close this packet and reconstruct the core models, not merely recognize their names. My final check is to explain one complete problem aloud: what the inputs mean, which invariant or contract controls the work, why the method is legal, what it costs, how it can fail, and what evidence would convince another engineer.

\end{document}
