Nieizomorficzne minimalne niedeterministyczne automaty skończone

Czy ktoś może podać przykład dwóch równoważnych (rozpoznających ten sam język) minimalnych niedeterministycznych automatów (NFA), które nie są izomorficzne?

fl.formal-languages automata-theory

— Guy Vidal-Naquet
źródło

Zobacz komentarz mikero na cstheory.stackexchange.com/questions/10829/…

— Tsuyoshi Ito,

Odpowiedzi:

Zobacz artykuł (postscriptum)

Arnold, Dicky, Nivat. Uwaga na temat minimalnych niedeterministycznych automatów

— Hendrik Jan
źródło

Dziękuję za podzielenie się! Ich artykuł zawiera ładny przykład. :)

— Michael Wehar,

Wzdłuż innej linii: zestaw łańcuchów w formie , gdzie jest nie wielokrotność 6 zawiera dwa różne minimalne NFAs. $L_6$ $a^n$ $n$

Jeden z nich to w zasadzie minimalny DFA, drugi zgaduje, czy nie jest wielokrotnością 2, czy nie wielokrotnością 3.

— Thomas S.
źródło

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.

Licensed under cc by-sa 3.0 with attribution required.