Can somebody provide an example of two equivalent (recognizing the same language) minimal non-deterministic automata (NFA) which are not isomorphic?
$\begingroup$
$\endgroup$
1
-
7$\begingroup$ See the comment by mikero on cstheory.stackexchange.com/questions/10829/… $\endgroup$– Tsuyoshi ItoOct 25, 2012 at 13:46
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Thank you for sharing! Their paper includes a nice example. :) $\endgroup$ Jun 11, 2015 at 5:10
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ But isn't the later automaton not minimal? One can discard the state a and set b and d as inital states (and moving the accepted states to c, e and f). So a minimal NFA has actually 5 states $\endgroup$ Feb 15 at 14:02
-
$\begingroup$ That depends on the actual definition of NFA. You are right: I silently assumed that NFAs have one initial state. That's at least a frequent definition, see, e.g., the Wikipedia article on NFAs. $\endgroup$– Thomas SFeb 16 at 15:24