1.

Define DFA and Explain its Components with an

Example
2. Definition
A Deterministic Finite Automaton (DFA) is a mathematical
model used to recognize patterns and regular languages.
A DFA is represented by a 5-tuple:
𝑀 = (𝑄, Σ, 𝛿, 𝑞0 , 𝐹)
Components of DFA
Symbol Meaning

𝑄 Finite set of states

Σ Input alphabet

𝛿 Transition function

𝑞0 Initial state

𝐹 Set of final/accepting states

Example
Construct a DFA over {0, 1}that accepts strings ending in 1.
States
 𝑞0 : Start state
 𝑞1 : Accept state
Transition Table
Current State Input 0 Input 1

𝑞0 𝑞0 𝑞1
𝑞1 𝑞0 𝑞1
Explanation
 If the last symbol is 1, the DFA reaches 𝑞1 .
 Therefore, all strings ending in 1 are accepted.
2. Convert an NFA with ε-moves into DFA
Steps for Conversion
1. Find ε-closure of all states.
2. Take ε-closure of start state as DFA start state.
3. Compute transitions for each input symbol.
4. Repeat until no new states are formed.
Example
NFA
States: {𝐴, 𝐵}
Alphabet: {0, 1}
Transitions:
𝜀
 𝐴→𝐵
0
 𝐵→𝐵
1
 𝐵→𝐴
Step 1: ε-closure
𝜀-closure(𝐴) = {𝐴, 𝐵}
𝜀-closure(𝐵) = {𝐵}

Step 2: DFA States

Start state:
{ 𝐴, 𝐵 }

Step 3: Transitions
DFA State Input 0 Input 1
{𝐴 , 𝐵 } {𝐵} {𝐴, 𝐵 }
{𝐵} {𝐵} {𝐴, 𝐵 }

Thus the equivalent DFA is obtained.

3. Explain Regular Expressions with Examples
Definition
A Regular Expression (RE) is a notation used to describe
regular languages.

Basic Operations
Symbol Meaning

+or ( )
Symbol Meaning

Concatenation Sequence

∗ Kleene Star
Examples
Example 1
(0 + 1)∗

Represents all binary strings.

Example 2
1(0 + 1)∗

Represents all binary strings starting with 1.

Example 3
(𝑎𝑏)∗

Represents:
{𝜀 , 𝑎𝑏, 𝑎𝑏𝑎𝑏, 𝑎𝑏𝑎𝑏𝑎𝑏 , . . . }
4. Prove Closure Properties of Regular Languages
Statement
Regular languages are closed under:
 Union
  Intersection
 Complement
 Concatenation
 Kleene Star
Closure under Union
Suppose:
 𝐿1 recognized by DFA 𝑀1
 𝐿2 recognized by DFA 𝑀2
Construct a product automaton:
𝑀 = (𝑄1 × 𝑄2 , Σ, 𝛿, (𝑞1 , 𝑞2 ), 𝐹)

where:
𝐹 = {(𝑝, 𝑞) ∣ 𝑝 ∈ 𝐹1 or 𝑞 ∈ 𝐹2 }
Hence 𝐿1 ∪ 𝐿2 is regular.
Closure under Complement
Swap final and non-final states in DFA.
Thus complement is also regular.
Closure under Concatenation and Star
Using NFA constructions:
 Connect final states using ε-transitions.
 Add loops for star operation.
Therefore regular languages remain regular.
5. State and Explain Pumping Lemma for Regular Languages
Statement
If 𝐿is regular, then there exists a pumping length 𝑝such that
every string 𝑤in 𝐿with:
∣ 𝑤 ∣≥ 𝑝
can be written as:
𝑤 = 𝑥𝑦𝑧
satisfying:
1. ∣ 𝑥𝑦 ∣≤ 𝑝
2. ∣ 𝑦 ∣> 0
𝑥𝑦 𝑖 𝑧 ∈ 𝐿∀𝑖 ≥ 0
Use
3. It is mainly used to prove a language is not regular.
Example
Show:
𝐿 = {0𝑛 1𝑛 ∣ 𝑛 ≥ 0}

is not regular.
Assume 𝐿is regular.
Take:
𝑤 = 0𝑝 1𝑝
According to pumping lemma:
𝑤 = 𝑥𝑦𝑧

where 𝑦contains only 0’s.

Pump 𝑦twice:
𝑥𝑦 2 𝑧

Now number of 0’s exceeds number of 1’s.

Hence:
𝑥𝑦 2 𝑧 ∉ 𝐿
Contradiction.
Therefore 𝐿is not regular.
6. Explain Ambiguity in CFG with Examples
Definition
A CFG is ambiguous if at least one string has:
 More than one parse tree
 More than one leftmost derivation
Example
Grammar:𝐸 → 𝐸 + 𝐸 ∣ 𝐸 ∗ 𝐸 ∣ 𝑖𝑑

String:𝑖𝑑 + 𝑖𝑑 ∗ 𝑖𝑑
can be parsed as:
 1. (𝑖𝑑 + 𝑖𝑑) ∗ 𝑖𝑑
2. 𝑖𝑑 + (𝑖𝑑 ∗ 𝑖𝑑)

Thus grammar is ambiguous.

Removing Ambiguity
Use precedence rules:
𝐸 →𝐸+𝑇 ∣𝑇
𝑇 →𝑇∗𝐹 ∣𝐹
𝐹 → 𝑖𝑑

Now multiplication has higher precedence.

7. Convert CFG into Chomsky Normal Form (CNF)
CNF Rules
Every production must be of the form:
𝐴 → 𝐵𝐶or𝐴 → 𝑎
where:
 𝐴, 𝐵, 𝐶are variables
 𝑎is terminal
Steps
1. Remove ε-productions
2. Remove unit productions
3. Remove useless symbols
 4. Replace long productions
Example
Given:
𝑆 → 𝑎𝐴𝐵
𝐴→𝑎
𝐵→𝑏
Introduce new variable:
𝑋→𝑎
Then:
𝑆 → 𝑋𝐶
𝐶 → 𝐴𝐵

Now grammar is in CNF.

8. Define PDA and Explain its Acceptance Methods
Definition
A Pushdown Automaton (PDA) is a finite automaton with
stack memory.
A PDA is represented as:
(𝑄 , Σ, Γ, 𝛿 , 𝑞0 , 𝑍0 , 𝐹 )
Components
Symbol Meaning

𝑄 States

Σ Input alphabet

Γ Stack alphabet
Acceptance Methods
𝑞0 Start state
1. Acceptance by Final State
𝑍0 Initial stack symbol
Input accepted if PDA reaches a
𝐹 Final states final state after consuming
input.
2. Acceptance by Empty Stack
Input accepted if stack becomes empty after processing
input.
Equivalence
Both methods accept the same class of languages:
Context-Free Languages (CFLs).
UNIT 1: Finite Automata
 DFA (Deterministic Finite Automata): A DFA is a 5-
tuple (Q, Σ, δ, q0, F). Each input symbol leads to
exactly one next state. Used for pattern matching
and lexical analysis.
 NFA (Non-Deterministic Finite Automata): An NFA
may have multiple transitions for the same symbol.
Every NFA has an equivalent DFA.
 NFA with ε-moves: Transitions can occur without
consuming input symbols. ε-closure is used for
conversion to DFA.
 Equivalence of DFA and NFA: Subset construction
method converts NFA into DFA.
 Minimization of DFA: Equivalent states are merged
to reduce the number of states.
UNIT 2: Regular Languages and Regular Grammar
 Languages and Grammar: A language is a set of
strings over an alphabet. Grammar generates strings
of a language.
 Regular Expressions: Symbols used to represent
regular languages. Operators include union (+),
concatenation, and Kleene star (*).
 Regular Languages: Languages accepted by finite
automata.
 Regular Grammar: Grammar where productions are
either right-linear or left-linear.
 Right and Left Linear Grammars: Right-linear: A →
aB or A → a. Left-linear: A → Ba or A → a.
 Equivalence: Regular expressions, regular grammars,
and finite automata are equivalent in expressive
power.
UNIT 3: Properties of Regular Languages
 Closure Properties: Regular languages are closed
under union, intersection, complement,
concatenation, and star operation.
 Decision Algorithms: Algorithms exist to determine
emptiness, finiteness, infiniteness, and equality.
 Pigeonhole Principle: Used to prove non-regularity
by showing repetition in finite states.
 Pumping Lemma for Regular Languages: If a
language is regular, long strings can be divided into
xyz satisfying pumping conditions.