8
$\begingroup$

This is somewhat related to another question I asked, but I feel it's different enough to warrant its own question.

I'm doing research where I'm trying to find the structure of complements of a certain class of finite languages. It's easy for me to get the minimal DFAs accepting these languages, but I'd like to examine what kind of structure NFAs accepting these langauges have, particularly how nondeterminism helps with state-size of the automata (the DFAs are exponentially large).

The problem is, the main NFA reduction technique uses equivalences, which won't produce any reduction if I start with a minimal DFA (since it's basically using the same technique). If I start with a non-minimal DFA, it just spits out the minimal DFA.

What I'm wondering is, are there algorithms which can start with a DFA, and shrink it into a smaller NFA by introducing nondeterminism? Are there "standard techniques" to do this?

I have found preorder reductions, which look promising but hard to implement. I'm open to many suggestions.

$\endgroup$
  • $\begingroup$ its possible but Pspace complete to find a minimal NFA for a DFA $\endgroup$ – vzn Jul 13 '13 at 23:42
  • $\begingroup$ Yes but there are reduction techniques which are useful but don't find the minimal in all cases. I'm more interested in how nondeterminism reduces the state size than actually finding the minimal case. $\endgroup$ – jmite Jul 14 '13 at 9:08
4
$\begingroup$

For efficient heuristics I'd suggest looking into the CAD literature on the state encoding problem (assigning binary identifiers to states of a DFA to minimize the amount of logic for the state transition function.) Devadas and Newton, "Decomposition and factorization of sequential finite state machines," IEEE TCAD, 8(11):1206-1217, 1989 points out that there is a close relationship between state encoding and state machine decomposition.

If for a DFA with $N$ states you assign a unique $M$ bit state identifier to each state ($\lg_2N < M\leq N$), then you have essentially decomposed the DFA into a network of $M$ interacting two-state machines. Equivalently: you have defined a set $S$ with $M$ elements, and assigned a unique subset of $S$ to each state in your original DFA. This is also what the Rabin-Scott powerset construction algorithm does. So by doing a state encoding on the DFA we are trying to reverse engineer the set that the powerset construction algorithm started from.

In the traditional state encoding problem all encodings are legal, and there is some objective function (related to the amount of logic in the state transition function) that you are trying to minimize. To generate an NFA you need to solve a constrained version of the enconding problem where:

an encoding of $M$ bit identifiers to the DFA states represents an NFA iff for each symbol in the alphabet the transition function for each bit is a simple disjunction of bits. (No conjunction or negation is allowed.)

