Answer: False

Justification: By formal definition (Sipser Def 1.5, Linz Def 2.1), the transition function of a DFA is a total function mapped as:

This means that for every state $q \in Q$ and every alphabet symbol $a \in \Sigma$, there must exist exactly one defined transition to a state in $Q$. It cannot be undefined or map to the empty set. If a state has no “active” transitions for a symbol, we must explicitly transition to a designated “trap state” (or dead state) $q_{trap} \in Q$ where $\delta(q_{trap}, a) = q_{trap}$ for all $a \in \Sigma$. Mapping to $\emptyset$ is only permitted in Nondeterministic Finite Automata (NFAs), where the range of the transition function is the power set of states, $\mathcal{P}(Q)$, which includes $\emptyset$.

Answer: True

Justification: By definition, an $\varepsilon$-transition allows an NFA to change its state without consuming any input symbol (Sipser Chapter 1.2). For any state $q$, the path of length 0 (traveling along zero $\varepsilon$ arrows) starts at $q$ and ends at $q$. Therefore, $q$ is always reachable from itself via $\varepsilon$-transitions. Mathematically, for any set of states $R \subseteq Q$:

where $E(R) = \{q \in Q \mid q \text{ can be reached from some } r \in R \text{ by traveling along zero or more } \varepsilon \text{ transitions}\}$.

Answer: False

Justification: While the subset construction proof (Sipser Theorem 1.39) states that the power set of states $Q' = \mathcal{P}(Q)$ has a cardinality of $|Q'| = 2^k$, many of these states may be inaccessible (unreachable) from the start state $q_0'$. In practice, when building the DFA, we only construct states that are reachable from the start state. Unreachable states can be safely omitted from the final transition graph without altering the language recognized by the machine (Linz Chapter 2.3). Thus, the final simplified DFA often has significantly fewer than $2^k$ states.

Answer: False

Justification: The definition of indistinguishability is much stricter. Two states $p$ and $q$ are indistinguishable if and only if for every string $w \in \Sigma^*$, the transitions from $p$ and $q$ on $w$ both lead to accepting states or both lead to non-accepting states. Mathematically:

If there merely exists one string $w$ where both accept, they are not necessarily indistinguishable, because there could be another string $x$ where $\delta^*(p, x) \in F$ but $\delta^*(q, x) \notin F$, making them distinguishable.

Correct Options: A, B, C, D

Justification:

• A is correct: This is the base case of the inductive definition of the extended transition function (Sipser Chapter 1.1, Linz Chapter 2.1).
• B is correct: This is the standard right-recursive step defining how a string is processed by reading the last character $a$ after the prefix $w$.
• C is correct: This is the left-recursive equivalent, which is mathematically consistent. It processes the first character $a$ to reach a state $q' = \delta(q, a)$, and then processes the remaining string $w$ from $q'$.
• D is correct: This is the general state-transition theorem for concatenating any two strings $x$ and $y$. It states that processing $xy$ from state $q$ is equivalent to processing $y$ starting from the state reached after processing $x$.

Correct Options: A, B, C

Justification:

• A is correct: Since there are no outgoing $\varepsilon$-transitions from $q_1$, its $\varepsilon$-closure is only the state itself: $E(\{q_1\}) = \{q_1\}$.
• B is correct: There is an $\varepsilon$-transition from $q_2$ to $q_3$. Thus, $E(\{q_2\}) = \{q_2, q_3\}$.
• C is correct: Under input $1$ from state $q_1$, the NFA can transition to $\{q_1, q_2\}$. Taking the $\varepsilon$-closure of this set: $$\delta'(\{q_1\}, 1) = E(\delta(q_1, 1)) = E(\{q_1, q_2\}) = E(\{q_1\}) \cup E(\{q_2\}) = \{q_1\} \cup \{q_2, q_3\} = \{q_1, q_2, q_3\}$$ Thus, option C is correct.
• D is incorrect: Let’s calculate $\delta'(\{q_2, q_3\}, 0)$: $$\delta'(\{q_2, q_3\}, 0) = E(\delta(q_2, 0) \cup \delta(q_3, 0)) = E(\{q_3\} \cup \emptyset) = E(\{q_3\}) = \{q_3\}$$ Wait! Let’s double check if there are $\varepsilon$-transitions from $q_3$. No, $E(\{q_3\}) = \{q_3\}$. So $\delta'(\{q_2, q_3\}, 0) = \{q_3\}$ is indeed mathematically correct! Correction: Let’s re-verify option D. Yes, $E(\delta(q_2, 0)) = E(\{q_3\}) = \{q_3\}$, and $E(\delta(q_3, 0)) = E(\emptyset) = \emptyset$. Their union is $\{q_3\}$. So D is actually correct! Let’s make sure our options are distinct. All options A, B, C, D are correct.

1. Mathematical Framework

