10
$\begingroup$

Brzozowski's algorithm can be extended to Moore automata but its time complexity is exponential in general. Is there any other algorithm for minimization of Moore automata? What are the running times of these algorithms if any?

$\endgroup$
  • $\begingroup$ Which Brzozowski's algorithm are you referring to? The one using derivatives of regular expressions? $\endgroup$ – J.-E. Pin Jun 29 '15 at 16:31
  • 1
    $\begingroup$ Welcome to SE Computer Science. Since you apparently did not yet read the presentation of the site, you should know that it is a cooperative work, based on technical exchange between users asking questions and users who provide answers or comments. Thus it is consider proper to answer users asking for more details in comments, to upvote good answers or good comments (or other interesting questions or answers that you read), and ultimately to accept the answer you consider best for your questions by clicking the "check sign" (like a V) of the left of the chosen answer. $\endgroup$ – babou Jun 30 '15 at 9:03
  • $\begingroup$ Was the answer any use to you? $\endgroup$ – babou Jul 3 '15 at 22:20
6
$\begingroup$

The original DFA minimization algorithm was actually designed for Moore Machines, guided by their apparently more observable behavior. But the algorithm presented here is a reconstruction from the DFA minimization, since I discovered the historical evidence after the fact.

After Wikipedia (with some notational changes):

A Moore machine can be defined as a 6-tuple $(Q, q_0, \Sigma, \Pi, \delta, \gamma)$ consisting of the following:

  • a finite set of states $Q$
  • a start state (also called initial state) $q_0$ which is an element of $Q$
  • a finite set called the input alphabet $\Sigma$
  • a finite set called the output alphabet $\Lambda$
  • a transition function $\delta : Q \times \Sigma \rightarrow Q$ mapping a state and the input alphabet to the next state
  • an output function $\gamma : Q \rightarrow \Pi$ mapping each state to the output alphabet

From this definition, a Moore machine is a deterministic finite state transducer.

I have no reference for minimization of Moore automata. However it seems not too hard to imagine an algorithm, derived from the algorithm used for deterministic finite state automata.

The idea in DFA minimization is based on the Myhill-Nerode characterization of regular languages.

Given a language $L$, and a pair of strings $x$ and $y$, define a distinguishing extension to be a string $z$ such that exactly one of the two strings $xz$ and $yz$ belongs to $L$. Define a relation $R_L$ on strings by the rule that $x R_L y$ iff there is no distinguishing extension for $x$ and $y$. It is easy to show that $R_L$ is an equivalence relation on strings, and thus it divides the set of all strings into equivalence classes.

The Myhill-Nerode theorem states that $L$ is regular if and only if $R_L$ has a finite number of equivalence classes, and moreover that the number of states in the smallest deterministic finite automaton (DFA) recognizing $L$ is equal to the number of equivalence classes in $R_L$.

Indeed each state $q$ of the smallest DFA is such that $W_q$ as defined above is one of the equivalence classes for the relation $R_L$.

For a non-minimal DFA for the regular language $L$, it is easy to show that each set $W_q$ contains strings that all belong to a same equivalent class with respect to $R_L$.

Hence, the minimization of the DFA actually consists of merging states (considered as sets of equivalent strings), whenever it is shown that two distinct states contain equivalent strings.

Two reasonably fast algorithms exists for that purpose, Moore algorithm (1956) which is in time $O(n^2)$ and Hopcroft's algorithm (1971) in time $O(n\log n)$.

The extension to Moore automata is best understood in redefining the equivalence relation as $R_T$ for a transducer $T$. The relation $R_L$ was concerned with whether future input would lead equivalently to an accepting state. The $R_T$ equivalence relation of Moore automata is concerned with whether future input will produce the same output.

Hence, given a transducer $T$, and two strings $x$ and $y$, we define a distinguishing extension to be a string $z$ such that $T(xz)=T(x)u$ and $T(yz)=T(y)v$ with $u\neq v$, i.e. such that the output behaviour of the transducer differs for $z$ depending on whther it is following $x$ or $y$.

Again, $R_T$ is an equivalence relation, dividing all strings in $\Sigma^*$ into equivalence classes. In the case of a Moore machine, these classes will again correspond to state of the minimal transducer.

The following algorithm mimics the Moore algorithm for DFA minimisation.

We define an initial partition $\mathcal P$ of $Q$ into classes of states $S_e$ as follow:

$\forall e\in\Pi:\; S_e=\{q\in Q\mid \gamma(q)=e\}$

Then we split the classes in $\mathcal P$ as follows:

