Theoretical Computer Science Concepts
Core concepts
Formal language
Any set of strings over an alphabet. The basis for everything in automata and computability theory.
DFA
Deterministic finite automaton — exactly one transition per input symbol per state. No ambiguity, no ε-transitions.
NFA
Nondeterministic finite automaton — allows ε-transitions and multiple transitions per symbol. Equivalent in power to DFAs, not stronger.
Context-free grammar
Productions replace variables with strings of variables and/or terminals. Generates languages with nested structure — not just finite ones.
Pushdown automaton
Extends finite automata with a stack. Recognizes exactly the context-free languages — more powerful than DFAs/NFAs.
Turing machine
Has an infinite tape and can read, write, and move in both directions. More powerful than PDAs — can rewrite memory arbitrarily.
Church–Turing thesis
Turing machines define the boundary of what is computable. Any effectively computable function can be computed by a TM.
Halting problem
Undecidable — no algorithm can determine whether an arbitrary program halts for all inputs. Not a question of input size.
Class P
Problems solvable in polynomial time. Tractable in practice.
Class NP
Problems whose solutions are verifiable in polynomial time. P ⊆ NP — whether P = NP is unsolved.
NP-complete
A problem that is both in NP and NP-hard. If any NP-complete problem is in P, then P = NP.
Reductions
Transform one problem into another to show relative difficulty. Used to prove NP-hardness and relate complexity classes.
Regular vs non-regular
Regular languages are recognized by DFAs/NFAs. Balanced parentheses is a classic non-regular language — it requires a stack.
Time complexity
Measures how runtime grows as a function of input size — not grammar rules, not memory. O(n log n) is still polynomial.
Watch out for
  • NFAs are not more powerful than DFAs — they are equivalent. The difference is nondeterminism, not capability.
  • PDAs recognize context-free languages, not recursively enumerable ones — that's Turing machines.
  • Turing machine tapes are infinite, not finite.
  • The halting problem is undecidable because of the nature of self-reference — not because inputs are too large.
  • NP-complete means in NP AND NP-hard — belonging to P alone is not sufficient.
  • If P = NP, all NP-complete problems become polynomial-time solvable — not all problems become unsolvable.
→ This page was created with help from Claude AI.