Can somebody provide an example of two equivalent (recognizing the same language) minimal non-deterministic automata (NFA) which are not isomorphic?
12
$\begingroup$
$\endgroup$
-
7$\begingroup$ See the comment by mikero on cstheory.stackexchange.com/questions/10829/… $\endgroup$ – Tsuyoshi Ito Oct 25 '12 at 13:46
11
$\begingroup$
$\endgroup$
-
1$\begingroup$ Thank you for sharing! Their paper includes a nice example. :) $\endgroup$ – Michael Wehar Jun 11 '15 at 5:10
4
$\begingroup$
$\endgroup$
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.
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.
