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.
Understanding Theory of Computation Automata and Complexity
Finite automata are useful because they model systems with limited memory. A turnstile controller, a simple network protocol, or a search tool that checks a text pattern can keep track of a fixed set of situations. Each new symbol changes the current situation.
A finite automaton cannot store an unbounded count. This is why it can recognize strings with an even number of zeros, yet it cannot recognize strings made of some number of zeros followed by exactly the same number of ones.
When studying a machine, identify what each state means in plain language. A good state meaning makes transition diagrams easier to build and check.
Nondeterminism does not mean a machine guesses magically in real hardware. It is a mathematical way to describe several possible next moves. An NFA accepts if at least one possible path reaches an accepting state.
Converting such a machine into a DFA tracks a set of possible NFA states at once. This explains why the converted DFA may need many more states. Regular expressions, automata, and regular languages are interchangeable tools, but each is convenient for different work.
Expressions are often best for describing patterns. Automata are often best for tracing inputs or proving closure properties. Closure proofs matter because they show that operations such as union, complement, and intersection do not take a language outside the regular family.
Context-free languages handle nested structure that finite automata cannot manage. A parser for programming code must match opening and closing parentheses, braces, or blocks. This requires memory that can grow with the input.
A pushdown automaton uses a stack for this purpose. It can place a marker on the stack for each opening symbol, then remove one for each matching closing symbol. Grammars describe the same kind of structure through rules that replace variables with pieces of a sentence.
Pay close attention to ambiguity. An ambiguous grammar gives more than one parse tree for some string. In programming languages, ambiguity can make an expression such as a subtraction chain unclear unless precedence and grouping rules settle the meaning.
Turing machines are used to reason about general algorithms because their tape provides unbounded working space. Their importance is not that people build computers from tapes, but that the model captures what ordinary programs can compute when given enough time and memory. The central distinction is between recognizing and deciding.
A recognizer may run forever on an input outside its language. A decider must eventually stop on every input. Reductions transfer difficulty between problems.
To show that a new problem is hard, transform every instance of a known hard problem into an instance of the new one, while preserving yes and no answers. Complexity then asks how resources grow as input size grows. Polynomial time is treated as practical in theory, while exponential growth becomes unmanageable quickly.
NP concerns solutions that can be checked efficiently. NP completeness identifies problems that would all become efficiently solvable if any one NP complete problem had a polynomial time algorithm.