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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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

Improve this answer
$\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$
    – Hendrik Jan
    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$
    – Hendrik Jan
    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.