📘 PAPER 1: THEORY OF COMPUTATION (MCA546) UNIT 5: TURING MACHINES & UNDECIDABILITY (university of allahabad )

 

🔴 UNIT 5: TURING MACHINES & UNDECIDABILITY

---

1️⃣ Turing Machine (TM)

✅ Definition

A Turing Machine is the most powerful abstract machine used to model computation.

It can solve any problem that is algorithmically computable.

---

✅ Components of Turing Machine

A Turing Machine is a 7-tuple:

M = (Q, Σ, Γ, δ, q₀, B, F)

Where:

• Q → Finite set of states

• Σ → Input alphabet

• Γ → Tape alphabet

• δ → Transition function

• q₀ → Initial state

• B → Blank symbol

• F → Final (accepting) states

---

✅ Structure of TM

A Turing Machine has:

• Infinite tape

• Read/Write head

• Finite control

• Move Left / Right / Stay

---

2️⃣ Instantaneous Description (ID)

✅ Definition

An Instantaneous Description (ID) represents the current state of the Turing Machine.

Format:

$$α q β$$

Where:

• α → Tape content to left of head

• q → Current state

• β → Tape content under and right of head

---

✅ Example

101q011

Means:

• Head is reading 0

• Current state = q

• Tape contains 101011

---

3️⃣ Language Accepted by Turing Machine

A language L is said to be accepted by a TM if:

• TM halts in accepting state for every string in L

• TM may loop for strings not in L

---

4️⃣ Turing Computability of Functions

A function is Turing computable if:

• There exists a TM that computes it

• TM halts for all valid inputs

---

Important Fact

All recursive functions are Turing computable

---

5️⃣ Equivalence of Turing Machine and Recursive Functions

Theorem:

A function is Turing computable if and only if it is partial recursive.

This proves:

• Turing Machine

• Recursive Functions

• Lambda Calculus

➡ All are equivalent models of computation

---

6️⃣ Recursively Enumerable (RE) Languages

✅ Definition

A language L is recursively enumerable if:

• There exists a Turing Machine that accepts L

• TM may not halt for strings not in L

---

✅ Types of Languages

Language Type	Description
Recursive	TM halts for all inputs
Recursively Enumerable	TM may loop
Non-RE	Not accepted by any TM

---

7️⃣ Recursively Decidable Languages

✅ Definition

A language is recursive (decidable) if:

• TM halts for all inputs

• Gives YES or NO answer

---

Relationship

Recursive ⊂ Recursively Enumerable

---

8️⃣ Undecidability

✅ Definition

A problem is undecidable if:

• No algorithm exists to solve it for all inputs

• TM cannot decide it

---

9️⃣ Undecidability of Type-0 Grammar

Type-0 grammars generate:

• Recursively enumerable languages

Problem:

Whether a given string belongs to a Type-0 grammar?

Result:

❌ Undecidable

Because:

• Equivalent to Halting Problem

• No general algorithm exists

---

🔟 Church–Turing Thesis

✅ Statement

Any function that can be computed by an algorithm can be computed by a Turing Machine.

---

⚠ Important Points

• Not a theorem (cannot be proved)

• Based on strong evidence

• Foundation of computer science

---

1️⃣1️⃣ Halting Problem

✅ Problem Statement

Given a program P and input I, determine:

Will P halt or run forever?

---

✅ Result

🚫 Halting Problem is Undecidable

---

✅ Proof Idea (Simple)

• Assume halting problem is decidable

• Construct a contradictory machine

• Leads to logical contradiction

• Hence undecidable

---

1️⃣2️⃣ Importance of Halting Problem

• Shows limits of computation

• Basis of undecidability theory

• Used in compiler design & verification

📘 PAPER 1: THEORY OF COMPUTATION (MCA546) UNIT 4: PUSH DOWN AUTOMATA (PDA) (university of allahabad)

 

🔴 UNIT 4: PUSH DOWN AUTOMATA (PDA)

This unit is very important because it connects CFG and Automata, and questions often come for 5–10 marks.

---

1️⃣ Pushdown Automata (PDA)

✅ Definition

A Pushdown Automaton (PDA) is a computational model that:

• Has finite control

• Uses a stack (LIFO)

• Recognizes Context-Free Languages (CFLs)

---

✅ Formal Definition

A PDA is a 7-tuple:

M = (Q, Σ, Γ, δ, q₀, Z₀, F)

Where:

• Q → Finite set of states

• Σ → Input alphabet

• Γ → Stack alphabet

• δ → Transition function

• q₀ → Initial state

• Z₀ → Initial stack symbol

• F → Final states

---

✅ Transition Function

$$\delta : Q × (Σ ∪ \{ε\}) × Γ → P(Q × Γ^*)$$

Meaning:

• Read input symbol or ε

• Pop top of stack

• Push new symbol(s)

---

2️⃣ Instantaneous Description (ID)

✅ Definition

An Instantaneous Description (ID) describes the current status of a PDA at any moment.

Format:

$$(q, w, γ)$$

Where:

• q → Current state

• w → Remaining input

• γ → Stack content

---

✅ Example

