Alphabets, Strings and Languages
Every model in the theory of computation (finite automata, pushdown automata, Turing machines) processes strings built from a fixed finite alphabet. A language is simply a set of strings.
TOC · Short notes
Theory of Computation short notes
17 short notes in syllabus order, about 122 minutes to read end to end.
Regular expressions
Regular Expressions
A regular expression (RE) is a concise notation for a language built from single symbols by union, concatenation and Kleene star.
Equivalence of Regular Expressions and Finite Automata
Regular expressions and finite automata define the same class of languages. One direction builds an ε-NFA from an expression (Thompson's construction). The other eliminates states from a DFA (or NFA) until a single regular expression remains.
Finite automata: DFA, NFA and minimization
Deterministic Finite Automata
A deterministic finite automaton (DFA) is a finite-state machine that reads an input string from left to right, one symbol at a time, and either accepts or rejects. At every step the next state is uniquely determined by the current state and the current symbol.
NFA, Epsilon-NFA and Subset Construction
A nondeterministic finite automaton (NFA) may have zero, one or many next states for a given state and symbol. It accepts a string if some sequence of choices leads to an accepting state. Allowing ε-transitions (moves without reading input) gives an ε-NFA.
DFA Minimization
Two states of a DFA are equivalent when no string leads from one to an accept state and from the other to a reject state. Merging equivalent states yields the unique (up to renaming) minimal DFA for the language: fewest states among all DFAs for that language.
Regular languages: closure, decision properties and pumping lemma
Closure and Decision Properties of Regular Languages
Regular languages are closed under a rich family of operations: Boolean operations, concatenation, star, reverse, homomorphisms and inverse homomorphisms. They also have decidable emptiness, membership, finiteness and equivalence.
Pumping Lemma for Regular Languages
The pumping lemma for regular languages is a necessary condition that every regular language satisfies. Its main use is negative: if you can show that a language breaks the condition, the language is not regular.
Context-free grammars
Context-Free Grammars, Derivations and Ambiguity
A context-free grammar (CFG) generates a language by rewriting nonterminals one at a time, independently of surrounding context. The languages of CFGs are the context-free languages (CFLs), recognized by pushdown automata.
CFG Simplification and Normal Forms
Before algorithms such as CYK or proofs such as the CFL pumping lemma, grammars are cleaned: remove useless symbols, ε-productions (when ε ∉ L), and unit productions, then convert to Chomsky normal form (CNF) or Greibach normal form (GNF).
Push-down automata
Pushdown Automata
A pushdown automaton (PDA) is an NFA equipped with a stack. The stack provides unbounded memory that is accessible only at the top, which is exactly the power needed for context-free languages: every CFG has an equivalent PDA and every PDA has an equivalent CFG.
Deterministic PDAs and DCFLs
A deterministic pushdown automaton (DPDA) never has a choice of move: at most one transition applies for the current state, input symbol (or ε), and top-of-stack symbol, and ε-input moves cannot compete with a defined symbol move. Languages of DPDAs are deterministic context-free languages (DCFLs).
Context-free languages: closure, decision properties and pumping lemma
Closure and Decision Properties of CFLs
Context-free languages are closed under union, concatenation, star, reverse and homomorphism, and under intersection with regular languages. They are not closed under intersection or complement. Membership, emptiness and finiteness are decidable for CFGs; equivalence and regularity are not.
Pumping Lemma for Context-Free Languages
The pumping lemma for context-free languages gives a necessary condition on every CFL. It is used to prove that languages such as a^n b^n c^n and ww are not context-free. The decomposition has five pieces uvxyz with constraints that reflect a repeated path in a CNF parse tree.
Turing machines
Turing Machines
A Turing machine (TM) is a finite-state controller with a doubly infinite (or one-way infinite) tape and a read/write head. It is the standard model of general-purpose computation.) languages; languages decided by TMs that always halt are the recursive (decidable) languages.
Chomsky Hierarchy and Language Classes
The Chomsky hierarchy organizes grammars and their languages into four classical types: regular (Type-3), context-free (Type-2), context-sensitive (Type-1), and unrestricted (Type-0). Matching machine models are finite automata, PDAs, linear bounded automata (LBAs), and Turing machines.
Decidability and undecidability
Decidability and Undecidability
A language is decidable (recursive) if some TM halts on every input and accepts exactly the strings in the language. It is undecidable if no such TM exists.