Computation Theory · Cluster
Formal Languages
Grammars, derivations, and the Chomsky hierarchy.
- 01 Alphabets, Strings, and the Closure Properties That Define a Language Class Why formal languages are studied as sets of strings, how closure under composition operations determines what a class can express, and why descriptions rather than sets carry the theory.
- 02 Derivations, Sentential Forms, and What a Parse Tree Actually Records How a grammar rewrites strings step by step, why leftmost derivations and parse trees are two views of one object, and where the correspondence breaks when a grammar is ambiguous.
- 03 Right-Linear Grammars and the Limits of One-Way Derivation Why a grammar whose rules can only consume input left to right generates exactly the regular languages, and what happens to the language when left-linear rules are mixed in.
- 04 The Chomsky Hierarchy as a Ladder of Memory Each level of the hierarchy corresponds to a kind of store a machine may use: none, a stack, a bounded tape, an unbounded tape. What the grammar restrictions encode about that store.
- 05 Chomsky Normal Form and the CYK Table How rewriting a grammar so every rule is A to BC or A to a makes cubic-time recognition possible, and why the table is indexed by substrings rather than by derivation prefixes.
- 06 Closure Gaps in Context-Free Languages Context-free languages are closed under union and star but not under intersection or complement, and the two failures are the same failure seen from two sides.
- 07 Pumping Lemmas, Marked Positions, and the Limits of Counting Arguments Why the pumping lemma is a necessary condition for regularity and never a sufficient one, and how marking positions in the input strengthens the argument for both regular and context-free languages.
- 08 Ambiguity, Equivalence, and Other Undecidable Grammar Questions Membership in a context-free language is decidable, but asking whether two grammars denote the same language is not, and neither is asking whether one is ambiguous.
- 09 Context-Sensitive Rules and Why Non-Contracting Rewriting Is Decidable A rule may rewrite a symbol in the context of its neighbours as long as it never shortens the string, and that single restriction turns an unbounded search into a finite one.
- 10 Counting Derivations: Algebraic Generating Functions and the Growth of Parse Trees A grammar can be compiled into a polynomial system whose power-series coefficients count parse trees, and the resulting algebraic function explains why ambiguity grows exponentially.