12
$\begingroup$

Can somebody provide an example of two equivalent (recognizing the same language) minimal non-deterministic automata (NFA) which are not isomorphic?

$\endgroup$
11
$\begingroup$

See the paper (postscript)

Arnold, Dicky, Nivat. A note about minimal non-deterministic automata

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Thank you for sharing! Their paper includes a nice example. :) $\endgroup$ – Michael Wehar Jun 11 '15 at 5:10
4
$\begingroup$

Along a different line: the set $L_6$ of strings of the form $a^n$, where $n$ is not a multiple of 6 has two very different minimal NFAs. Two minimal NFAs for $L_6$.

One of them is basically the minimal DFA, the other guesses whether it is not a multiple of 2 or not a multiple of 3.

$\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.