1. **Problem Statement:** Convert the given Non-Deterministic Finite Automata (NFA) into equivalent Deterministic Finite Automata (DFA). 2. **Key Concepts:** - An NFA can have multiple transitions for the same input from a state, including epsilon ($\varepsilon$) transitions. - A DFA has exactly one transition for each input symbol from every state. - The subset construction method is used to convert an NFA to a DFA by creating states in the DFA that represent sets of NFA states. 3. **Step-by-step Conversion for Graph 1:** - States: 1, 2 - Alphabet: {a, b} - Transitions: - From 1: on 'a' to 1 (self-loop), on 'a' or 'b' to 2 - From 2: on 'b' to 1 - Start with initial DFA state representing {1}. - From {1} on 'a': NFA goes to {1, 2} (since 1 loops on 'a' and 1 to 2 on 'a'). - From {1} on 'b': NFA goes to {2} (from 1 to 2 on 'b'). - From {1, 2} on 'a': from 1 on 'a' to {1, 2}, from 2 no 'a' transition, so result {1, 2}. - From {1, 2} on 'b': from 1 on 'b' to {2}, from 2 on 'b' to {1}, so combined {1, 2}. - From {2} on 'a': no transition, so empty set. - From {2} on 'b': to {1}. 4. **Step-by-step Conversion for Graph 2:** - States: q1, q2, q3 - Alphabet: {a, b} - Transitions: - q1 to q2 on $\varepsilon$ - q2 to q1 on 'a' - q1 to q3 on 'a' - q3 to q2 on 'a' or 'b' - q3 self-loop on 'b' - First, compute $\varepsilon$-closure: - $\varepsilon$-closure(q1) = {q1, q2} - $\varepsilon$-closure(q2) = {q2} - $\varepsilon$-closure(q3) = {q3} - Start DFA state: {q1, q2} - From {q1, q2} on 'a': - q1 on 'a' to q3 - q2 on 'a' to q1 - $\varepsilon$-closure(q3) = {q3} - $\varepsilon$-closure(q1) = {q1, q2} - Combined: {q1, q2, q3} - From {q1, q2} on 'b': - q1 no 'b' transition - q2 no 'b' transition - Result: empty set - From {q1, q2, q3} on 'a': - q1 on 'a' to q3 - q2 on 'a' to q1 - q3 on 'a' to q2 - $\varepsilon$-closures combined: {q1, q2, q3} - From {q1, q2, q3} on 'b': - q3 on 'b' to q3 - $\varepsilon$-closure(q3) = {q3} - Result: {q3} - From {q3} on 'a': to {q2} after $\varepsilon$-closure - From {q3} on 'b': to {q3} - From {q2} on 'a': to {q1, q2} - From {q2} on 'b': empty set 5. **Summary:** - The DFA states are sets of NFA states. - Transitions are defined by moving on input symbols and taking $\varepsilon$-closures. - The empty set represents no transitions. This completes the conversion of the given NFAs to equivalent DFAs.