Theory of computation studies what computers can recognize, decide, and compute in principle. This cheat sheet connects automata models, formal languages, Turing machines, and complexity classes in one compact reference. Students need these ideas to prove language properties, compare models of computation, and understand the limits of algorithms.
It is especially useful when preparing for exams on regular languages, context-free languages, decidability, reductions, and P versus NP.
Key Facts
- A DFA is a 5-tuple (Q, Sigma, delta, q0, F), where delta: Q x Sigma -> Q gives exactly one next state for each state and input symbol.
- An NFA is equivalent in power to a DFA, and any NFA with n states can be converted to a DFA with at most 2^n states.
- A language is regular if and only if it is recognized by some DFA, NFA, or regular expression.
- The pumping lemma for regular languages says that if L is regular, then there is a pumping length p such that any string s in L with |s| >= p can be written as s = xyz, with |xy| <= p, |y| > 0, and xy^i z in L for all i >= 0.
- A context-free grammar is a 4-tuple (V, Sigma, R, S), where productions in R have the form A -> alpha with one variable A on the left.
- A language is decidable if there is a Turing machine that halts on every input and accepts exactly the strings in the language.
- A language A is mapping reducible to B, written A <=m B, if there is a computable function f such that x is in A if and only if f(x) is in B.
- P is the class of decision problems solvable in polynomial time, NP is the class verifiable in polynomial time, and NP-complete problems are in NP and are at least as hard as every problem in NP.
Vocabulary
- Alphabet
- A finite nonempty set of symbols used to form strings in a formal language.
- Deterministic Finite Automaton
- A finite-state machine with exactly one transition for each state and input symbol.
- Context-Free Language
- A language generated by a context-free grammar or recognized by a pushdown automaton.
- Turing Machine
- A mathematical model of computation with an infinite tape, a finite control, and rules for reading, writing, and moving.
- Decidable Language
- A language for which some Turing machine always halts and correctly accepts or rejects every input.
- NP-Complete
- A decision problem that is in NP and to which every problem in NP can be polynomial-time reduced.
Common Mistakes to Avoid
- Confusing recognition with decidability is wrong because a recognizer may loop forever on strings not in the language, while a decider must halt on every input.
- Assuming every nonregular language is context-free is wrong because some languages, such as {a^n b^n c^n | n >= 0}, are not context-free.
- Using the pumping lemma as a proof that a language is regular is wrong because the lemma gives a necessary condition for regular languages, not a sufficient one.
- Claiming an NFA is more powerful than a DFA is wrong because NFAs can be converted into equivalent DFAs that recognize the same languages.
- Proving NP-completeness without showing membership in NP is incomplete because a problem must be both in NP and NP-hard to be NP-complete.
Practice Questions
- 1 A DFA has 5 states and alphabet {0, 1}. How many transition entries must its transition table contain?
- 2 An NFA has 4 states. What is the maximum number of states in the equivalent DFA produced by the subset construction?
- 3 Give a context-free grammar for the language {a^n b^n | n >= 0}.
- 4 Explain why proving a problem is NP-hard does not by itself prove that the problem is NP-complete.