Theory of Computation and Compiler Design
Theory of computation and compiler design tests formal languages, automata, decidability, and the translation pipeline from source text to optimized code. Questions often connect a grammar property to a parser or a language class to a machine.
Core rules and concepts
- Regular languages are closed under union, intersection, complement, concatenation, and star; they are recognized by DFA/NFA and described by regular expressions.
- Pumping lemma for regular languages is necessary, not sufficient: failure to pump proves non-regularity, but passing does not prove regularity.
- Context-free languages are recognized by pushdown automata and generated by CFGs; deterministic CFLs are a proper subset.
- A Turing machine is the standard model for computability; the halting problem is undecidable, and Rice’s theorem generalizes undecidability of nontrivial semantic properties.
- Compiler phases: lexical analysis, syntax analysis, semantic analysis, intermediate code generation, optimization, and code generation. LL parsers are top-down and need left-recursion removal; LR parsers are bottom-up and handle more grammars.
Worked example
Design a DFA over {0,1} accepting strings with an even number of 0s and an even number of 1s. Track two parities, so four states: EE (start and accept), OE, EO, OO. Reading 0 toggles the 0-parity; reading 1 toggles the 1-parity. From EE, 0 goes to OE and 1 goes to EO; from OE, 0 returns to EE and 1 goes to OO; and so on. The product construction gives exactly four states, and EE is the only accepting state.
Traps that cost marks
Forgetting epsilon-closure in NFA simulation; treating a grammar as LL(1) while it is left-recursive; confusing SLR, LALR, and canonical LR conflict power; and assuming a language is regular because a particular grammar is not. In compilers, semantic analysis catches type errors that parsing cannot.