02
Finite Automata and Regular Languages
Chapter 2 • Intermediate
80 min
Finite Automata and Regular Languages
Finite Automata recognize regular languages.
DFA (Deterministic Finite Automaton)
DFA is a 5-tuple: M = (Q, Σ, δ, q₀, F)
- Q: Finite set of states
- Σ: Alphabet
- δ: Transition function (Q × Σ → Q)
- q₀: Start state
- F: Set of accepting states
Properties:
- Exactly one transition per symbol
- Deterministic
Example:
DFA accepting strings ending with '1':
- States: {q₀, q₁}
- Start: q₀
- Accept: {q₁}
- Transitions: δ(q₀, 0) = q₀, δ(q₀, 1) = q₁, δ(q₁, 0) = q₀, δ(q₁, 1) = q₁
NFA (Nondeterministic Finite Automaton)
NFA is a 5-tuple: M = (Q, Σ, δ, q₀, F)
- Q: Finite set of states
- Σ: Alphabet
- δ: Transition function (Q × (Σ ∪ {ε}) → 2^Q)
- q₀: Start state
- F: Set of accepting states
Properties:
- Multiple transitions possible
- ε-transitions allowed
- Nondeterministic
NFA to DFA Conversion:
- Use subset construction
- States are subsets of NFA states
- Exponential blowup possible
ε-NFA
ε-NFA allows ε-transitions.
ε-Closure: Set of states reachable via ε-transitions.
Conversion:
- ε-NFA → NFA (remove ε-transitions)
- NFA → DFA (subset construction)
Regular Expressions
Regular Expression describes regular languages.
Operations:
- Union (| or +): L₁ ∪ L₂
- Concatenation (·): L₁ · L₂
- **Kleene Star (*):** L*
Examples:
- (0|1)*: All binary strings
- 01: Strings with 0s followed by 1s
- (0|1)00(0|1): Strings containing "00"
Regular Grammar
Regular Grammar generates regular languages.
Right Linear Grammar:
- A → aB or A → a
- Non-terminal on right
Left Linear Grammar:
- A → Ba or A → a
- Non-terminal on left
Equivalence
DFA ≡ NFA ≡ ε-NFA ≡ Regular Expression ≡ Regular Grammar
All recognize/generate regular languages.
Pumping Lemma for Regular Languages
Pumping Lemma: If L is regular, then:
- ∃ n such that ∀ w ∈ L with |w| ≥ n
- w = xyz where:
- |xy| ≤ n
- |y| > 0
- xyⁱz ∈ L for all i ≥ 0
Use: Prove language is NOT regular.
Example: L = {0ⁿ1ⁿ | n ≥ 0} is not regular.
Closure Properties
Regular languages are closed under:
- Union
- Intersection
- Complement
- Concatenation
- Kleene star
- Reversal
- Homomorphism
GATE CS Important Points
- DFA/NFA: Construction and conversion
- Regular Expressions: Write and convert
- Pumping Lemma: Prove non-regularity
- Closure Properties: Know all properties
- Minimization: Minimize DFA
Practice Tips
- Construct DFA: Practice for various languages
- NFA to DFA: Practice conversion
- Regular Expressions: Write for given languages
- Pumping Lemma: Practice proofs
- Previous Year Questions: Solve GATE FA questions