So you could enumerate all the $M$ bit encodings for all $\lg_2N < M\leq N$, and check whether each one satisfies the constraint. (Note that for $M=N$ the trivial "one-hot" encoding always satisfies the constraints, and gives you the DFA.) The enumeration is ridiculously large though, (Di Micheli's textbook gives it as something like $\frac{2^M !}{(2^M - N)!M!}$.) The reason I'm suggesting the CAD literature is that there are techniques for doing this search implicitly rather than enumerating (for example, by using BDDs, see Lin, Touati and Newton, "Don't care minimization of multi-level sequential logic networks," Int'l Conf Comp-Aided Dsgn ICCAD-90:414-417, 1990.

Example

Take the following DFA, (with a state encoding that I derived by cheating (I generated the DFA from an NFA using Rabin-Scott, and the encoding represents the subsets chosen by Rabin-Scott.))

DFA from Rabin-Scott

If we call the bits in the state assignment ABCD, then when the input symbol is 1, the transition function is A=A, B=A, C=B, D=C. When the input symbol is 0, the transition function is A=A, C=B, D=C. This is a purely disjunctive transition function with no conjunction or negation, so this state encoding gives us an NFA. The states in the NFA correspond one-to-one with the bits in the encoding, and the transition function is as given:

NFA for Rabin-Scott

Formulation as boolean satisfiability problem

The informal description above leads directly to an encoding as a boolean satisfiability problem. There is a set of variables that describes the transitions in the NFA, and a set of variables for the DFA state encoding that would be derived from Rabin-Scott for the chosen NFA. The transitions of the specific DFA you are trying to decompose are used to place constraints on the NFA transitions.

Suppose we are given a DFA with $N$ states for a language with $S$ symbols, and we would like to derive an $M$ state NFA, with $\lg_2N<M\leq N$. We will use the variables $y_{sft}$ to represent the possible transitions in the NFA. $y_{sft}$ will be true iff there is a transition in the NFA from NFA state $f$ to NFA state $t$ on symbol $s$. In the above example NFA, the alphabet is of size 2 and there are 4 NFA states, so there are $SM^2=32$ $y$ variables and $y_{0AA}, y_{1AA}$, and $y_{1AB}$ are all true while $y_{1DA}$ is false.

We will use the variables $x_{dn}$ to indicate whether or not the Rabin-Scott algorithm should include NFA state $n$ in the set of states labeling DFA state $d$. In the example above we have $N=8$ DFA states and $M=4$ NFA states so there are 32 $x$ variables. In the example above suppose the bottom-most state (the one labeled "1011") is state $k$, then $x_{kA}$, $x_{kC}$, and $x_{kD}$ are true while $x_{kB}$ is false.

Now the constraints. First of all, Rabin-Scott must find a different encoding for each DFA state, so for the DFA states $i < j$ and all NFA states $\{A,B,\cdots, D\}$: $$ (x_{iA} \neq x_{jA}) + (x_{iB} \neq x_{jB}) + \cdots + (x_{iD} \neq x_{jD}). $$

Next it must be the case that if Rabin-Scott found a transition from DFA state $i$ to DFA state $j$ on symbol $s$ then for each NFA state $k$ included in the encoding of $j$ there must be an NFA state $l$ from the encoding of DFA state $j$ such that the original NFA had a transition from $l$ to $k$. In the example above, on symbol "1" there is a DFA transition from DFA state "1000" to DFA state "1100" so there must be an NFA transition from NFA state A to NFA states A and B and no NFA transition from NFA state A to either NFA state C or D. So for each of the $o(SN^2)$ edges in the DFA we have the constraints: $$ \begin{eqnarray*} x_{jA} & = & y_{sAA} x_{iA} + y_{sBA} x_{iB} + \cdots + y_{sDA} x_{iD} \\ x_{jB} & = & y_{sAB} x_{iA} + y_{sBB} x_{iB} + \cdots + y_{sDB} x_{iD} \\ & & \cdots \\ x_{jD} & = & y_{sAD} x_{iA} + y_{sBD} x_{iB} + \cdots + y_{sDD} x_{iD}. \end{eqnarray*} $$

Finally we need to deal with the start and accept states. The DFA start state is encoded with the union of the NFA start states, so the DFA start state better not be encoded with the empty set, so $x_0A + x_0B + \cdots + x_0D$. And finally we need a set of variables $f_n$ to indicate whether each NFA state is an NFA accept state. It must be the case that the encoding for every DFA accept state contains at least one NFA accept state and that the encoding for every DFA non-accept state contains no NFA accept states so: $x_{iA}f_A + x_{iB}f_B + \cdots + x_{iD}f_D$ for DFA accept states $i$ and $\neg (x_{jA}f_A + x_{jB}f_B + \cdots + x_{jD}f_D)$ for DFA non-accept states $j$.

$\endgroup$
  • $\begingroup$ This idea of reverse-engineering the subset construction is exactly what I'm looking for. It seems complicated, so I'll take some time to parse through it. Thanks! $\endgroup$ – jmite Jul 15 '13 at 17:36
  • 1
    $\begingroup$ I've been trying to figure out how to reformulate it as a SAT problem, but haven't put enough time into it yet. $\endgroup$ – Wandering Logic Jul 15 '13 at 17:56
3
$\begingroup$

Minimising NFAs is hard, so hard indeed that even approximation is hard; see Minimizing NFA’s and Regular Expressions by Gramlich and Schnitger (2005). This article seems to have some useful references, too, e.g. NFA Reduction Algorithms by Means of Regular Inequalities by Champarnaud and Coulon (2002) which contains minimisation techniques.

$\endgroup$
  • $\begingroup$ Yeah, I'm okay if it's just a reduction and not a full minimization. I'll take a look, those references look really good though. $\endgroup$ – jmite Jul 13 '13 at 12:42
2
$\begingroup$

There exists some notions of canonical FSAs that are not necessarily deterministic, hence can be smaller than the minimal DFA. One example is the "Residual" FSAs, for which one can compute canonical residual FSAs quite directly, see F. Denis, A. Lemay, and A. Terlutte. "Residual finite state automata", Fundamenta Informaticae 51(4):339-368, 2002. Several alternatives exist.

$\endgroup$
  • $\begingroup$ Could you explain the computing quite directly? It ways that computing the canonical residual FSA is a PSPACE-complete problem. That still might work for me (my machines are fairly small) but I'm wary of it. $\endgroup$ – jmite Jul 13 '13 at 6:14
  • $\begingroup$ In particular, I'm confused as to how I'd determine if a state in a machine is "coverable", as is defined in page 17 of the paper, right before Section 5 Lemma 4. $\endgroup$ – jmite Jul 13 '13 at 6:44

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.