Practice Theory of Computation interview questions covering finite automata, regular expressions, context-free grammars, pushdown automata, Turing machines, and computational complexity.
Theory of Computation interviews appear in PhD research applications, compilers and programming language engineering roles, formal verification positions, and thorough CS screenings at research-oriented companies. They test mathematical precision and the ability to reason about what is and is not computationally possible.
Begin with the automata hierarchy: deterministic finite automata (DFA), non-deterministic finite automata (NFA and the subset construction for NFA-to-DFA conversion), and pushdown automata (PDA). Know the equivalences: DFAs and NFAs recognise exactly the regular languages; PDAs recognise exactly the context-free languages. Context-free grammars (CFGs), the pumping lemma for CFLs, Chomsky Normal Form conversion, and the CYK parsing algorithm form the second core area. Understand why the intersection of two CFLs is not necessarily context-free, which trips up candidates who over-extend closure properties from regular languages.
Turing machines, decidability, and computational complexity complete the picture: the halting problem undecidability proof (diagonalisation), reductions (many-one, Turing), the P vs NP question, NP-hardness and NP-completeness (Cook-Levin theorem, reduction from known NP-complete problems), and the complexity classes PSPACE and EXP. Use the Top 50 TOC Interview Questions to practise constructing rigorous proofs and precise complexity arguments.
