📘 PAPER 1: THEORY OF COMPUTATION (MCA546) UNIT -1 Recursive Functions & Formal Languages (university of allahabad)

 

🔴 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

1. Zero function:
   Z(x) = 0

2. Successor function:
   S(x) = x + 1

3. Projection function:
   Pᵢⁿ(x₁, x₂, …, xₙ) = xᵢ

---

Operations Used to Build Recursive Functions

1. Composition

2. Primitive recursion

3. Minimization

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

• Regular

• Context-Free

• Context-Sensitive

• Recursively Enumerable

---

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