When reading a binary string from left to right, each newly read bit $b \in \{0, 1\}$ shifts the value of the existing prefix $v$ to the left by 1 bit (multiplying it by 2) and adds $b$. Mathematically, if the value of the string read so far is $x$, reading a new bit $b$ updates the value to:

Since we are interested in divisibility by 3, we work modulo 3. Let’s trace how the remainder $r = x \bmod 3$ changes:

• If $x \equiv 0 \pmod 3$:
  • New remainder on $0$: $(2(0) + 0) \bmod 3 = 0 \implies q_0$
  • New remainder on $1$: $(2(0) + 1) \bmod 3 = 1 \implies q_1$
• If $x \equiv 1 \pmod 3$:
  • New remainder on $0$: $(2(1) + 0) \bmod 3 = 2 \implies q_2$
  • New remainder on $1$: $(2(1) + 1) \bmod 3 = 3 \equiv 0 \implies q_0$
• If $x \equiv 2 \pmod 3$:
  • New remainder on $0$: $(2(2) + 0) \bmod 3 = 4 \equiv 1 \implies q_1$
  • New remainder on $1$: $(2(2) + 1) \bmod 3 = 5 \equiv 2 \implies q_2$

2. Formal 5-Tuple Description

The DFA is $M = (Q, \Sigma, \delta, q_0, F)$, where:

• $Q = \{q_0, q_1, q_2\}$ representing remainders 0, 1, and 2 respectively.
• $\Sigma = \{0, 1\}$
• $q_0$ is the start state (representing $0 \bmod 3 = 0$).
• $F = \{q_0\}$ (since we accept only when the remainder is 0).
• $\delta$ is defined by the transitions below.

3. Transition Table

4. State Diagram (TikZ Description)

\usetikzlibrary{automata, positioning}
\begin{tikzpicture}[shorten >=1pt, node distance=2.5cm, on grid, auto]
   \node[state, initial, accepting] (q0) {$q_0$};
   \node[state, right=of q0] (q1) {$q_1$};
   \node[state, right=of q1] (q2) {$q_2$};
   
   \path[->]
    (q0) edge [loop above] node {0} (q0)
         edge [bend left] node {1} (q1)
    (q1) edge [bend left] node {1} (q0)
         edge [bend left] node {0} (q2)
    (q2) edge [bend left] node {0} (q1)
         edge [loop above] node {1} (q2);
\end{tikzpicture}

Step 1: Find initial state and closures

First, we find the start state of the equivalent DFA $M'$, which is defined as $E(\{1\})$, the $\varepsilon$-closure of the NFA’s start state.

• $E(\{1\})$: We can reach state $3$ from state $1$ using the $\varepsilon$-transition. No other transitions exist. $$q_0' = E(\{1\}) = \{1, 3\}$$

Now let’s pre-compute the $\varepsilon$-closures for all individual states to make the process easier:

• $E(\{1\}) = \{1, 3\}$
• $E(\{2\}) = \{2\}$
• $E(\{3\}) = \{3\}$

Step 2: Iterative State and Transition Construction

We start with our initial DFA state $A = \{1, 3\}$ and compute transitions for each alphabet symbol $\{a, b\}$:

1. From State $A = \{1, 3\}$ on $a$:

   • $\delta(1, a) = \{2\}$
   • $\delta(3, a) = \{1\}$
   • Union: $\{1, 2\}$
   • Take $\varepsilon$-closure of union: $$E(\{1, 2\}) = E(\{1\}) \cup E(\{2\}) = \{1, 3\} \cup \{2\} = \{1, 2, 3\}$$
   • Let this new state be $B = \{1, 2, 3\}$.
   • Transition: $\delta'(A, a) = B$

2. From State $A = \{1, 3\}$ on $b$:

   • $\delta(1, b) = \emptyset$
   • $\delta(3, b) = \emptyset$
   • Union: $\emptyset$
   • Take $\varepsilon$-closure of union: $E(\emptyset) = \emptyset$ (Trap State)
   • Let this state be $T = \emptyset$.
   • Transition: $\delta'(A, b) = T$

Now we must explore transitions from our new state $B = \{1, 2, 3\}$:

3. From State $B = \{1, 2, 3\}$ on $a$:

   • $\delta(1, a) = \{2\}$
   • $\delta(2, a) = \{2\}$
   • $\delta(3, a) = \{1\}$
   • Union: $\{1, 2\}$
   • Take $\varepsilon$-closure of union: $$E(\{1, 2\}) = \{1, 2, 3\} = B$$
   • Transition: $\delta'(B, a) = B$

4. From State $B = \{1, 2, 3\}$ on $b$:

   • $\delta(1, b) = \emptyset$
   • $\delta(2, b) = \{3\}$
   • $\delta(3, b) = \emptyset$
   • Union: $\{3\}$
   • Take $\varepsilon$-closure of union: $$E(\{3\}) = \{3\}$$
   • Let this new state be $C = \{3\}$.
   • Transition: $\delta'(B, b) = C$

