7
$\begingroup$

It is well known that minimizing an NFA for a fixed regular language is $PSPACE-Complete$.

As far as I know, there are no better than trivial algorithms for minimizing such NFA, but there's a little improvement if you consider symmetries.

I've a specific regular language I'd like to compute a minimal automaton for:

$$ L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall i\in[k]: \sigma_i\in\Sigma ~\text{ and }~ \forall j\ne i: \sigma_j\ne\sigma_i \}$$

But at the moment I can't seem to close the gap between the automaton I know to build for it and the lower bound I can prove for it.

I thought it might be fruitful to use some tool that given a language (it is finite for all $k,n$), searches (exhaustively if needed) for the smallest automaton which accept it, and see what the automaton looks like for small values of $k,n$.

Does anyone know a tool which builds a minimal automaton for a given language?

$\endgroup$

2 Answers 2

5
$\begingroup$

The following paper reports on an implementation of the Kameda-Weiner algorithm for computing a minimal NFA, as well on an approach using a SAT solver. I don't know whether the implementation is available, but perhaps you can contact the authors about this.

Jaco Geldenhuys, Brink van der Merwe, and Lynette van Zijl. Reducing Nondeterministic Finite Automata with SAT Solvers. Revised Selected Papers from the 8th International Workshop on Finite-State Methods and Natural Language Processing (FSMNLP 2009), LNCS 6062, Springer, pages 81-92, 2010.

$\endgroup$
0
$\begingroup$

There is an elementary argument showing that a minimal NFA must have $O(|\Sigma|^k)$ states, so I guess the standard construction is essentially optimal. The argument is as follows. Suppose w.l.o.g. that $A$ is a NFA without $\epsilon$-transitions recognizing $L_k$. We can make the following assumptions:

  • $A$ has a unique starting state $q_0$ and each state recognizes a non-empty language;
  • $A$ is acyclic, and contains $k+1$ levels where each state at level $i$ only recognizes words in $L_i$.

It can be seen that if two words of $L_i$ have a different set of letters, then they cannot lead to the same state starting from $q_0$. It follows that the number of states at level $i$ is at least $\binom{|\Sigma|}{i}$, and thus the total number of states is at least $\sum_{i = 0}^{k} \binom{|\Sigma|}{i} = O(|\Sigma|^k)$.

$\endgroup$
3
  • $\begingroup$ This is not correct. See the link in the question for a not trivial automaton of size: $O((2e)^{k\cdot log^3(n)}\cdot poly(n))$. $\endgroup$
    – R B
    Mar 9, 2014 at 20:47
  • 1
    $\begingroup$ I see, but your solution requires preprocessing as you first apply a hash function. This kind of computation cannot be performed with a NFA (maybe with a transducer?) so could you please make your question more specific? $\endgroup$
    – Super9
    Mar 9, 2014 at 20:51
  • $\begingroup$ This is not preproccesing needed to be done by the NFA, this is a way of computing the NFA / showing such NFA exists. The NFA, by itself is a standard NFA. My question is whether there exists a tool that gets as in input a set of words and computes the minimal NFA that accepts them (and just them). $\endgroup$
    – R B
    Mar 9, 2014 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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