(q₀, 1011, Z₀)

Means:

• Current state = q₀

• Input remaining = 1011

• Stack contains = Z₀

---

3️⃣ Acceptance by PDA

A PDA can accept a language in two ways:

---

🔹 1. Acceptance by Final State

A string is accepted if:

• Input is completely read

• PDA reaches a final state

✔ Stack content does not matter

---

🔹 2. Acceptance by Empty Stack

A string is accepted if:

• Input is fully consumed

• Stack becomes empty

✔ Final state not necessary

---

⚠ Important Theorem

👉 Both methods are equivalent in power

---

4️⃣ Deterministic Pushdown Automata (DPDA)

✅ Definition

A PDA is deterministic if:

• For a given state, input symbol, and stack symbol

• Only one transition is possible

---

✅ Key Points

• DPDA ⊂ PDA

• DPDA recognizes deterministic CFL

• Not all CFLs are accepted by DPDA

---

✅ Example

Language:
L = { aⁿbⁿ | n ≥ 1 }

✔ Can be accepted by DPDA

---

❌ Example

L = { wwʳ | w ∈ {a,b}* }

✖ Cannot be accepted by DPDA

---

5️⃣ Relationship Between PDA and CFG

🔹 Important Theorem

A language is context-free if and only if it is accepted by a PDA

---

🔹 CFG → PDA

For every CFG, there exists a PDA that:

• Simulates leftmost derivation

• Uses stack to store variables

---

🔹 PDA → CFG

For every PDA, a CFG can be constructed that:

• Generates same language

• Uses transitions to define productions

---

🔁 Relationship Diagram

CFG  ⇄  PDA

---

6️⃣ PDA for Language aⁿbⁿ

Language:

L = { aⁿbⁿ | n ≥ 1 }

---

Working:

1. Push a onto stack for each input a

2. Pop one a for each b

3. Accept when stack is empty

---

Stack Behavior:

Input	Stack
a	push a
a	push a
b	pop a
b	pop a

---

7️⃣ Difference: FA vs PDA

Finite Automata	Pushdown Automata
No stack	Has stack
Recognizes regular languages	Recognizes CFL
Limited memory	Infinite memory (stack)
DFA/NFA	PDA

---

8️⃣ Applications of PDA

• Syntax checking

• Compiler design

• Expression evaluation

• Parsing in programming languages

📘 PAPER 1: THEORY OF COMPUTATION (MCA546) UNIT -3 Context Free Grammars (CFG) (university of allahabad)

🔴 UNIT 3: Context Free Grammars (CFG)

(EXTREMELY IMPORTANT – Long answers + conversions often asked)

---

1️⃣ Context Free Grammar (CFG)

Definition

A Context Free Grammar is a grammar in which each production rule has a single non-terminal on the left-hand side.

Formal Definition

A CFG is a 4-tuple:

G = (V, Σ, P, S)

Where:

• V → Set of non-terminals

• Σ → Set of terminals

• P → Production rules

• S → Start symbol

---

Form of Productions

A → α
Where:

• A ∈ V

• α ∈ (V ∪ Σ)*

---

Example

Grammar for L = { aⁿbⁿ | n ≥ 1 }

Productions:

• S → aSb

• S → ab

---

2️⃣ Derivation in CFG

Derivation

Process of generating strings from the start symbol using production rules.

---

Types of Derivation

Leftmost Derivation

• Always expand the leftmost non-terminal

Rightmost Derivation

• Always expand the rightmost non-terminal

---

Example

S → aSb → aab b

---

3️⃣ Derivation Trees (Parse Trees)

Definition

A derivation tree (or parse tree) is a tree representation of how a string is generated in a CFG.

---

Properties

• Root → Start symbol

• Internal nodes → Non-terminals

• Leaves → Terminals

• Reading leaves left to right gives the string

---

Importance

• Shows structure of language

• Used in compilers

• Common exam question

---

4️⃣ Ambiguity in CFG

Ambiguous Grammar

A grammar is ambiguous if a string has more than one parse tree.

---

Example

Grammar:
E → E + E | E * E | id

Expression: id + id * id

➡ Two different parse trees possible

---

Key Point

• Some languages are inherently ambiguous

• Ambiguity is undesirable in compilers

---

5️⃣ Simplification of Context Free Grammars

Simplification means removing unnecessary productions without changing the language.

---

Steps of Simplification

(a) Removal of ε-productions

Productions of the form:
A → ε

---

(b) Removal of Unit Productions

Productions of the form:
A → B

---

(c) Removal of Useless Symbols

• Non-generating symbols

• Unreachable symbols

---

Result

Simplified grammar that generates the same language

---

6️⃣ Chomsky Normal Form (CNF)

Definition

A CFG is in Chomsky Normal Form if all productions are of the form:

• A → BC

• A → a

Where:

• A, B, C ∈ V

• a ∈ Σ

---

Special Rule

S → ε allowed if ε ∈ L

---

Steps to Convert CFG to CNF

1. Remove ε-productions

2. Remove unit productions

3. Remove useless symbols

4. Convert long RHS into binary form

5. Replace terminals in long productions

---

