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$

1 Answer 1

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$
4
  • $\begingroup$ Do you know whether-or-not there's also an example for a 1-symbol alphabet? ​ ​ $\endgroup$
    – user12859
    Oct 21, 2016 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$ Oct 28, 2016 at 2:12
  • $\begingroup$ That example's NFA is not unambiguous. ​ (Consider the length-1 input.) ​ ​ ​ ​ $\endgroup$
    – user12859
    Oct 28, 2016 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$ Oct 28, 2016 at 21:48

Your Answer

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