Proving that 3 regular NFA equivalent to NFA

Question

Let 3 regular NFA be an NFA automata, which satisfies the following: $$\forall q\in Q,\forall\sigma\in \Sigma:|\delta(q,\sigma)|=3$$ Prove that the 3 regular NFA model is equivalent to NFA.

---

$Proof.$ we shall prove that the given 3 regular NFA model is equivalent to DFA model.

$First\ Direction.$ for the first direction, we can turn any DFA automata to 3 regular NFA automata which gets the same language, doing the following:$$\text{if}\ \delta_D(q,a)=p \ \ \text{then: } \ \delta_{N_3}(q,a)=\{p,q_{pit_1},q_{pit_2}\}$$

$Second\ Direction.$ for the second direction, we can turn any NFA automata to DFA automata which gets the same language, doing the following:

Let $N$ be 3 regular NFA, while $Q_{N_3}$ is the states' set, $\Sigma$ is the alphabet, starting state $q_0$, a set of accepted states $F_{N_3}$, and the transition function $\delta_{N_3}$. We define the following DFA:

• The set of states is the set of all subsets of length 3 belongs to $Q_{N_3}$, which means that: $Q_{D} =\left\{X\in \mathcal{P}( Q_{N_{3}})\Bigl| |X|=3\right\}$.
• An alphabet $\Sigma$.
• a starting state ${q_0}$
• An accepted states' set $F_D$: contains any subset of $Q_{N_3}$ in length 3, which contains an element from $F_{N_3}$.
• A transition function $\delta_D:$ such that $\delta_D({q_1,\dots, q_k},a)$ is the set generated by the union of each $i=1,\dots ,k$ of $\delta_{N_3}(q_i,a)$

Now, we know already that the DFA model is equivalent to the NFA model, and therefore, we get that the 3 regular NFA model is equivalent to the NFA model. $Q.E.D$

---

I am not sure whether it's correct or not because it is a bit complex. I will be glad to see what you think.

Answer 1

This looks good to me! I particularly like your idea to use DFAs instead of NFAs directly, as it's easy to add transitions but potentially hard to remove transitions (which would be necessary for an NFA with some large number of out transitions). Here are a few pointers, though, to make your life a bit easier. I'll write $3$-NFA instead of $3$-regular NFA throughout, because life is short.

First, you should be a bit more clear in your DFA $\implies$ $3$-NFA direction. What are $q_{\text{pit}_1}$ and $q_{\text{pit}_2}$? You should be a bit more explicit as to their intended behavior (even though it's obvious from the names). Depending on how much of a stickler your grader is, this could matter. Similarly, it's worth taking one (1) sentence to show that your modified DFA really is a $3$-NFA. Obviously it is, but again, a mean grader could take off points for you not including a proof.

Second, there's no need to duplicate work. In showing that $3$-NFAs can be turned into equivalent DFAs, you're basically redoing the argument that a general NFA can be converted into a DFA. Of course, you've almost certainly seen this argument before, which lets you sidestep this argument entirely! Every $3$-NFA is, in particular, an NFA. So if you know that NFAs can be converted into DFAs, then you also know $3$-NFAs can be! Because a $3$-NFA is a special case of an NFA! This means you can say something like "Since any NFA has an equivalent DFA, and every $3$-NFA is an NFA, we get the $3$-NFA $\implies$ DFA direction as a corollary of an earlier result".

---

I hope this helps ^_^