2

I am looking for an algorithm that can convert from a DFA to an NFA, while at the same time producing the minimum number of states for the NFA. My gut tells me this can be done with around $n$ states, where the DFA has $O(2^n)$ states. That is, I do not care how many transitions there are, only about the number of NFA states. I am not a graph-theorist, but it seems to me that there should be an algorithm based on the relationship between the number of vertices(states) and edges(transitions) based on Euler's equation.

Said in another way, I am not attempting to minimize the NFA, but to use a minimized DFA to construct an NFA that has fewer states than the DFA.

Pseudo-code is most welcome.

Andries
  • 21
  • Depending on your application, minimizing states might not be what you actually want. Often multiple states can be represented by a single integer counter, and finite arithmetic can drastically improve state machine performance and space. – DanielV May 09 '14 at 13:35

2 Answers2

1

By definition, DFA is itself an NFA. So, conversion from DFA to NFA doesn't make much sense. But, you can always convert a DFA to an equivalent DFA with minimum number of states. There are several algorithms for that purpose. The best known time complexity is $O(n\log\log n)$, where $n$ is the number of states in the DFA.

Sayan Bandyapadhyay
  • 373
  • 1
    Hi Sayan, I know the basic conversion; I am not interested in a big DFA, but in a small NFA. This leads to prettier pictures. – Andries May 08 '14 at 21:16
  • 1
    There are NFAs which contain $n$ states, where their equivalent DFA contains $O(2^n)$ states. So, if you start with one of those DFA and try to get an NFA with minimum number of states, then my claim is that for each node of the DFA you need to check if it should appear in that NFA or not and possibly need to delete it. Thus any such algorithm has a lower bound of $\omega(2^n)$. If you could have done this in $O(n)$ time then you can minimize any DFA with $O(n)$ states in $O(\log n)$ time which violates the existing lower bound $\omega(n)$. – Sayan Bandyapadhyay May 08 '14 at 21:41
0

There are arbitrarily large DFAs where the minimum number of states is not reduced at all by access to the epsilon relation. An example is a DFA on a alphabet of $\Sigma$ with 2k symbols, $a_1, a_2 \cdots a_k$ and $b_1, b_2, \cdots b_k$ and which only accepts strings of the form $a_i b_i$ and nothing else. Then the minimal DFA has k+2 states and the minimal NFA has k+1 states. So one cannot in general go from around $2^n$ states to around $n$ states.

Now to give an answer to your primary question: I'm not aware of a general solution which isn't essentially brute force. There's a decently efficient algorithm for deciding whether two DFAs describe the same language. See https://arxiv.org/abs/0907.5058 . So, one thing one could do is a brute force search of all NFAs on the alphabet in question. For each, convert the NFA into a DFA and test if it matches your DFA. Do this on all NFAs of size n, iterating n until you find a match (which is then minimal). Unfortunately, the number of NFAs with n states grows roughly exponentially in $n$, so this isn't going to be very efficient. The good news is that the algorithm given above for determining if two DFAs match is pretty efficient. My guess though is that there isn't going to be any highly efficient method for finding the smallest NFA which matches a given DFA, and also that proving this would be very difficult.

JoshuaZ
  • 1,752