12
$\begingroup$

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

$\endgroup$
1

2 Answers 2

11
$\begingroup$

See the paper (postscript)

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

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ Thank you for sharing! Their paper includes a nice example. :) $\endgroup$ Commented Jun 11, 2015 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$
2
  • $\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$
    – Andrei Kh
    Commented Feb 15, 2023 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 S
    Commented Feb 16, 2023 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.