<p>See the <a href="https://www.researchgate.net/publication/220530733_A_note_about_minimal_non-deterministic_automata" rel="nofollow noreferrer" title="minimal">paper</a> (postscript)</p>

<p>Arnold, Dicky, Nivat. A note about minimal non-deterministic automata </p>

<p><a href="https://i.sstatic.net/Q4BPb.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Q4BPb.jpg" alt="enter image description here"></a></p>

CC BY-SA 3.0
2015-06-11T05:10:32.670Z
Thank you for sharing!  Their paper includes a nice example.  :)
Michael Wehar
CC BY-SA 3.0
2012-10-25T15:32:17.280Z
2016-10-21T10:38:52.110Z
2016-10-21T10:38:52.110Z
Hendrik Jan
<p>Along a different line: the set $L_6$ of strings of the form $a^n$, where $n$ is <em>not</em> a multiple of 6 has two very different minimal NFAs.
<a href="https://i.sstatic.net/7sutv.jpg" rel="noreferrer"><img src="https://i.sstatic.net/7sutv.jpg" alt="Two minimal NFAs for $L_6$."></a></p>

<p>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.</p>

CC BY-SA 4.0
2023-02-15T14:02:17.313Z
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
CC BY-SA 4.0
2023-02-16T15:24:08.100Z
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
CC BY-SA 3.0
2016-10-23T07:46:24.003Z
2016-10-23T07:46:24.003Z
Thomas S
<p>Can somebody provide an example of two equivalent (recognizing the same language) minimal non-deterministic automata (NFA) which are not isomorphic?</p>

CC BY-SA 3.0
2012-10-25T13:46:40.563Z
See the comment by mikero on http://cstheory.stackexchange.com/questions/10829/computing-the-minimal-nfa-for-a-dfa
Tsuyoshi Ito
<fl.formal-languages><automata-theory>
Non-isomorphic minimal non-deterministic finite automata
Guy Vidal-Naquet
# Non-isomorphic minimal non-deterministic finite automata

(Asked by: username_0 on 2012-10-25)

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

**Tags:** fl.formal-languages, automata-theory

> **Comments:**
> **username_1**: See the comment by mikero on http://cstheory.stackexchange.com/questions/10829/computing-the-minimal-nfa-for-a-dfa  

---

## 2 answers

### Answer by username_2 on 2012-10-25. Score: 11

See the [paper](https://www.researchgate.net/publication/220530733_A_note_about_minimal_non-deterministic_automata "minimal") (postscript)

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

[![enter image description here](https://i.sstatic.net/Q4BPb.jpg)](https://i.sstatic.net/Q4BPb.jpg)

> **Comments:**
> **username_3**: Thank you for sharing!  Their paper includes a nice example.  :)  

---

### Answer by username_4 on 2016-10-23. Score: 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$.](https://i.sstatic.net/7sutv.jpg)](https://i.sstatic.net/7sutv.jpg)

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.

> **Comments:**
> **username_5**: 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  
> **username_4**: 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.  

---

