Top 50 Theory of Computation Interview Questions (2026)

Theory of computation studies what problems machines can solve and how efficiently, using formal models instead of real hardware so the answers hold for every computer. It has three parts: automata theory (models of computation), computability theory (what's solvable at all), and complexity theory (what's solvable efficiently).

It matters because it tells you the limits before you waste effort. It explains why regex can't match balanced brackets, why no tool can perfectly detect infinite loops, and why some problems are NP-complete so you should reach for approximation rather than an exact solver that'll never finish on large input.

An alphabet, written sigma, is a finite set of symbols, like {0, 1} or {a, b}. A string is a finite sequence of symbols from that alphabet, including the empty string epsilon. A language is a set of strings over the alphabet, so it's a subset of sigma-star, the set of all possible strings.

This vocabulary is the foundation everything else uses. When someone says a finite automaton recognizes a language, they mean it accepts exactly the strings in that set and rejects everything else. Getting these three terms exactly right signals you can speak the field's language precisely.

A DFA is the simplest machine model: a finite set of states, a start state, a set of accepting states, and a transition function that reads one input symbol at a time and moves to exactly one next state. It has no memory beyond which state it's currently in.

You feed it a string, it runs through the transitions, and if it ends in an accepting The string is accepted, otherwise rejected. Deterministic means every state has exactly one transition per input symbol, so the run is fully predictable. DFAs recognize exactly the regular languages.

In a DFA, each state has exactly one transition for each input symbol, so there's a single path through the machine. In an NFA (nondeterministic finite automaton), a state can have zero, one, or many transitions on a symbol, and it may take epsilon (empty) transitions that consume no input. An NFA accepts if any path leads to an accepting state.

The surprising result is they're equal in strength: both recognize exactly the regular languages. The subset construction turns any NFA into an equivalent DFA. NFAs are often smaller and easier to design; DFAs are easier to run because there's no guessing.

You use the subset construction. Each DFA state represents a set of NFA states the machine could be in at once. Start from the epsilon-closure of the NFA's start state, and for each input symbol compute the set of NFA states reachable, taking epsilon-closures as you go. Every distinct set you reach becomes one DFA state.

A DFA state is accepting if its set contains any NFA accepting state. The catch is the state blow-up: an NFA with n states can produce a DFA with up to 2^n states, because there are that many subsets. In practice most subsets aren't reachable, so it's usually far smaller.

A regular expression is a compact notation for a regular language, built from symbols, union (the pipe), concatenation, and the Kleene star (zero or more). It describes exactly the same class of languages that finite automata recognize.

Kleene's theorem ties them together: a language is regular if and only if some regular expression describes it, if and only if some finite automaton recognizes it. That's why regex engines compile a pattern into an automaton to run it. The theory regex and the messy regex in programming languages differ, because those add non-regular features like backreferences.

The Kleene star applied to a set means zero or more concatenations of strings from that set. So a-star is the set { epsilon, a, aa, aaa, ... }, and it always includes the empty string epsilon because zero copies is allowed. Applied to an alphabet, sigma-star is the set of all possible strings over that alphabet.

It's the operation that gives regular expressions their ability to describe unbounded repetition with a finite pattern. Forgetting that the star includes the empty string is a common slip that breaks proofs and constructions.

Yes, regular languages are closed under all three, plus concatenation and Kleene star. If you take two regular languages and union, intersect, or complement them, the result is still regular. That's a defining property of the class.

The constructions are concrete. Complement flips accepting and non-accepting states of a DFA. Intersection uses the product construction, a DFA whose states are pairs tracking both machines at once. Union has a similar product construction or an NFA that branches to either machine. Knowing a closure property comes with a construction is the mature answer.

A context-free grammar is a set of production rules that generate strings. It has variables (nonterminals), terminals (the actual alphabet symbols), a start variable, and rules that rewrite a single variable into a string of variables and terminals. You derive a string by repeatedly applying rules until only terminals remain.

Context-free means the left side of every rule is a single variable, so a variable can be replaced regardless of its surroundings. These grammars generate the context-free languages, which include most programming language syntax, which is why parsers are built on them.