Now we must explore transitions from our new state $C = \{3\}$:

5. From State $C = \{3\}$ on $a$:

   • $\delta(3, a) = \{1\}$
   • Take $\varepsilon$-closure: $$E(\{1\}) = \{1, 3\} = A$$
   • Transition: $\delta'(C, a) = A$

6. From State $C = \{3\}$ on $b$:

   • $\delta(3, b) = \emptyset \implies T$
   • Transition: $\delta'(C, b) = T$

Finally, transitions from the Trap State $T = \emptyset$:

• $\delta'(T, a) = T$
• $\delta'(T, b) = T$

Step 3: Identify Accepting States

Any state in the DFA whose subset contains an accepting state of the NFA ($F_N = \{1\}$) becomes an accepting state in the DFA.

• Our states are:
  • $A = \{1, 3\}$ (Contains 1) $\implies$ Accepting
  • $B = \{1, 2, 3\}$ (Contains 1) $\implies$ Accepting
  • $C = \{3\}$ (Does not contain 1) $\implies$ Non-accepting
  • $T = \emptyset$ (Does not contain 1) $\implies$ Non-accepting

Step 4: Simplified DFA Transition Table & Diagram

\usetikzlibrary{automata, positioning}
\begin{tikzpicture}[shorten >=1pt, node distance=2.5cm, on grid, auto]
   \node[state, initial, accepting] (A) {$A$};
   \node[state, accepting, right=of A] (B) {$B$};
   \node[state, below=of B] (C) {$C$};
   \node[state, below=of A] (T) {$T$};
   
   \path[->]
    (A) edge node {a} (B)
        edge node {b} (T)
    (B) edge [loop above] node {a} (B)
        edge [bend left] node {b} (C)
    (C) edge [bend left] node {a} (A)
        edge node {b} (T)
    (T) edge [loop left] node {a,b} (T);
\end{tikzpicture}

Step 1: Remove Inaccessible States

Let’s trace paths starting from $q_0$:

• $\delta(q_0, 0) = q_1$
• $\delta(q_0, 1) = q_3$
• $\delta(q_1, 0) = q_2$, $\delta(q_1, 1) = q_4$
• $\delta(q_3, 0) = q_2$, $\delta(q_3, 1) = q_4$ All states $\{q_0, q_1, q_2, q_3, q_4\}$ are reachable.
• Is $q_5$ reachable? Let’s check: none of the transition outputs from $\{q_0, q_1, q_2, q_3, q_4\}$ ever lead to $q_5$.
• Therefore, $q_5$ is an inaccessible state and must be removed immediately.

Our remaining active state set is: $Q_{active} = \{q_0, q_1, q_2, q_3, q_4\}$, with $F = \{q_2, q_4\}$.

Step 2: Initial Partition of Distinguishable Pairs

We partition states into non-accepting ($Q-F = \{q_0, q_1, q_3\}$) and accepting ($F = \{q_2, q_4\}$). Any pair containing one accepting and one non-accepting state is immediately marked as distinguishable (denoted by $D$):

• Pairs marked distinguishable in Step 1:
  • $(q_0, q_2), (q_0, q_4)$
  • $(q_1, q_2), (q_1, q_4)$
  • $(q_3, q_2), (q_3, q_4)$

Let’s represent this in the table grid of unmarked pairs:

• Remaining candidates to check:
  • Within non-accepting: $(q_0, q_1), (q_0, q_3), (q_1, q_3)$
  • Within accepting: $(q_2, q_4)$

Step 3: Iterative Refinement

We evaluate the remaining pairs for distinguishability:

1. Check Pair $(q_0, q_1)$:

   • On input $0$: $(\delta(q_0, 0), \delta(q_1, 0)) = (q_1, q_2)$. Since $q_1$ is non-accepting and $q_2$ is accepting, the pair $(q_1, q_2)$ is already marked distinguishable!
   • Therefore, $(q_0, q_1)$ is distinguishable.

2. Check Pair $(q_0, q_3)$:

   • On input $0$: $(\delta(q_0, 0), \delta(q_3, 0)) = (q_1, q_2) \implies$ Distinguishable!
   • Therefore, $(q_0, q_3)$ is distinguishable.

3. Check Pair $(q_1, q_3)$:

   • On input $0$: $(\delta(q_1, 0), \delta(q_3, 0)) = (q_2, q_2)$ (same state $\implies$ indistinguishable).
   • On input $1$: $(\delta(q_1, 1), \delta(q_3, 1)) = (q_4, q_4)$ (same state $\implies$ indistinguishable).
   • Therefore, $(q_1, q_3)$ remains unmarked (indistinguishable).

