Converting NFA to DFA

Overview

• Discussing conversion of NFA (Nondeterministic Finite Automaton) to DFA (Deterministic Finite Automaton).
• Equivalence of DFA and NFA.
• Aim: To calculate the equivalent DFA for the given NFA.

Example 1: Design DFA from Given NFA

Given NFA

• Initial state: q0
• Final state: q2 (represented with a circle)
• Alphabet: {0, 1}

Construct State Transition Table for NFA

• Transition Table for NFA:
  • q0 on 0: {q0, q1}
  • q0 on 1: {} (no transition, denoted as empty set)
  • q1 on 0: {} (no transition, denoted as empty set)
  • q1 on 1: {q1, q2}
  • q2 on 0: {q0}
  • q2 on 1: {} (no transition, denoted as empty set)

Construct DFA Transition Table

• Initial state: q0
• Alphabet: {0, 1}
• DFA Transition Table:
  • q0 on 0: {q0, q1}
  • q0 on 1: {} (denote as qd, dead state)
  • q0, q1 on 0: {q0, q1}
  • q0, q1 on 1: {q1, q2}
  • q1, q2 on 0: {q0}
  • q1, q2 on 1: {q1, q2}

Final State Identification

• Final States:
  • q0 (initial state and final state)
  • q0, q1 (contains q0)
  • q1, q2 (does not contain q0, not final)

Transition Details

• Use square brackets for states representation.
• Final states represented with double circles.
• Transition Table:
  • q0 on 0: {q0, q1}
  • q0 on 1: qd (dead state)
  • q0, q1 on 0: {q0, q1}
  • q0, q1 on 1: {q1, q2}
  • q1, q2 on 0: {q0}
  • q1, q2 on 1: {q1, q2}

Example 2: Another NFA to DFA Conversion

Given NFA

• Initial state: q0
• Final state: q2
• Alphabet: {a, b}

Construct State Transition Table for NFA

• Transition Table:
  • q0 on a: {q0, q1}
  • q0 on b: {q0}
  • q1 on a: {} (no transition)
  • q1 on b: {q2}
  • q2 on a: {q2}
  • q2 on b: {} (no transition)

Construct DFA Transition Table

• Initial state: q0
• Alphabet: {a, b}
• DFA Transition Table:
  • q0 on a: {q0, q1}
  • q0 on b: {q0}
  • q0, q1 on a: {q0, q1}
  • q0, q1 on b: {q2}
  • q0, q2 on a: {q0, q1}
  • q0, q2 on b: {q0}

Final State Identification

• Final States:
  • q2 (final state as it contains q2)
  • q0
  • q0, q1 (final state as it contains q0)

Transition Representation

• No need for dead state (qd) in this example.
• Self-loops and transitions are noted accordingly.

Conclusion

• In both examples, the method to convert NFA into DFA through the construction of transition tables was demonstrated.