Unit II: Regular Expressions
Unit II: Regular Expressions and Regular Languages
Complete Exam Preparation Notes with Examples & Proof Ideas
1. Regular Expressions (RE)
A Regular Expression over alphabet Σ is built using:
- ∅ (empty set), ε (empty string), and each a ∈ Σ
- If r₁ and r₂ are RE → then (r₁ + r₂), (r₁ · r₂), (r₁)* are RE
Common Notation & Examples
| Expression | Meaning | Language Denoted |
|---|---|---|
| a | single symbol | {a} |
| a + b | union | {a, b} |
| ab | concatenation | {ab} |
| a* | zero or more a's | {ε, a, aa, aaa, …} |
| (a + b)* | all strings over {a,b} | Σ* |
| a(a + b)* | strings starting with a | all strings that begin with a |
| (a + b)*a | strings ending with a | all strings that end with a |
| (a + b)*abb | strings ending with abb | very common exam question |
Identities (Must Remember)
- ∅* = ε
- ε* = ε
- r + r = r
- r · ε = ε · r = r
- r + ∅ = ∅ + r = r
2. Kleene’s Theorem (Most Important Theorem in Unit II)
Kleene’s Theorem: A language is regular ⇔ it is accepted by a Finite Automaton ⇔ it can be represented by a Regular Expression.
Three Parts (All are frequently asked in exams)
| Part | Conversion | Method |
|---|---|---|
| Part 1 | DFA/NFA → Regular Expression | State Elimination / Arden’s Theorem / Transition Table Method |
| Part 2 | Regular Expression → NFA | Thompson’s Construction (easy) |
| Part 3 | NFA → DFA | Subset Construction (already in Unit I) |
3. Methods to Convert FA → Regular Expression
A. Arden’s Theorem (Very Important)
If equation is qᵢ = qᵢ a + qⱼ b + … + ε (i.e., a is only symbol looping on qᵢ)
Then solution is qᵢ = qⱼ b a* + … + ε a*
Then solution is qᵢ = qⱼ b a* + … + ε a*
Example using Arden’s Theorem
Consider DFA with equations:
q₁ = q₁0 + q₂1 + ε (start state)
q₂ = q₁1 + q₃0
q₃ = q₃1 (q₃ is final)
Solution:
From q₃ = q₃1 → q₃ = ε · 1* = 1* (apply Arden)
q₂ = q₁1 + q₃0 = q₁1 + 1*0
q₁ = q₁0 + q₂1 + ε = q₁0 + (q₁1 + 1*0)1 + ε
→ q₁ = q₁ (0 + 11 + 1*01) + ε
→ q₁ = ε (0 + 11 + 1*01)*
→ RE = (0 + 11 + 1*01)*
q₁ = q₁0 + q₂1 + ε (start state)
q₂ = q₁1 + q₃0
q₃ = q₃1 (q₃ is final)
Solution:
From q₃ = q₃1 → q₃ = ε · 1* = 1* (apply Arden)
q₂ = q₁1 + q₃0 = q₁1 + 1*0
q₁ = q₁0 + q₂1 + ε = q₁0 + (q₁1 + 1*0)1 + ε
→ q₁ = q₁ (0 + 11 + 1*01) + ε
→ q₁ = ε (0 + 11 + 1*01)*
→ RE = (0 + 11 + 1*01)*
B. State Elimination Method (Most used in exams)
Eliminate states one by one, update labels with union & concatenation.
4. Regular Languages – Closure Properties (Very Important)
| Operation | Closed? (Yes/No) | Construction |
|---|---|---|
| Union | Yes | NFA with ε-move from new start |
| Concatenation | Yes | Connect final of first to start of second via ε |
| Kleene Star | Yes | New start & final with ε-loops |
| Complement | Yes | Swap final & non-final states in DFA |
| Intersection | Yes | Product automaton (or De Morgan) |
| Difference | Yes | L₁ – L₂ = L₁ ∩ L₂ᶜ |
| Reverse | Yes | Reverse all arrows, swap start & final |
5. Non-Regular Languages – Pumping Lemma (Killer Topic)
Pumping Lemma for Regular Languages:
If L is regular, then ∃ p (pumping length) such that ∀ w ∈ L with |w| ≥ p,
w can be divided as w = xyz where:
1. |xy| ≤ p
2. |y| ≥ 1
3. ∀ k ≥ 0, xyᵏz ∈ L
If L is regular, then ∃ p (pumping length) such that ∀ w ∈ L with |w| ≥ p,
w can be divided as w = xyz where:
1. |xy| ≤ p
2. |y| ≥ 1
3. ∀ k ≥ 0, xyᵏz ∈ L
How to Prove a Language is NOT Regular (Standard Contradiction Method)
- Assume L is regular → ∃ p
- Choose a string w ∈ L with |w| ≥ p (smart choice!)
- w = xyz with |xy| ≤ p, |y| ≥ 1
- Pump y (usually k=0 or k=2) → get xyᵏz ∉ L → contradiction
Classic Non-Regular Languages (Memorize)
| Language | Why Not Regular? | Choose w = |
|---|---|---|
| {0ⁿ1ⁿ | n ≥ 0} | Needs counting | 0ᵖ 1ᵖ |
| {ww | w ∈ {0,1}*} | Middle unknown | 0ᵖ 1 0ᵖ 1 |
| {0ⁿ | n is prime} | No pattern | Use different proof |
| Palindromes | Only over 2 symbols with center mark is regular | — |
6. Pigeonhole Principle in TOC
If n pigeons → m holes and n > m → at least one hole has >1 pigeon.
Used in:
- Proving existence of equivalent states in minimization
- Myhill-Nerode theorem proof
- Pumping lemma intuition
7. Decidability & Decision Properties of Regular Languages
| Problem | Decidable? (Yes/No) | How? |
|---|---|---|
| Is L(M) = ∅ ? | Yes | Check if any final state reachable |
| Is L(M) = Σ* ? | Yes | Minimize DFA → check all states accepting |
| Is w ∈ L(M) ? | Yes | Simulate DFA |
| Equivalence of two DFA? | Yes | Minimize both → check isomorphism or symmetric difference empty |
| Is L regular? | No (undecidable in general) | — |
8. Transition Graph (Generalized FA)
Like NFA but allows:
- Regular expressions on edges
- Multiple start/final states possible
Used as intermediate step in RE ↔ FA conversion.
Most Important Exam Questions – Unit II
- Convert DFA/NFA → Regular Expression (Arden’s or State Elimination)
- Construct NFA from given Regular Expression
- Prove given language is not regular using Pumping Lemma (0ⁿ1ⁿ, ww, etc.)
- Prove closure properties with construction
- Apply Arden’s theorem step-by-step on equations
- Given two regular expressions, prove they are equal using identities
- Minimize DFA and then find RE
- State and prove Kleene’s Theorem (only statement usually enough)
Quick Revision One-Liners
- Regular ↔ FA ↔ RE (Kleene)
- Pumping Lemma is for proving non-regularity only
- Arden’s works only when no ε-loop on the state being solved
- Regular languages closed under all Boolean operations
- Choose w wisely in Pumping Lemma (usually with p powers)
You are now 100% ready for Unit II Exam!
Practice 5 Pumping Lemma + 5 Arden’s + 3 Closure proofs → Full Marks Guaranteed!
Practice 5 Pumping Lemma + 5 Arden’s + 3 Closure proofs → Full Marks Guaranteed!