Как мне доказать, что в DFA нет синхронизирующего слова?
Чтобы найти синхронизирующее слово, я всегда использовал метод проб и ошибок, что хорошо для небольших DFA, но не очень полезно для больших DFA. Однако я хочу знать, существует ли алгоритм определения синхронизирующего слова или есть способ определить, что его не существует. (Вместо того, чтобы просто сказать: "Я не могу найти кого-то, поэтому никто не может существовать", что ни в коем случае не является доказательством).
Я осмотрел Google и пока только что наткнулся на методы определения того, какие верхние и нижние границы для длины синхронизирующего слова будут основываться на количестве состояний, однако это мне не полезно.
1 ответ
Существование верхних границ длины синхронизирующего слова сразу подразумевает существование (очень медленного) алгоритма для его нахождения: просто перечислите все строки длиной меньше верхней границы и проверьте, является ли каждое слово синхронизирующим. Если есть какое-либо из них, то синхронизирующее слово существует, и если ни одно из них не существует, синхронизирующее слово отсутствует. Это экспоненциально медленно, поэтому не рекомендуется на больших DFA.
Дэвид Эппштейн разработал алгоритм полиномиального времени для поиска синхронизирующих слов в DFA, хотя я не очень знаком с этим алгоритмом.
Надеюсь это поможет!