Theory of Computation · ODD 2026 · Foundations

Formal Languages

How the foundational building blocks assemble into the Chomsky hierarchy — for orientation and review, not first-time reading. Pair this with the lecture notes for the “why,” and the flashcards for recall.

Formal Languages Building Blocks Closure & Algebra Specifying L Chomsky Hierarchy Alphabet Σ String w, |w| Language L⊆Σ* Decision problem Concatenation Kleene star L* Positive closure L+ Closure property Recognizer Generator Regular expression Grammar (V,Σ,P,S) Type 3 • Regular Type 2 • Context-free Type 1 • Context-sensitive Type 0 • Unrestricted
How the foundational building blocks assemble into the Chomsky hierarchy: alphabets and strings become languages, languages get specified two dual ways (a machine that reads, or a device that writes), and grammars sort into four nested classes purely by the shape of their own production rules.
Building Blocks Closure & Algebra Specifying L Chomsky Hierarchy
AI-generated study aid. This mind map was generated with AI assistance and has been reviewed, but it may still contain small errors. If you spot one, please report it so it can be corrected.