A pushdown automaton (PDA) is a finite automaton plus one stack. On each move it reads an input symbol and the top of the stack, then changes state and pushes or pops the stack. That stack is unbounded memory with last-in-first-out access.

The stack lets it count and match nested structure, which a DFA can't. A PDA recognizes a^n b^n by pushing on each a and popping on each b, and it handles balanced parentheses the same way. PDAs recognize exactly the context-free languages, one strict step above regular.

A Turing machine is an abstract model of general computation: a finite control (states) plus an unbounded tape it can read from and write to, with a head that moves left or right one cell per step. Each step reads the current cell, writes a symbol, moves the head, and changes state based on a transition function.

That read-write tape is the key difference from weaker models: it gives unbounded, random-ish memory, so a Turing machine can compute anything an ordinary computer can. It's the model behind the Church-Turing thesis and the reference point for what's computable at all.

A language is decidable (or recursive) if some Turing machine halts on every input and correctly says yes or no. It's recognizable (or recursively enumerable) if some Turing machine accepts every string in the language but may loop forever on strings that aren't in it.

So decidable is the stronger property: the machine always terminates with an answer. Every decidable language is recognizable, but not the reverse. The halting problem is recognizable but not decidable, which is the classic example of the gap.

The Chomsky hierarchy ranks four classes of formal languages by generative power, each strictly containing the ones below. Type 3 is regular (finite automata), type 2 is context-free (pushdown automata), type 1 is context-sensitive (linear bounded automata), and type 0 is recursively enumerable (Turing machines).

Each level corresponds to a machine model and a grammar form, and the containment is strict: every regular language is context-free, but a^n b^n is context-free and not regular. The hierarchy is the map that tells you which machine is the weakest one that can handle a given problem.

A nondeterministic machine can have several possible moves from a configuration and, informally, explores all of them at once. It accepts a string if any sequence of choices leads to an accepting state. Think of it as guessing the right path and always guessing correctly if one exists.

For finite automata, nondeterminism adds no power: NFAs recognize the same regular languages as DFAs. For Turing machines it adds no computability power either, but the time cost of simulating it deterministically is the whole tension behind P versus NP.

A grammar generates a language: you start from the start symbol and apply rules to produce strings, so a grammar defines a language by building its members. A machine recognizes a language: you hand it a string and it decides whether that string is in the language.

They're two views of the same set. Kleene's theorem and the grammar-automaton correspondences say that for each language class, the generating grammars and the recognizing machines describe exactly the same languages. Regular expressions and grammars generate; automata recognize.

The empty string, epsilon, is a string of length zero. The empty language, often written with the empty-set symbol, is a language with no strings in it at all. They're completely different: a language containing only the empty string has one member, while the empty language has zero members.

This matters in constructions and proofs. A DFA whose start state is accepting accepts epsilon; a DFA with no accepting states recognizes the empty language. Confusing the two is a common beginner error that breaks otherwise correct answers.

Regular languages are ones a finite automaton can recognize with only its state as memory. Examples: all strings that end in ab, all strings with an even number of zeros, all strings containing the substring 101, and any finite set of strings. Anything a plain regular expression describes is regular.

Not regular are languages that need unbounded counting or matching: a^n b^n (equal counts), balanced parentheses, palindromes, and strings with equal numbers of a's and b's. The tell is whether recognizing membership needs to remember an unbounded quantity, which a finite machine can't.

It starts in the start state and reads the string one symbol at a time, following the transition for the current state and symbol to move to the next state. After consuming the whole string, it looks at the state it ended in. If that state is an accepting state, the string is accepted, otherwise it's rejected.

For a DFA the path is unique, so acceptance is straightforward. For an NFA there can be many paths, and the string is accepted if any path ends in an accepting state. Either way, acceptance is about the final state after reading the entire input, not about states passed through along the way.

The pumping lemma says every regular language has a pumping length p such that any string s in the language with length at least p can be split into three parts x, y, z where y isn't empty, xy has length at most p, and pumping y (repeating it any number of times) keeps the string in the language. It's a property every regular language must have.

