Может ли язык иметь более одного DFA?

17

Например, когда мы рассматриваем DFA, который позволяет строкам, не имеющим подстрок, 00или 11I, я могу создать следующие два DFA:

введите описание изображения здесь

automata finite-automata Мадхури
источник

Ответы:

37

Прежде всего, ваш левый DFA неверен - он принимает, например, 011.

Во-вторых, DFA могут быть канонически минимизированы , поэтому в этом смысле вы всегда можете найти один канонический DFA для определенного языка.

Но в целом, существует бесконечно много разных DFA для каждого языка, поэтому вы можете получить разные правильные ответы.

Shaull
источник
И это даже бесконечно много с точностью до изоморфизма.
Г. Бах
N
Бесконечно много разных DFA даже для конечных языков?
Берги
1
@ Берги: Конечно - вы можете добавить столько избыточных состояний, сколько захотите. Это может звучать «глупо», и это действительно бессмысленно, когда вы создаете автомат самостоятельно. Однако во многих случаях автоматы создаются путем перевода из некоторого другого формализма (например, определения NFA), и в этом случае вы, скорее всего, получите избыточные состояния.
Шал
@Shaull: Вы имеете в виду с ε-переходами или недостижимыми состояниями? ОК, я не учел их.
Берги