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

December 24, 2025

📘 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:

|y| > 0
|xy| ≤ p
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