patternMinor
Is there a language with non-isomorphic minimum-state UFAs?
Viewed 0 times
ufasnonwithminimumisomorphiclanguagestatethere
Problem
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?
Is there a regular language whose state-minimal Unambiguous Finite Automata are not all isomorphic to each other?
Solution
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.
They give the following example, which happen to be both unambiguous, so are applicable in your case too.
Context
StackExchange Computer Science Q#64910, answer score: 3
Revisions (0)
No revisions yet.