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

17

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:

wprowadź opis zdjęcia tutaj

automata finite-automata Madhuri
źródło

Odpowiedzi:

37

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.
Nieskończenie wiele różnych DFA nawet dla języków skończonych?
Bergi
1
@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