Минимизация автоматов, принимающих

Каков стандартный подход к минимизации Büchi-Automata (или также Müller-Automata)? Перенос обычного метода из конечных слов, то есть установка двух состояний равными, если слова «заканчиваются» из принятых состояний одинаковы, не будут работать. Например, рассмотрим Büchi-Automoton, принимающий все слова с бесконечным числом a, состоящим из двух состояний: начального и конечного состояний, и конечное состояние вводится каждый раз, когда читается a, и начальное состояние вводится каждый раз, когда a другой символ читается. Оба состояния считаются равными по вышеприведенному определению, но их сложение приводит к автоматам, состоящим из одного состояния, и тем самым принимает все слова.

В целом, $\omega$ регулярные языки могут не иметь единственного минимального DBW. Например, язык «бесконечно много а и бесконечно много б» ​​имеет два DBW с тремя состояниями (на рисунке замените $\neg a$ на $b$ ):

Как видите, они не являются топологически эквивалентными.

Следовательно, задача минимизации сложнее, чем конечный случай, и на самом деле она NP-полная .

Этот вопрос породил много литературы в 80-х годах, отчасти из-за плохого подхода к проблеме. Это довольно длинная история, которую я постараюсь обобщить в этом ответе.

1. Случай конечных слов

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

Напомним , что DFA является доступным , если для всех ц ∈ Q , есть слово у ∈ * такое , что я ⋅ у = д . Это полное , если ц ⋅ определен для всех ц ∈ Q и в ∈ A .$(Q, A, \cdot, i, F)$$q \in Q$$u \in A^*$$i \cdot u = q$$q \cdot a$$q \in Q$$a \in A$

Пусть и A 2 = ( Q 2 , A , ⋅ , i 2 , F 2 ) два полных, доступных DFA. Морфизм из A 1 в A 2 является функцией φ : Q 1 → Q 2 такой, что${\cal A}_1 = (Q_1, A, \cdot, i_1, F_1)$${\cal A}_2 = (Q_2, A, \cdot, i_2, F_2)$$\mathcal{A}_1$$\mathcal{A}_2$$\varphi:Q_1 \to Q_2$

1. ,$\varphi(i_1) = i_2$
2. ,$\varphi^{-1}(F_2) = F_1$
3. для всех и ∈ , φ ( д ) ⋅ = φ ( д ⋅ ) .$q \in Q_1$$a \in A$$\varphi(q)\cdot a=\varphi(q\cdot a)$

Можно показать, что из этих условий следует, что обязательно сюръективен (и поэтому | Q 2 | ⩽ | Q 1 | ). Кроме того, существует не более одного морфизма от A 1 до A 2, и если этот морфизм существует, то A 1 и A 2 распознают один и тот же язык. Теперь можно показать, что для каждого языка L существует уникальный полный доступный DFA A L, принимающий L, и такой, что для каждого полного доступного DFA A, принимающего $\varphi$$|Q_2| \leqslant |Q_1|$${\cal A}_1$${\cal A}_2$${\cal A}_1$${\cal A}_2$$L$${\cal A}_L$$L$$\cal A$$L$, Существует морфизм из на A L . Этот автомат называется минимальным DFA из L . Еще раз отметим, что, поскольку число состояний в A L меньше количества состояний в A , A L также минимально в первом смысле.$\cal A$${\cal A}_L$$L$${\cal A}_L$$\cal A$${\cal A}_L$

Стоит отметить, что существует также подходящее алгебраическое определение для неполных DFA. См. [Eilenberg, Automata, Languages ​​and Machines , vol. A, Academic Press, 1974] для более подробной информации.

2. Вернуться к бесконечным словам

Расширение первого определения не работает, как показано Шаллем в его ответе. И, к сожалению, можно также показать, что универсальное свойство второго определения не распространяется на бесконечные слова, за исключением нескольких частных случаев.

Это конец истории? Подождите секунду, есть еще один минимальный объект, который принимает обычные языки ...

3. Синтаксический подход

Давайте сначала вернемся снова к конечным словам. Напомню , что язык из A * является распознается моноидными М , если существует сюръективен моноид морфизм F : * → М и подмножество Р из М такого , что F - 1 ( Р ) = л . Опять же , существует моноидное M ( L ) , называется синтаксической Моноидом из L , которая распознает L и является фактором всех моноидов распознающих $L$$A^*$ $M$$f:A^* \to M$$P$$M$$f^{-1}(P) = L$$M(L)$$L$$L$$L$, Этот синтаксический моноид может быть определен непосредственно как частное от по синтаксической конгруэнции ∼ L в L , определенной следующим образом: u ∼ L v  тогда и только тогда, когда для всех  x , y ∈ A ∗ ,  x u y ∈ $A^*$ $\sim_L$$L$ Хорошая новость заключается в том, что на этот раз этот подход был распространен на бесконечные слова, но потребовалось много времени, чтобы найти соответствующие понятия. Во-первых, А. Арнольд нашел подходящее понятие синтаксической конгруэнции (Синтаксическая конгруэнция для рациональныхω-языков, Теорет. Вычисл. Sci.39, 2-3 (1985), 333–335). Расширение синтаксических моноидов до набора бесконечных слов потребовало более сложного типа алгебр, называемых в настоящее времяалгебрами Вилкев честь Т. Вилке, который первым их определил (Т. Вилке, Алгебраическая теория для регулярных языков конечных и бесконечных слова,Int. J. Alg. Comput.3

4. Вывод

Таким образом, существует математически обоснованное понятие минимального объекта, принимающего данный регулярный язык, но оно не опирается на автоматы. На самом деле это довольно общий факт: автоматы являются очень мощным алгоритмическим инструментом, но их не всегда достаточно для рассмотрения математических вопросов о языках.$\omega$