You use it to prove a language is not regular, by contradiction. Assume it's regular, take the pumping length p, pick a specific string that's in the language, and show that no valid split can be pumped without leaving the language. Finding one bad string is enough to break the assumption.

Assume it's regular, so the pumping lemma gives a length p. Choose the string s = a^p b^p, which is in the language and has length at least p. By the lemma, split s into x, y, z with y non-empty and xy of length at most p. Since the first p symbols are all a's, y consists only of a's.

Now pump: xyyz has more a's than b's, so it's not of the form a^n b^n and isn't in the language. That contradicts the lemma's guarantee that all pumped strings stay in the language. So the assumption fails and the language isn't regular. It is context-free, recognized by a PDA that pushes on a and pops on b.

The Myhill-Nerode theorem says a language is regular if and only if its set of distinguishable string-prefixes (its equivalence classes under a natural relation) is finite. Two strings are equivalent if no suffix distinguishes them: appending the same thing always lands both inside or both outside the language.

It gives two things the pumping lemma can't. It's an exact test: finitely many classes means regular, infinitely many means not regular, no guessing a clever string. And the number of classes equals the number of states in the minimal DFA, so it also tells you the smallest DFA for the language.

You merge states that are indistinguishable, meaning no input string leads one to accept and the other to reject. The standard method partitions states into accepting and non-accepting, then repeatedly refines: two states stay together only if, for every input symbol, they transition into the same current group. When no group splits further, each group becomes one state of the minimal DFA.

First remove unreachable states, since they can't affect any run. The result is unique up to renaming: every regular language has exactly one minimal DFA, and its state count matches the Myhill-Nerode class count. That uniqueness is why minimization is well defined.

A grammar is ambiguous if some string has more than one distinct parse tree (or equivalently more than one leftmost derivation). The classic example is an expression grammar where a + b * c can parse as (a + b) * c or a + (b * c), because the grammar doesn't encode precedence.

Ambiguity is a property of the grammar, not always the language. Many ambiguous grammars can be rewritten unambiguously, for instance by adding precedence levels. But some context-free languages are inherently ambiguous: no unambiguous grammar exists for them. Parsers need unambiguous grammars, which is why expression grammars are carefully layered.

The context-free pumping lemma pumps two substrings at once, not one. It says any long enough string in a context-free language splits into five parts u, v, x, y, z where v and y aren't both empty, and u v^i x y^i z stays in the language for all i. You pump v and y together.

You use it the same way, to prove a language is not context-free. The go-to example is a^n b^n c^n: any way you place v and y can pump at most two of the three symbols, so the three counts can't stay equal, and the string leaves the language. That's why a^n b^n c^n is context-sensitive, not context-free.

No, and this is a key contrast with regular languages. Context-free languages are closed under union, concatenation, and Kleene star, but not under intersection or complement. The classic counterexample: a^n b^n c^m and a^m b^n c^n are both context-free, but their intersection is a^n b^n c^n, which isn't context-free.

Since closure under complement plus union would give closure under intersection (by De Morgan), the failure of intersection means complement fails too. Regular languages are closed under everything; context-free languages lose intersection and complement. That difference shows up in interview closure-property questions.

A reduction transforms one problem into another so that a solution to the second gives a solution to the first. If you can convert every instance of problem A into an instance of problem B such that the answers match, you've reduced A to B. It says B is at least as hard as A.

It's the main proof engine in the field. To show a problem is undecidable, reduce a known undecidable problem (like the halting problem) to it. To show a problem is NP-hard, reduce a known NP-complete problem to it. The direction matters: reducing A to B proves B is hard, not A.

Plenty of automata questions are decidable. Whether a given DFA accepts a specific string is decidable: just run it. Whether a DFA's language is empty is decidable: check if any accepting state is reachable. Whether two DFAs are equivalent is decidable: minimize both and compare, or check the symmetric difference is empty.

For context-free grammars, whether the language is empty and whether a specific string is generated (via CYK parsing) are both decidable. The contrast worth knowing: whether two context-free grammars generate the same language is undecidable, even though the DFA version is decidable. Same-sounding questions can land on opposite sides of the line.

