हिंदी में: कंप्यूटर क्या-क्या गणना कर सकता है और क्या नहीं — ऑटोमेटा, ग्रामर और ट्यूरिंग मशीन।
Why study theory of computation?
Theory of Computation (TOC) answers three questions: What can be computed? How efficiently? With what kind of machine? It is the foundation for compilers, text search, regular expressions, protocol design and complexity theory.
Basic terms
- Alphabet (Σ) – a finite set of symbols, e.g. {0, 1}.
- String – a finite sequence of symbols; ε is the empty string.
- Language – a set of strings over an alphabet, e.g. all binary strings ending in 1.
Finite automata and regular languages
A Deterministic Finite Automaton (DFA) has a finite set of states, one start state, accepting states and exactly one transition for each symbol from each state.
An NFA may have several (or zero) transitions for a symbol and ε-moves. Every NFA can be converted to an equivalent DFA (subset construction), so both recognise exactly the regular languages.
Regular expressions describe the same class of languages. Example: (0|1)*1 = binary strings ending in 1; (a|b)*abb = strings over {a, b} ending in “abb”.
Pumping lemma (regular): used to prove a language is not regular. Example: { aⁿbⁿ | n ≥ 0 } is not regular, because a finite automaton cannot count without limit.
Regular languages are closed under union, concatenation, Kleene star, intersection and complement.
Context-free grammars and pushdown automata
A context-free grammar (CFG) has rules like S → aSb | ε, which generates { aⁿbⁿ }. CFGs describe the syntax of most programming languages.
A Pushdown Automaton (PDA) is a finite automaton plus a stack, and recognises exactly the context-free languages.
Related ideas: derivations and parse trees, ambiguity (a string with two parse trees), Chomsky Normal Form and Greibach Normal Form. { aⁿbⁿcⁿ } is not context-free (shown with the CFL pumping lemma).
Turing machines
A Turing machine has a finite control and an infinite tape it can read, write and move on in both directions. The Church–Turing thesis states that anything that can be computed by an algorithm can be computed by a Turing machine.
The Chomsky hierarchy
| Type | Grammar | Machine | Example language |
|---|---|---|---|
| Type 3 | Regular | Finite automaton | (ab)* |
| Type 2 | Context-free | Pushdown automaton | aⁿbⁿ |
| Type 1 | Context-sensitive | Linear bounded automaton | aⁿbⁿcⁿ |
| Type 0 | Unrestricted | Turing machine | Recursively enumerable languages |
Each class strictly contains the one above it.
Decidability
- A problem is decidable if some Turing machine always halts with the correct yes/no answer.
- The Halting Problem — “does program P halt on input x?” — is undecidable (proved by Alan Turing in 1936).
- Other undecidable problems: whether two CFGs generate the same language, Post’s Correspondence Problem.
- Recursive languages are decidable; recursively enumerable languages are those a TM can accept (it may run forever on strings not in the language).
Quick revision
- DFA = NFA = regular expressions in power.
- PDA = finite automaton + stack = context-free languages.
- aⁿbⁿ is context-free but not regular; aⁿbⁿcⁿ is not context-free.
- The Halting Problem is undecidable.