Written coursework from a computability and formal-languages class (CS 252): the theory of computation, worked out by hand across a semester of homework and problem sessions.
This is a theory course, so the artifacts are written proofs and constructions rather than code. The work moves up the hierarchy of computational models, from finite automata through Turing machines, and then into what those machines can and cannot decide. Each PDF is a homework set or a problem-session (TA) walkthrough building formal arguments about languages and machines.
- Finite automata (DFA and NFA) and the regular languages they recognize
- Regular expressions and their equivalence to finite automata
- The pumping lemma and proving a language is not regular
- Context-free grammars and pushdown automata
- Turing machines as the model of general computation
- Decidability and undecidability, reductions between problems
- The relationship between language classes in the Chomsky hierarchy
Scanned and typed problem sets and TA-session solutions:
CS 252 HW #2–#9— homework setsCS 252 TA #2–#8— TA problem-session walkthroughsCS 312 HW 6— one algorithms homework kept alongside
- Pen-and-paper formal proofs, automata diagrams, and constructions (PDF)
There is no code to run here. The value is the reasoning: automata constructions, grammar derivations, and decidability arguments.