Decidable languages are closed under complement. If a Turing machine decides a language and always halts, you flip its accept and reject outputs to decide the complement, and it still always halts. Decidable languages are also closed under union and intersection.

Recognizable languages are not closed under complement. The reason is a clean theorem: a language is decidable if and only if both it and its complement are recognizable. The halting problem is recognizable but undecidable, so its complement can't be recognizable, or the language would be decidable. That asymmetry is a common exam and interview point.

A language is recursively enumerable if some procedure can list (enumerate) all its members, one after another, possibly never stopping. That's equivalent to being recognizable by a Turing machine: if you can accept exactly the members, you can enumerate them by running all strings in a dovetailed order and printing each one your machine accepts.

The 'enumerable' framing is why non-members are the problem: you can eventually list every member, but you can never be sure a string won't show up later, so you can't reject with certainty. That's exactly the recognizable-but-not-decidable gap, viewed as a listing process instead of an accept/reject one.

A linear bounded automaton is a Turing machine whose tape is limited to the space taken by the input (up to a constant factor), so it can't use unbounded extra memory. That restriction sits between the pushdown automaton and the full Turing machine in power.

It recognizes the context-sensitive languages, type 1 in the Chomsky hierarchy. Languages like a^n b^n c^n that a PDA can't handle but that only need bounded workspace fall here. The open theoretical question tied to it (whether nondeterministic and deterministic versions are equal) is the LBA problem, which is worth a mention if pushed.

They describe the same class: a language is context-free if and only if some pushdown automaton recognizes it. The two are interconvertible. From a grammar you can build a PDA that uses its stack to simulate leftmost derivations, pushing the right-hand side of a rule and matching terminals against the input.

From a PDA you can build an equivalent grammar, though the construction is fiddlier. This equivalence is the context-free analog of Kleene's theorem for regular languages: the generating form (grammar) and the recognizing form (automaton) coincide. It's why parser generators start from a grammar.

A universal Turing machine takes as input a description of another Turing machine plus that machine's input, and simulates it. One fixed machine can run any machine you hand it, which is the theoretical basis for the stored-program computer: code is just data the interpreter reads.

Its existence matters for proofs. Because a machine's description can be fed to another machine as a string, you can build self-referential arguments, and that's exactly what the undecidability of the halting problem relies on. The universal machine is what makes 'programs that reason about programs' a formal object.

The CYK (Cocke-Younger-Kasami) algorithm decides whether a given string can be generated by a context-free grammar, and if so builds its parse. It's a dynamic-programming method that works on a grammar in Chomsky normal form, filling a table where each cell records which variables can derive each substring, combining shorter spans into longer ones.

It runs in time cubic in the string length, times the grammar size, so it's a polynomial-time membership test for context-free languages. That's the key takeaway: membership for a context-free grammar is decidable and efficient, even though other questions about grammars (like equivalence) aren't decidable at all.

In Chomsky normal form, every rule is either a single variable going to exactly two variables, or a variable going to a single terminal (with the empty string handled separately for the start symbol). Any context-free grammar can be converted to an equivalent one in this form.

The reason to convert is that the restricted shape makes algorithms simpler and derivations predictable: every internal step of a parse tree becomes a binary branch. The CYK algorithm needs this form, and many proofs about context-free languages assume it because the fixed structure removes special cases like long right-hand sides or chains of unit rules.

Assume a decider H exists that, given a program P and input x, always halts and says whether P halts on x. Build a new program D that takes a program P, runs H on (P, P), and then does the opposite: if H says P halts on P, then D loops forever, and if H says P doesn't halt, D halts.

Now ask what D does on its own description: run D on D. If D halts on D, then by its construction H said it doesn't, contradiction. If D loops on D, then H said it halts, so D should have looped only when H said halt, contradiction either way. No consistent answer exists, so H can't exist. The halting problem is undecidable.

Rice's theorem says any non-trivial semantic property of the language a Turing machine recognizes is undecidable. Non-trivial means at least one machine has the property and at least one doesn't; semantic means it's about the machine's behavior (its language), not its syntax (its states or code).