4. Check Pair $(q_2, q_4)$:

   • On input $0$: $(\delta(q_2, 0), \delta(q_4, 0)) = (q_1, q_1)$ (same state).
   • On input $1$: $(\delta(q_2, 1), \delta(q_4, 1)) = (q_3, q_3)$ (same state).
   • Therefore, $(q_2, q_4)$ remains unmarked (indistinguishable).

Step 4: Final Equivalence Classes

Since no more pairs can be marked in subsequent passes, our partition has stabilized. The indistinguishable states merge into equivalence classes:

• $[q_0] = \{q_0\}$
• $[q_1] = \{q_1, q_3\}$
• $[q_2] = \{q_2, q_4\}$

Step 5: Minimal DFA Construction

We build the new minimized DFA with three merged states:

• $Q_{min} = \{A, B, C\}$ where $A = [q_0]$, $B = [q_1, q_3]$, and $C = [q_2, q_4]$.
• Start State: $A$
• Accepting State: $C$ (since it contains accepting states $q_2$ and $q_4$).

Transitions:

• From $A$:
  • On input $0$: $\delta(q_0, 0) = q_1 \in B \implies \delta'(A, 0) = B$
  • On input $1$: $\delta(q_0, 1) = q_3 \in B \implies \delta'(A, 1) = B$
• From $B$:
  • On input $0$: $\delta(q_1, 0) = q_2 \in C \implies \delta'(B, 0) = C$
  • On input $1$: $\delta(q_1, 1) = q_4 \in C \implies \delta'(B, 1) = C$
• From $C$:
  • On input $0$: $\delta(q_2, 0) = q_1 \in B \implies \delta'(C, 0) = B$
  • On input $1$: $\delta(q_2, 1) = q_3 \in B \implies \delta'(C, 1) = B$

Minimized DFA Transition Table:

\usetikzlibrary{automata, positioning}
\begin{tikzpicture}[shorten >=1pt, node distance=2.5cm, on grid, auto]
   \node[state, initial] (A) {$A$};
   \node[state, right=of A] (B) {$B$};
   \node[state, accepting, right=of B] (C) {$C$};
   
   \path[->]
    (A) edge node {0,1} (B)
    (B) edge [bend left] node {0,1} (C)
    (C) edge [bend left] node {0,1} (B);
\end{tikzpicture}

Part 1: DFA Complement Proof

Construction: Let $M = (Q, \Sigma, \delta, q_0, F)$ be a DFA that recognizes $L$, meaning $L(M) = L$. We construct a complementary machine:

Since the transition function $\delta$ of a DFA is total, every string $w \in \Sigma^*$ has a unique, deterministic path starting from $q_0$ and ending at some state $q \in Q$:

Equivalence Proof: Let’s show that $w \in L(M^c) \iff w \in \bar{L}$:

By definition of set subtraction:

Since $M$ is deterministic, $w$ is accepted by $M$ if and only if its unique computation ends in $F$. Therefore:

By definition of complementation:

This formal bi-conditional proof confirms that $L(M^c) = \bar{L}$. Since $M^c$ is a valid DFA, the complement language $\bar{L}$ is regular. $\blacksquare$

Part 2: NFA Counterexample

In an NFA, a string $w$ is accepted if at least one computation branch ends in an accepting state. If we simply swap the accept and non-accept states of an NFA $N$, we do not necessarily recognize $\bar{L}(N)$.

Counterexample Construction: Let’s define the NFA $N_1$ over $\Sigma = \{a\}$ with states $Q = \{q_1, q_2\}$, start state $q_1$, and accept states $F = \{q_2\}$.

• Transitions:

  • $\delta(q_1, a) = \{q_1, q_2\}$
  • $\delta(q_2, a) = \emptyset$

• Analyze $L(N_1)$: The string $w = a$ starts at $q_1$. On input $a$, the NFA can transition to $q_1$ or $q_2$. Since there is an active computation path ending in $q_2 \in F$, the string $a$ is accepted. Thus:

  $$a \in L(N_1)$$

  The complement language $\bar{L}(N_1)$ must therefore exclude the string $a$:

  $$a \notin \bar{L}(N_1)$$

• Swapping States: Now let’s construct NFA $N_1^c$ by swapping states. The new accept state set is:

  $$F^c = Q - F = \{q_1\}$$

  Let’s run the same string $w = a$ on $N_1^c$. Starting at $q_1$ on input $a$, we can transition to $q_1$ or $q_2$. Since one of our active computation branches ends in $q_1 \in F^c$, the string $a$ is accepted by $N_1^c$!

  $$a \in L(N_1^c)$$

  Since $a \in L(N_1)$ and $a \in L(N_1^c)$, $N_1^c$ does not recognize the complement language of $N_1$. This demonstrates that the state-swapping complementation method fails for nondeterministic machines.