Importance

• Used in parsing algorithms

• Asked as long conversion question

---

7️⃣ Greibach Normal Form (GNF)

Definition

A CFG is in Greibach Normal Form if every production is of the form:

A → aα

Where:

• a ∈ Σ

• α ∈ V*

---

Characteristics

• Right-hand side starts with a terminal

• No left recursion

---

Importance

• Useful in top-down parsing

• Ensures derivations consume input symbols

---

8️⃣ Decision Algorithms for CFG

Decidable Problems

1. Membership problem
   Given string w, determine whether w ∈ L(G)

2. Emptiness problem
   Determine whether L(G) = ∅

3. Finiteness problem
   Check if L(G) is finite

---

Undecidable Problem

• Equivalence of two CFGs

---

🔑 CFG vs Regular Grammar

CFG	Regular Grammar
More powerful	Less powerful
PDA required	FA sufficient
Supports recursion	No recursion

📘 PAPER 1: THEORY OF COMPUTATION (MCA546)🔴 UNIT 2: Finite Automata (university of allahabad)

🔴 UNIT 2: Finite Automata

(VERY HIGH EXAM WEIGHT – Definitions + Diagrams + Theorems)

---

1️⃣ Finite Automata (FA)

A Finite Automaton is a mathematical model of computation used to recognize regular languages.

Formal Definition

A finite automaton is a 5-tuple:

M = (Q, Σ, δ, q₀, F)

Where:

• Q → Finite set of states

• Σ → Input alphabet

• δ → Transition function

• q₀ → Initial state

• F → Set of final (accepting) states

---

2️⃣ Deterministic Finite Automata (DFA)

Definition

A DFA is a finite automaton in which:

• For each state and input symbol, there is exactly one transition

• No ε-moves allowed

Transition Function

δ : Q × Σ → Q

---

Example

Language: Strings ending with 01

States:

• q₀ → start

• q₁ → last symbol was 0

• q₂ → accept (01 found)

---

Key Properties

• Simple and predictable

• Easy to implement

• Always deterministic

---

3️⃣ Non-Deterministic Finite Automata (NFA)

Definition

An NFA allows:

• Multiple transitions for the same input

• ε-transitions (move without input)

Transition Function

δ : Q × (Σ ∪ {ε}) → 2^Q

---

Important Fact

➡ Every NFA has an equivalent DFA

(This is a very common exam question)

---

Difference: DFA vs NFA

DFA	NFA
One transition per symbol	Multiple transitions
No ε-moves	ε-moves allowed
Faster execution	Easier to design
Harder to design	Simple construction

---

4️⃣ ε-Moves (Moves on Empty String)

An ε-move allows the automaton to:

• Change state without reading any input

Why Needed

• Simplifies automaton design

• Useful in regular expression to NFA conversion

---

5️⃣ Regular Expressions

Definition

A Regular Expression (RE) describes regular languages using symbols and operators.

Operators

• Union: |

• Concatenation: .

• Closure (Kleene star): *

---

Examples

• (0|1)* → All binary strings

• 0*1* → Any number of 0s followed by 1s

---

Equivalence

➡ Regular Expression ⇔ Finite Automaton

---

6️⃣ Regular Sets (Regular Languages)

A language is called regular if:

• It can be represented by a DFA

• Or an NFA

• Or a Regular Expression

---

Examples

• Set of strings with even number of 0s

• Strings ending with 1

---

7️⃣ Relationship with Regular Grammars

Regular Grammar

A grammar is regular if its production rules are of the form:

• A → aB

• A → a

---

Important Relationship

• Every regular grammar generates a regular language

• Every regular language has a regular grammar

---

8️⃣ Pumping Lemma for Regular Sets

Purpose

Used to prove that a language is NOT regular

---

Statement

If L is a regular language, then ∃ a constant p such that any string w ∈ L with |w| ≥ p can be split into:

w = xyz

Such that:

1. |y| > 0

2. |xy| ≤ p

3. xyⁱz ∈ L for all i ≥ 0

---

Usage

• Assume language is regular

• Apply pumping lemma

• Reach contradiction

• Conclude: Language is not regular

---

Common Example

L = {0ⁿ1ⁿ | n ≥ 1} → NOT regular

---

9️⃣ Closure Properties of Regular Sets

Regular languages are closed under:

• Union

• Intersection

• Complement

• Difference

• Concatenation

• Kleene star

• Reversal

---

Meaning

If L₁ and L₂ are regular, then:

• L₁ ∪ L₂ is regular

• L₁ ∩ L₂ is regular

➡ Frequently asked in short notes

---

🔟 Decision Algorithms for Regular Sets

Problems That Are Decidable

• Emptiness problem

• Membership problem

• Equivalence of DFA

• Finiteness of language

---

Meaning

There exists an algorithm that always terminates and gives correct answer.

---

1️⃣1️⃣ Minimization of Finite Automata

Goal

Reduce the number of states without changing the language

---

Steps

1. Remove unreachable states

2. Identify equivalent states

3. Merge equivalent states

---

Why Important

• Reduces memory

• Improves efficiency

• Asked as long question

📘 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