6
$\begingroup$

For all regular languages L, by the Myhill-Nerode classes, all state-minimal DFAs for L are isomorphic. ​ On the other hand, "a regular language may have many non-isomorphic state-minimal nfas". ​ What about Unambiguous Finite Automata? ​ Every DFA is also a UFA, so every regular language has at least one UFA. ​ The natural numbers are well-ordered, so in turn every regular language has at least one state-minimal UFA.

Is there a regular language whose state-minimal Unambiguous Finite Automata are not all isomorphic to each other?

$\endgroup$
3
$\begingroup$

In their paper "A note about minimal non-deterministic automata" Arnold, Dicky and Nivat observe that the problem of finding non-isomorphic minimal automata was solved in a report by Christian Carrez (Lille, 1970).

They give the following example, which happen to be both unambiguous, so are applicable in your case too.

isomorphic nondet finite automata

$\endgroup$
  • $\begingroup$ Do you know whether-or-not there's also an example for a 1-symbol alphabet? ​ ​ $\endgroup$ – user12859 Oct 21 '16 at 10:43
  • $\begingroup$ A very nice example for a one-symbol alphabet was just added to a similar question at our cousin site cstheory: cstheory.stackexchange.com/a/36824/12122 $\endgroup$ – Hendrik Jan Oct 28 '16 at 2:12
  • $\begingroup$ That example's NFA is not unambiguous. ​ (Consider the length-1 input.) ​ ​ ​ ​ $\endgroup$ – user12859 Oct 28 '16 at 14:37
  • $\begingroup$ Sorry. You are right of course. I forgot about your restriction! It still is a nice example, but not at this point. $\endgroup$ – Hendrik Jan Oct 28 '16 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy