UNIT – III - Finite Automata

Part 1 Link : https://deepanotes.blogspot.com/2022/05/linked-list-representations-of-employee.html

TOPIC 5 Conversion of NFA to DFA

5.1 Definition

The conversion of an NFA into a DFA is done by the Subset Construction (Powerset Construction) Method. Each state of the DFA represents a set of states of the NFA.

Every NFA can be converted into an equivalent DFA that accepts the same language.

5.2 Steps for Conversion

Step	Action
1	Initialize: let Q′ be the set of DFA states and T′ its transition table; both start empty.
2	Add the initial state of the NFA to Q′. If ε-transitions exist, use the ε-closure of the initial state.
3	For the initial DFA state, find the transitions for every input symbol. If several NFA states are reachable, combine them into one DFA state.
4	Each newly obtained set of NFA states becomes a new DFA state (if not already present).
5	Record the transitions of every new DFA state for every input symbol.
6	Repeat until no new states are generated.
7	Mark every DFA state containing at least one NFA final state as a final state.
8	Complete the DFA: include the empty-set state ∅ where required.
9	Draw the state diagram: nodes = DFA states, edges = transitions.
10	Verify that the DFA accepts exactly the language of the NFA.

Formula: δ′(S, a) = ⋃_{q ∈ S} δ(q, a) for every subset S ⊆ Q and every a ∈ Σ. Final states of the DFA: F′ = { S | S ∩ F ≠ ∅ }.

5.3 Worked Example

Problem: Convert the NFA below (accepting strings over {0,1} that end with 01) into an equivalent DFA.

Fig. 3 NFA with Q = {q₀, q₁, q₂}, initial state q₀, F = {q₂}

Step 1: NFA transition table

Present State	Input 0	Input 1
→ q₀	{q₀, q₁}	{q₀}
q₁	∅	{q₂}
* q₂	∅	∅

Step 2: Subset construction

DFA State	NFA Subset	On 0	On 1
→ A	{q₀}	{q₀, q₁} = B	{q₀} = A
B	{q₀, q₁}	{q₀, q₁} = B	{q₀, q₂} = C
* C	{q₀, q₂}	{q₀, q₁} = B	{q₀} = A

Check for B on 1: δ(q₀,1) ∪ δ(q₁,1) = {q₀} ∪ {q₂} = {q₀, q₂}. C is final because it contains q₂.

Note: Although 2³ = 8 subsets are possible, only 3 are reachable from the start state — only reachable subsets are written.

Step 3: Resulting DFA

Fig. 4 Equivalent DFA (A = {q₀}, B = {q₀,q₁}, C = {q₀,q₂})

TOPIC 6 Minimization of DFA

6.1 Introduction

DFA minimization reduces the number of states of a DFA without changing the language it accepts. The minimized DFA is equivalent to the original and has the minimum possible number of states. The aim is to merge equivalent states and remove unreachable states.

6.2 Steps for Minimization (Table-Filling Method)

Step	Action
1	Construct the transition table of the given DFA.
2	Remove unreachable states (states that cannot be reached from the initial state).
3	Divide the states into two groups: final states and non-final states.
4	Construct the state-pair table listing all pairs of distinct states.
5	Mark every pair in which one state is final and the other is non-final.
6	For each unmarked pair, examine the transitions of both states for every input symbol.
7	If the transitions lead to an already marked pair, mark the original pair as distinguishable.
8	Repeat until no further pairs can be marked.
9	Unmarked pairs are equivalent states — merge them into single states.
10	Build the minimized transition table and diagram, preserving the initial state and final-state conditions.

6.3 Worked Example

Problem: Minimize the DFA over Σ = {a, b} shown below (F = {q₃, q₄}).

Fig. 5 Original DFA (q₅ is unreachable)

Step 1: Transition table

Present State	Input a	Input b
→ q₀	q₁	q₂
q₁	q₃	q₄
q₂	q₃	q₄
* q₃	q₃	q₄
* q₄	q₃	q₄
q₅	q₃	q₀

Step 2: Remove unreachable states

Starting from q₀, the reachable states are q₀, q₁, q₂, q₃, q₄. State q₅ cannot be reached, so it is deleted.

Step 3: State-pair table (number = round in which the pair is marked)

	q₀	q₁	q₂	q₃
q₁	2
q₂	2	≡
q₃	1	1	1
q₄	1	1	1	≡

● Round 1: pairs with one final and one non-final state are marked — (q₀,q₃), (q₀,q₄), (q₁,q₃), (q₁,q₄), (q₂,q₃), (q₂,q₄).

● Round 2: (q₀,q₁) and (q₀,q₂) go to (q₁,q₃) on a, which is already marked, so they are marked.

● Pair (q₁,q₂): on a → (q₃,q₃), on b → (q₄,q₄) — identical, so it stays unmarked. Pair (q₃,q₄): same reasoning — unmarked.

● Round 3: no new pair can be marked. Stop.

Equivalent states: q₁ ≡ q₂ and q₃ ≡ q₄

Step 4: Minimized DFA

Present State	Input a	Input b
→ {q₀}	{q₁, q₂}	{q₁, q₂}
{q₁, q₂}	{q₃, q₄}	{q₃, q₄}
* {q₃, q₄}	{q₃, q₄}	{q₃, q₄}

Fig. 6 Minimized DFA — 3 states (accepts all strings of length ≥ 2)

TOPIC 7 Regular Expression

7.1 Definition

A Regular Expression (RE) is a mathematical notation used to represent a set of strings over a given alphabet. It describes patterns used to identify, search, and validate strings. Regular expressions are widely used in automata theory, compiler design, text searching, and input validation.

7.2 Basic Operations (Σ = {a, b})

Operation	Symbol	Meaning	Example
Union	+ or \|	Either one pattern or another	a + b
Concatenation	Writing symbols together	One symbol followed by another	ab
Kleene star	*	Zero or more repetitions	a^*
Positive closure	+ (superscript)	One or more repetitions	a⁺
Epsilon	ε	Empty string	ε
Empty set	∅	No strings	∅

7.3 Examples of Regular Expressions

No.	Regular Expression	Meaning	Language L
1	a + b	Either a or b	{a, b}
2	ab	a followed by b	{ab}
3	a^*	Zero or more a’s	{ε, a, aa, aaa, …}
4	a⁺	One or more a’s	{a, aa, aaa, …}
5	(a + b)^*	All strings over {a, b}, including ε	{ε, a, b, ab, ba, aa, bb, aba, …}
6	a^*b	Zero or more a’s followed by exactly one b	{b, ab, aab, aaab, …}
7	ab^*	One a followed by zero or more b’s	{a, ab, abb, abbb, …}
8	(ab)^*	Zero or more repetitions of ab	{ε, ab, abab, ababab, …}

7.4 Common Patterns over Σ = {0, 1}

Language	Regular Expression
Strings ending with 1	(0 + 1)^*1
Strings starting with 0	0(0 + 1)^*
Strings containing 01 as a substring	(0 + 1)^01(0 + 1)^
Strings of even length	((0 + 1)(0 + 1))^*

7.5 Important Rules (Identities)

For regular expressions R, S, and T:

No.	Law	Rule
1	Union is commutative	R + S = S + R
2	Union is associative	(R + S) + T = R + (S + T)
3	Concatenation is associative	(RS)T = R(ST)
4	Distributive law	R(S + T) = RS + RT
5	Kleene star	R^* = ε + RR^*
6	Identity for concatenation	Rε = εR = R
7	Identity for union	R + ∅ = R
8	Annihilator	R∅ = ∅R = ∅
9	Idempotent law	R + R = R
10	Star of star	(R^)^ = R^*

Extra rules (rows 7–10) are standard identities added to the original notes for completeness.

7.6 Applications

● Searching for patterns in text; find and replace

● Validating email addresses and phone numbers

● Lexical analysis in compiler design

● Recognizing regular languages and constructing finite automata

TOPIC 8 Pumping Lemma for Regular Languages

8.1 Introduction

The Pumping Lemma is an important theorem used to prove that a language is not regular. It states that every sufficiently long string in a regular language can be divided into three parts, so that the middle part can be repeated any number of times and the resulting string still belongs to the language.

8.2 Statement

If L is a regular language, then there exists a positive integer p (the pumping length) such that every string w ∈ L with |w| ≥ p can be written as

w = xyz

satisfying all three conditions:

No.	Condition	Notation	Explanation
1	Length condition	\|xy\| ≤ p	The first two parts together cannot exceed the pumping length
2	Non-empty condition	\|y\| > 0	The middle part contains at least one symbol
3	Pumping condition	xyⁱz ∈ L for all i ≥ 0	Repeating or removing the middle part still gives a string in L

Value of i	Resulting String	Effect
i = 0	xz	Middle part removed
i = 1	xyz = w	Original string
i = 2	xyyz	Middle part repeated once

8.3 Example — Prove that L = {aⁿbⁿ | n ≥ 0} is not regular

Step 1: Assume L is regular

By the Pumping Lemma, there exists a pumping length p.

Step 2: Choose a string

w = a^pb^p

Clearly w ∈ L and |w| = 2p ≥ p.

Step 3: Divide the string

Let w = xyz satisfy the conditions. Since |xy| ≤ p, both x and y consist only of a’s. Since |y| > 0, let y = a^k where k ≥ 1.

Step 4: Pump the string

Choose i = 0, which removes y:

xz = a^p−kb^p

The number of a’s (p − k) is now different from the number of b’s (p). Therefore xz ∉ L.

Step 5: Conclusion

This contradicts the condition xyⁱz ∈ L for every i ≥ 0. Hence:

L = {aⁿbⁿ | n ≥ 0} is not regular

8.4 Steps to Apply the Pumping Lemma

1. Assume that the given language is regular.

2. Let p be its pumping length.

3. Choose a string w ∈ L such that |w| ≥ p.

4. Divide w into xyz satisfying all three conditions.

5. Use the length conditions to determine the possible form of y.

6. Choose a suitable value of i, usually 0 or 2.

7. Show that xyⁱz ∉ L, producing a contradiction.

8. Conclude that the language is not regular.

8.5 Important Points to Remember

● The Pumping Lemma is used mainly to prove that a language is NOT regular.

● Every regular language satisfies the lemma, but satisfying the lemma alone does not prove a language is regular.

● The pumping length p is a positive integer; |y| > 0 ensures the middle part is non-empty.

TOPIC 9 Myhill–Nerode Theorem

9.1 Introduction

The Myhill–Nerode Theorem is used to decide whether a language is regular and to find the minimum number of states in a DFA. It gives a necessary and sufficient condition for a language to be regular.

9.2 Equivalence Relation

Let L be a language over Σ. Two strings x and y are equivalent with respect to L if, for every string z ∈ Σ^*:

xz ∈ L ⇔ yz ∈ L

This is written x ≡_L y. In simple terms, appending any string z to both strings either makes both belong to L or makes both fall outside L. If some string z distinguishes them, the strings are inequivalent.

9.3 Statement of the Theorem

L is regular ⇔ ≡_L has a finite number of equivalence classes

The number of equivalence classes equals the number of states in the minimal DFA for L.

9.4 Worked Examples

Example 1: L = strings over {0,1} ending with 1 (regular)

Class	Strings	Reason
[ε]	ε, 0, 10, 100, …	Strings not ending in 1 — accepted after appending z only if z itself ends in 1
[1]	1, 01, 11, 101, …	Strings ending in 1 — accepted with z = ε, and after any z ending in 1

There are 2 equivalence classes (finite), so L is regular and its minimal DFA has 2 states (see Fig. 1).

Example 2: L = {aⁿbⁿ | n ≥ 0} (not regular)

Take the strings aⁱ and a^j with i ≠ j. Choose the suffix z = bⁱ. Then aⁱbⁱ ∈ L but a^jbⁱ ∉ L. So aⁱ and a^j are inequivalent for every i ≠ j.

Infinitely many equivalence classes ⇒ L is not regular

9.5 Applications

● Proving that a language is regular or non-regular

● Finding the minimum number of states in a DFA

● Identifying equivalent states during DFA minimization

● Studying the properties of regular languages

9.6 Pumping Lemma vs Myhill–Nerode Theorem

Pumping Lemma	Myhill–Nerode Theorem
Mainly used to prove that a language is not regular	Used to determine regularity and minimal DFA size
Based on dividing a long string into parts (xyz)	Based on distinguishing strings using suffixes (z)
A necessary condition for regularity	A necessary and sufficient condition for regularity

Master Recap — Unit III

#	Topic	Key Idea to Remember
1	Finite Automata	Finite states + transitions; recognizes regular languages
2	DFA	M = (Q, Σ, δ, q₀, F), δ : Q × Σ → Q (exactly one next state)
3	NDFA	δ : Q × Σ → 2^Q (a set of next states); accept if some path ends in F
4	DFA vs NDFA	Same power; DFA = one next state, NDFA = set of next states
5	NFA → DFA	Subset construction; DFA state = set of NFA states; ≤ 2ⁿ states
6	DFA Minimization	Remove unreachable states, mark distinguishable pairs, merge unmarked pairs
7	Regular Expression	Union (+), concatenation, star (*); describes exactly the regular languages
8	Pumping Lemma	w = xyz, \|xy\| ≤ p, \|y\| > 0, xyⁱz ∈ L — used to prove NON-regularity
9	Myhill–Nerode	L regular ⇔ finitely many classes of ≡_L; classes = states of minimal DFA

Search This Blog

Deepa PhD CS