3
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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 ^_^

$\endgroup$
3
  • 1
    $\begingroup$ Thank you so much! I like what you wrote and especially how you wrote it. In addition, in the second direction, can I also define $Q_{D} =\left\{X\in \mathcal{P}( Q_{N_{3}})\Bigl| |X| \geq 3\right\}$ instead? $\endgroup$
    – Chopin
    Nov 7, 2021 at 21:39
  • $\begingroup$ That probably works, but why think? Just add a state for every possible subset. If you end up with some extra states, who cares. This is an existence proof, so there's no need to split hairs about efficiency $\endgroup$ Nov 7, 2021 at 23:57
  • $\begingroup$ Right, but in $F_D$ I still have to take all subsets of length 3, which contains an element from $F_{N_3}$. Right? because if I just take all subsets from $F_{N_3}$ then it doesn't work right? $\endgroup$
    – Chopin
    Nov 8, 2021 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.