🔴 UNIT 1: Recursive Functions & Formal Languages
(VERY IMPORTANT – Theory + Definitions + Examples)
1️⃣ Partial and Total Functions
Function
A function is a mapping from one set (domain) to another set (codomain) where each input has exactly one output.
Partial Function
A function is called partial if it is not defined for every input in its domain.
Example:
Let
f(x) = x ÷ y
If y = 0, the function is undefined.
So, f(x) is a partial function.
➡ Some inputs produce output, some do not.
Total Function
A function is total if it is defined for every element of its domain.
Example:
f(x) = x²
For every integer x, f(x) is defined.
➡ All inputs give output.
Difference (Exam-Friendly)
| Partial Function | Total Function |
|---|---|
| Not defined for all inputs | Defined for all inputs |
| May not halt | Always halts |
| Used in computability theory | Used in mathematics |
2️⃣ Recursive Functions
Recursive functions are functions defined using simpler functions and rules.
Basic Functions
-
Zero function:
Z(x) = 0 -
Successor function:
S(x) = x + 1 -
Projection function:
Pᵢⁿ(x₁, x₂, …, xₙ) = xᵢ
Operations Used to Build Recursive Functions
A function built using these operations is called a recursive function.
Importance
-
Used to define computable functions
-
Foundation of algorithm theory
-
Equivalent to Turing computability
3️⃣ Bounded Minimization
Minimization Operator (μ)
Used to find the smallest value for which a function becomes zero.
Bounded Minimization
Search is restricted to a fixed limit.
Definition:
μx ≤ k [f(x) = 0]
➡ Guarantees termination
➡ Produces total recursive functions
Why Important
-
Prevents infinite loops
-
Used in defining primitive recursive functions
4️⃣ Ackermann’s Function
Ackermann’s function is a total computable function but not primitive recursive.
Definition
A(m, n) =
-
n + 1, if m = 0
-
A(m − 1, 1), if m > 0 and n = 0
-
A(m − 1, A(m, n − 1)), if m > 0 and n > 0
Key Points
-
Grows very fast
-
Shows limits of primitive recursion
-
Important example in theory of computation
➡ Frequently asked as theoretical question
5️⃣ Strings
A string is a finite sequence of symbols taken from an alphabet.
Alphabet (Σ)
A finite non-empty set of symbols.
Example:
Σ = {0,1}
Examples of Strings
-
ε (empty string)
-
0
-
10101
Length of String
|w| = number of symbols in w
Example:
|101| = 3
6️⃣ Free Semi-Group
A free semi-group is a set of all non-empty strings over an alphabet under concatenation.
Properties
-
Closure under concatenation
-
Associative operation
-
No identity element
Example:
Σ⁺ = {0, 1, 01, 10, 110, …}
7️⃣ Languages
A language is a set of strings over an alphabet.
Definition
L ⊆ Σ*
Examples
-
L = {0ⁿ1ⁿ | n ≥ 1}
-
L = set of all valid identifiers
Types of Languages
8️⃣ Generative Grammars and Their Languages
A grammar is a formal system used to generate languages.
Grammar G
G = (V, Σ, P, S)
Where:
-
V → Variables
-
Σ → Terminals
-
P → Productions
-
S → Start symbol
Language Generated
L(G) = all strings derived from S using P.
9️⃣ Chomsky Classification of Grammars
Chomsky classified grammars into four types:
| Type | Grammar | Language | Machine |
|---|---|---|---|
| Type 0 | Unrestricted | Recursively Enumerable | Turing Machine |
| Type 1 | Context Sensitive | CSL | Linear Bounded Automata |
| Type 2 | Context Free | CFL | Pushdown Automata |
| Type 3 | Regular | RL | Finite Automata |
