The Theory of Computation (TOC) helps us understand:
Capabilities of machines
Problems that can be solved
Limitations of machines
It focuses on the logic and concepts of machines rather than hardware details.
Purpose:
Allows systematic thinking about what machines can do
Helps analyze computational tasks mathematically
Computation = Any calculation or task performed by a machine (like a calculator, computer, etc.).
Computations are used to represent mathematical models such as:
Finite Automata (FA)
Pushdown Automata (PDA)
Turing Machine (TM)
TOC studies mathematical models of abstract machines and computational problems that these models can solve.
It is divided into three main branches:
| Branch | Focus Area |
|---|---|
| Automata Theory | Deals with properties of mathematical models like FA, PDA, etc. |
| Computability Theory | Studies what can and cannot be computed by a machine. |
| Complexity Theory | Analyzes computable problems based on their difficulty (hardness). |
A symbol is a single unit of input (a character) for a machine.
Symbols are used to build languages for machines.
Examples:
Digits: 0, 1, 2, 3
Alphabets: a, b, c
Special symbols: !, $, #, @, <, >, ?
An alphabet is a finite, non-empty set of symbols.
Denoted by Σ.
Examples:
Σ = {0,1,2}
Σ = {a, b, f}
Σ = {A, B, C, Z}
A string is a finite sequence of symbols from an alphabet Σ.
Length of a string (|w|) = Number of symbols in the string.
Examples:
Σ = {0,1}, w = 01101001 → |w| = 8
Σ = {a,b}, w = abbaa → |w| = 5
w = E (empty string) → |w| = 0
Combining two strings x and y to form a new string.
Example:
x = abc, y = pqr
Concatenation: xy = abcpqr
Σ^k = Set of all strings of length k over alphabet Σ.
Examples:
Σ = {0,1}, k = 2 → Σ² = {00, 01, 10, 11}
Σ = {0,1}, k = 3 → Σ³ = {000, 001, 010, 011, 100, 101, 110, 111}
Notes:
Σ⁰ = {ε} → Set containing the empty string ε
Cartesian Product: Σ^k can be seen as repeated Cartesian product of Σ with itself k times.
Symbol: *
Definition: Unary operator on an alphabet Σ that represents the set of all possible strings of any length, including the empty string (ε).
Key Points:
Includes null (ε).
Produces an infinite set of strings.
Example:
Σ = {5, 6} → Σ* = {ε, 5, 6, 55, 56, 65, 66, 555, …}
Σ = {a, b} → Σ* = {ε, a, b, aa, ab, ba, bb, aaa, …}
Symbol: +
Definition: Unary operator on an alphabet Σ that represents the set of all possible strings of any length, excluding the empty string (ε).
Key Points:
Does not include ε.
Produces an infinite set of strings.
Example:
Σ = {a, b} → Σ⁺ = {a, b, aa, ab, ba, bb, aaa, …}
Σ = {5, 6} → Σ⁺ = {5, 6, 55, 56, 65, 66, …}
Definition: A language (L) is a collection of strings formed from an alphabet Σ.
Types of Language:
Finite Language: Contains a limited number of strings.
Example:
Σ = {a, b}
L = {aa, ab, ba, bb} → Strings of length 2 → finite set
Infinite Language: Contains an infinite number of strings.
Example:
Σ = {a, b}
L = {a, b, aa, ab, ba, bb, aaa, …} → Infinite set
Notes:
A language can be finite or infinite.
Σ* (Kleene Star) is the parent of all languages over an alphabet Σ.