12

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

Community
  • 1
Guy Vidal-Naquet
  • 129
  • 3
  • 7
    See the comment by mikero on http://cstheory.stackexchange.com/questions/10829/computing-the-minimal-nfa-for-a-dfa – Tsuyoshi Ito Oct 25 '12 at 13:46

2 Answers2

11

See the paper (postscript)

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

enter image description here

Hendrik Jan
  • 696
  • 3
  • 11
4

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.

Thomas S
  • 1,417
  • 11
  • 14
  • 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 – Andrei Kh Feb 15 '23 at 14:02
  • 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. – Thomas S Feb 16 '23 at 15:24