Czy język może mieć więcej niż jeden DFA?

Na przykład, gdy weźmiemy pod uwagę DFA, który zezwala na łańcuchy bez podłańcuchów 00lub 11mogę wygenerować następujące dwa DFA:

automata finite-automata

— Madhuri
źródło

Przede wszystkim lewy DFA jest niepoprawny - akceptuje np. 011.

Po drugie, DFA można kanonicznie zminimalizować , więc w tym sensie zawsze można znaleźć jeden kanoniczny DFA dla określonego języka.

Ale ogólnie istnieje nieskończenie wiele różnych DFA dla każdego języka, więc możesz uzyskać różne poprawne odpowiedzi.

— Shaull
źródło

I to nawet nieskończenie wiele do izomorfizmu.

— G. Bach,

N

$\mathbb{N}$

Nieskończenie wiele różnych DFA nawet dla języków skończonych?

— Bergi

@Bergi: Oczywiście - możesz dodać dowolną liczbę nadmiarowych stanów. Może to zabrzmieć „głupio” i jest naprawdę bezsensowne, kiedy sam konstruujesz automat. Jednak wiele razy automaty są konstruowane przez tłumaczenie z innego formalizmu (np. Określanie NFA), w którym to przypadku istnieje duże prawdopodobieństwo, że wystąpią nadmiarowe stany.

— Shaull

@Shaull: Masz na myśli przejścia ε lub nieosiągalne stany? OK, nie brałem ich pod uwagę.

— Bergi