Convert NFA Diagram to DFA

Question

Need help to convert this NFA diagram to DFA. The language associated with the diagram is : L = {vwv : v, w ∈ {a, b}∗ and |v| = 2}

Answer 1

Hint. In this very specific case, you can first consider the languages $L_3$, $L_4$, $L_5$ and $L_6$ obtained by taking $q_3$, $q_4$, $q_5$ and $q_6$, respectively, as initial state. Setting $A = \{a, b\}$, you get $L_3 = A^*aa$, $L_4 = A^*ab$, $L_5 = A^*ba$ and $L_6 = A^*bb$. Now, just compute the minimal DFAs of these four languages: you will find in each case a 3-state DFA. It suffices now to replace the "branch" starting in $q_i$ by the minimal DFA of $L_i$, for $i \in \{3,4,5,6\}$. The resulting automaton will be a 15-state DFA recognising $L$.

Answer 2

You will need to use the subset construction here. In the following,I assume that we are considering nondeterministic finite-state automata without $\epsilon$-transitions (the automaton above is of this kind).

Given an NFA

$N = (Q,q_0,\delta,\Sigma,F)$

the equivalent DFA

$M = (Q_1,q^0_1,\delta_1,\Sigma,F_1)$

is defined by

• $Q_1 = \mathcal{P}(Q)$, that is, the powerset of $Q$; the intuition is that the new states keep track of all the possible sets of states that can be reached

• $q^0_1 = \{ q_0 \}$

• $\delta_1$ is defined by

$\delta(R,a) = \bigcup_{r \in R}\delta(r,a)$,

that is, for a new state $R$, the state reached when reading alphabet symbol $a$, is the state comprised of the set of original states that can be reached by reading an $a$ from any one of the original states in $R$

• $F_1$ is defined as the set of new states that contain at least one of the original final states, that is,

$F_1 = \{ R \mid R \cap F \neq \emptyset \}$

You can build the NFA directly from this definition. If done this way, the DFA will have $2^{15} = 32768$ states, which is a fairly large number of states. However, many of these are not reachable from the start state.

A less inefficient variant of the subset construction is to start with the new start state $\{ q_0 \}$ and find all the transitions from it. This will involve constructing the new states that are reachable in this way. Continue finding all the transitions from the new states that you now have, until you cannot build any more new states. This variant of the subset construction will only construct the class of states reachable from $\{ q_0 \}$, and in many cases this is not the entire state space defined in the above.