So questions like 'does this program compute the constant zero function', 'does it accept any input', or 'does its language equal some fixed target' are all undecidable, in one sweep. It generalizes the halting problem: instead of proving each behavioral question undecidable by a separate reduction, Rice's theorem hands you undecidability for the whole category at once.

You reduce a known undecidable problem to the new one. Concretely, to show problem B is undecidable, assume a decider for B existed and use it to build a decider for a known-undecidable problem A, usually the halting problem or the acceptance problem. Since A has no decider, B can't have one either.

The construction is a computable transformation: given an instance of A, produce an instance of B whose answer matches. For example, to prove the emptiness problem for Turing machines is undecidable, map a halting question into a machine whose language is non-empty exactly when the original machine halts. The reduction must itself be computable, or the argument breaks.

P is the class of decision problems a deterministic machine solves in polynomial time. NP is the class where a proposed solution can be verified in polynomial time, equivalently, a nondeterministic machine solves them in polynomial time. Every problem in P is in NP, because if you can solve it fast you can verify it fast.

The open question is whether P equals NP: is every efficiently verifiable problem also efficiently solvable. Most researchers believe P doesn't equal NP, meaning some problems are genuinely hard to solve even though checking an answer is easy. It's unproven, and it's one of the Millennium Prize problems.

A problem is NP-complete if it's in NP and it's NP-hard, meaning every problem in NP reduces to it in polynomial time. NP-complete problems are the hardest problems in NP: they're all equivalent under polynomial reduction, so a fast algorithm for any one of them would give a fast algorithm for all of NP, proving P equals NP.

It matters practically. Recognizing that your problem is NP-complete tells you to stop hunting for a guaranteed-fast exact algorithm and instead use approximation, heuristics, or exponential methods that work on the instance sizes you actually have. Examples: SAT, 3-SAT, the traveling salesman decision version, graph coloring, subset sum.

The Cook-Levin theorem proves that boolean satisfiability (SAT) is NP-complete. It was the first problem shown NP-complete, established by constructing, for any nondeterministic polynomial-time machine and input, a boolean formula that's satisfiable exactly when the machine accepts. That directly shows every NP problem reduces to SAT.

It's foundational because it bootstraps the whole theory of NP-completeness. Once SAT is known NP-complete, you prove other problems NP-complete just by reducing SAT (or another known NP-complete problem) to them, which is far easier than encoding a Turing machine each time. Every NP-completeness proof traces back to Cook-Levin.

Two steps. First show the problem is in NP by giving a polynomial-time verifier: a certificate and a check that runs in polynomial time. Second show it's NP-hard by reducing a known NP-complete problem to it in polynomial time, mapping instances so yes-instances map to yes-instances and no to no.

The reduction direction is what people get wrong: you reduce the known-hard problem INTO your problem, showing your problem is at least as hard. Pick a source problem structurally close to yours (3-SAT for logic-flavored problems, vertex cover or clique for graph problems) so the gadget construction stays manageable.

NP-hard means at least as hard as every problem in NP: everything in NP reduces to it in polynomial time. It does not require the problem itself to be in NP, so an NP-hard problem can be much harder, even undecidable. NP-complete means both NP-hard and in NP, so it's the hardest problems that are still in NP.

The distinction shows up with optimization and undecidable problems. The halting problem is NP-hard (everything reduces to it) but not in NP and not NP-complete, because it isn't even decidable. The traveling salesman optimization problem is NP-hard; its decision version is NP-complete. Membership in NP is the dividing line.

No, and conflating them is a common senior-interview trap. NP-complete problems are decidable: you can always solve them, for instance by brute-forcing all candidate solutions, it just takes exponential time in the worst case. They're hard in the efficiency sense, not the solvability sense.

Undecidable problems like the halting problem can't be solved by any algorithm at all, no matter how much time you allow. So the two live in different worlds: NP-completeness is about tractability (P vs NP), undecidability is about computability (what's solvable in principle). A problem being NP-complete guarantees it's decidable.