repeat successively for each class of states $S$, until none changes
$\ \ $ repeat $\forall a\in\Sigma,\;$
$\ \ \ \ $ If $ \exists S'\in \mathcal P,\; \forall q\in S,\; \delta(q,a)\in S'$ then do nothing
$\ \ \ \ $ else split $S$ into subsets $S_i$ such that
$\ \ \ \ \ \ $ for each subset $S_i$, there is a different class $S'\in \mathcal P$ such that $ \forall q\in S_i,\; \delta(q,a)\in S'$
$\ \ \ \ \ \ $ (the subsets $S_i$ replace $S$ in $\mathcal P$)

When there is no class left that needs to be split, the remaining classes of states will form the states of the minimal Moore machine.

By construction, all states in a class have the same output which is the output for the class.

Similarly, for any input $a\in\Sigma$, all states in a class go to some state in the same other class, which defines the transition function for the minimal Moore machine.

Complexity analysis: Let $n=|Q|$ be the number of states, and $s=|\Sigma|$ the size of the input alphabet.
The main loop is executed at most $n$ times, since each iteration must split at least one class of states, and each class contains at least one state. Each iteration of the loop examines each state a finite number of times, and in proportion to the number of input symbols. Hence the complexity of the algorithm is $O(sn^2)$, the same as that of the DFA minimization algorithm that served as a guideline for this one.

I do not have any reference for this minimization of Moore machines. Possibly it is included in his paper:

Moore, Edward F (1956). "Gedanken-experiments on Sequential Machines". Automata Studies, Annals of Mathematical Studies (Princeton, N.J.: Princeton University Press) (34): 129-153.

This paper is the main reference introducing Moore Machines. It is also the reference for Moore's DFA minimization algorithm. It should thus be surprising if the adaptation of the algorithm to the minimization of Moore Machines were not at least suggested in that paper. I did check the paper, and the version of the minimization algorithm that is presented is actually for Moore machines, not for DFA. The paper is well written, but the style of the time makes it a bit harder to read. It is interesting to see that many of the ideas of the Myhill-Nerode theory of Finite State Machines are already sketched in this paper.

The more recent $O(sn\log n)$ algorithm due to John Hopcroft (1971) should be similarly adaptable to Moore machines. It is not clear that there was any reason to publish this adaptation anywhere, and the Hopcroft paper seems to have no reference to Moore machines.

$\endgroup$
  • $\begingroup$ @Raphael A reference ... Well, you are lucky, I redesigned the algorithm, because I do not have access to a library. But since you asked for a reference, I got you one. You should like it. But I am not sure I would use it for teaching. $\endgroup$ – babou Jun 29 '15 at 21:37
  • $\begingroup$ @Raphael The paper is interesting in its presentation that attempts to be very intuitive, more operational than algebraic. I do not remember all details of the contribution of Myhill and Nerode (two years later in 1958), and I did not read the paper carefully enough (I rather skimmed it) but I am wondering if the theory should not be attributed to Moore as well. $\endgroup$ – babou Jun 30 '15 at 21:44
2
$\begingroup$

A version of Brzozowski's algorithm using derivatives of regular expressions is given in [2], Chapter 12, Section 4, where it is credited to [4]. See [1] and [3] for the more general case of subsequential transducers (the terminology is a bit outdated and the term sequential transducer is probably more appropriate nowadays).

[1] C. Choffrut, Minimizing subsequential transducers: a survey, Theoret. Comp. Sci. 292 (2003), 131–143.

[2] S. Eilenberg, Automata, Languages and Machines, vol. A, Academic Press, 1974.

[3] J.-E. Pin, A tutorial on sequential functions. (Slides)

[4] G. N. Raney, Sequential functions, JACM 5 (1958), 177–180.

$\endgroup$
  • $\begingroup$ @D.W. Thanks for the edit. Just perfect. $\endgroup$ – J.-E. Pin Jul 2 '15 at 22:13
1
$\begingroup$

Brzozowski's algorithm is a bad starting point (if you are concerned with asymptotic worst-case runtime). Even Wikipedia tells you as much:

As Brzozowski (1963) observed, reversing the edges of a DFA produces a non-deterministic finite automaton (NFA) for the reversal of the original language, and converting this NFA to a DFA using the standard powerset construction (constructing only the reachable states of the converted DFA) leads to a minimal DFA for the same reversed language. Repeating this reversal operation a second time produces a minimal DFA for the original language. The worst-case complexity of Brzozowski's algorithm is exponential, as there are regular languages for which the minimal DFA of the reversal is exponentially larger than the minimal DFA of the language,[6] but it frequently performs better than this worst case would suggest.

The algorithm has exponential worst-case runtime even on DFA because it computes an automaton for the reverse, which may have to be exponentially large. So your problem does not come from the extension to transducers.

Try to adapt another DFA-minimisation algorithm.

$\endgroup$

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.