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

  1. DFA/NFA: Construction and conversion
  2. Regular Expressions: Write and convert
  3. Pumping Lemma: Prove non-regularity
  4. Closure Properties: Know all properties
  5. Minimization: Minimize DFA

Practice Tips

  1. Construct DFA: Practice for various languages
  2. NFA to DFA: Practice conversion
  3. Regular Expressions: Write for given languages
  4. Pumping Lemma: Practice proofs
  5. Previous Year Questions: Solve GATE FA questions