PSPACE is the class of problems solvable using polynomial memory, with no limit on time. It contains both P and NP, because a machine with polynomial space can, given enough time, explore the exponentially many possibilities that an NP verifier's certificates represent. Whether NP equals PSPACE is open.

The known chain is P is contained in NP, which is contained in PSPACE, which is contained in EXPTIME, and we know P is strictly inside EXPTIME by the time hierarchy theorem, so at least one of those containments is strict, but we don't know which. Savitch's theorem adds that nondeterministic and deterministic polynomial space coincide (PSPACE equals NPSPACE), which is why space behaves more tamely than time.

Mapping (many-one) reducibility transforms an instance of A into a single instance of B with a computable function, so a decider for B is called exactly once and its answer is A's answer. It's the strict notion used to define NP-completeness and most undecidability results.

Turing reducibility is looser: A is Turing-reducible to B if a machine with an oracle for B (able to query B freely, many times, and act on the answers) can decide A. Every mapping reduction is a Turing reduction, but not the reverse. Turing reducibility can relate problems that mapping reducibility can't, for instance a language and its complement, which is why the finer distinction matters in computability theory.

The time hierarchy theorem says more time strictly buys more computational power: for reasonable (time-constructible) bounds, there are problems solvable in, say, n-cubed time that provably can't be solved in n-squared time. So the time-bounded classes form a strict infinite hierarchy.

Its concrete payoff is one of the few unconditional separations we have. It proves P is strictly contained in EXPTIME, no assumptions needed, using a diagonalization argument much like the halting-problem proof. That's why we can say for certain that some decidable problems are genuinely intractable, even while P versus NP stays open.

Diagonalization is a proof technique that constructs an object differing from every item on a list, by disagreeing with the n-th item in its n-th position. Cantor used it to show the reals are uncountable; the same trick shows there are more languages than Turing machines, so some languages can't be recognized at all.

It recurs because the field is full of self-reference and enumeration. The halting-problem proof, the undecidability results, and the time hierarchy theorem all build a machine that does the opposite of what the n-th machine does on its own input. Recognizing when a problem calls for a diagonal argument is a mark of comfort with the theory.

More than people expect. Regular expressions and lexers are finite automata, so understanding regular languages tells you why some matching is fast and why backreferences can blow up. Parsers and compilers are built on context-free grammars, and grammar ambiguity is a real bug source in language design. Recognizing an NP-complete problem (scheduling, routing, allocation) tells you to reach for approximation or a solver instead of a doomed exact algorithm.

The computability side has a practical edge too. Undecidability explains why no static analyzer can perfectly detect all bugs or infinite loops (Rice's theorem), which sets honest expectations for tooling. The theory doesn't write your code, but it tells you which goals are achievable and where to stop trying for a perfect solution.

NP is the class of problems where a yes-answer has a short, quickly verifiable certificate. Co-NP is the mirror: problems where a no-answer has a short, quickly verifiable certificate. So 'is this formula satisfiable' is in NP (a satisfying assignment proves yes), while 'is this formula unsatisfiable' is in co-NP.

Every problem in P is in both NP and co-NP, since you can just solve it. Whether NP equals co-NP is open and separate from P versus NP: if they differ, then P doesn't equal NP, but the reverse isn't known. It's widely believed NP and co-NP are different, which is why nobody expects a short certificate for unsatisfiability.

Reduce 3-SAT to the Clique problem. Given a 3-SAT formula with k clauses, build a graph: for each literal in each clause make a vertex, so three vertices per clause. Add an edge between two vertices whenever they belong to different clauses and don't contradict each other, meaning you never a variable connects to its own negation.

Now the formula is satisfiable exactly when the graph has a clique of size k. A satisfying assignment picks one true literal per clause, and those chosen vertices are pairwise connected (different clauses, non-contradictory), forming a k-clique. Conversely a k-clique must use one vertex per clause with consistent choices, giving a satisfying assignment. The reduction is polynomial, so since 3-SAT is NP-complete, Clique is NP-hard, and since Clique is in NP, it's NP-complete.