Универсальные синхронизирующие и универсальные сжимающие слова

1.1 Синхронизируемость и сжимаемость.

Детерминированным конечным автоматом (или кратко ДКА) мы будем называть тройку srf — (Q, Е, S), где Q — конечное множество состояний, Е — конечный входной алфавит, и 5 — всюду определенная функция переходов, действующая из Q х Е в Q. Действие букв из Е на множество состояний Q, определяемое функцией переходов 5, естественным образом расширяется до действия слов из свободного Е-порожденного моноида Е* с пустым словом епоследнее действие будем также обозначать через 5. Для произвольного слова v е Е* и произвольного RQ Q мы определим действие словом v на множество R следующим образом: S (R, v) = {S (q, v) q 6 .R}. Дефектом действия слова v на автомат назовем dfv (stf) — Q — г>)|.

ДКА = (Q, Е, 5) называется синхронизируемым, если действие некоторого слова w G Е* отображает все состояния этого автомата в некоторое одно состояние, т. е. существует состояние р G Q такое, что для всех состояний q? Q выполняется 5(q, w) = ртакое слово w будем называть синхронизирующим словом для автомата ,<г/.

Рис. 1: Автомат Черни с 4 состояниями.

На рис. 1 представлен пример синхронизируемого автомата. Легко проверить, что любое состояние этого автомата словом ab3ab3a отображается в состояние 2, т. е. слово ab3ab3a является синхронизирующим словом для данного автомата. Отметим, что у любого синхронизируемого автомата существует бесконечно много синхронизирующих слов, так как если мы припишем к синхронизирующему автомат слову в начало и в конец любые слова, то полученное слово по-прежнему будет синхронизировать этот автомат. Оказывается, что слово аЪ3аЪ3а не только является синхронизирующим словом для автомата Черни с 4 состояниями, но еще и кратчайшим с данным свойством.

Что же хорошего в синхронизирующем автомат слове и почему здесь уместно слово 'синхронизация'? Для ответа представим, что мы имеем несколько одинаковых синхронизируемых автоматов, работающих независимо, и пусть каждый из этих автоматов находится в некотором состоянии, причем начальные состояния для разных автоматов могут различаться. Если мы ко всем этим автоматам одновременно применим синхронизирующее их слово, то все они окажутся в одном и том же состоянии — тем самым, дальнейшая работа этих автоматов под действием единого потока сигналов будет синхронизирована. Можно считать, что данное слово выполнило 'сброс' всех этих автоматов в 'начальное' состояние. Другим важным применением синхронизирующего автомат слова является ситуация, когда у нас имеется один синхронизируемый автомат, но мы не знаем, в каком состоянии он находится. Тогда применение синхронизирующего его слова переведет автомат в заранее известное нам состояние. Т. е. синхронизирующее автомат слово позволяет уменьшить неопределенность поведения автомата! Существует множество других применений, некоторые из них описаны в работах [23- 29].

Одним из первых понятие синхронизируемости сформулировал Черни (Сегпу) в 1964 году, в работе [15]. Черни также высказал гипотезу:

Гипотеза 1.1 (Сегпу, 1964). Любой синхронизируемый ДКА srf = (Q, E,<5) может быть синхронизирован словом длины не большей, чем (|(3| — I)2 •.

С тех пор было много попыток доказать или опровергнуть эту так легко формулируемую гипотезу, но ни одна из них не увенчалась успехом. На данный момент гипотеза доказана для многочисленных классов автоматов (см. [5- 14- 19- 21- 34−38]), а в общем случае получена только кубическая верхняя оценка М (см. [1]). Сам же Черни в работе [15] построил бесконечную серию автоматов, кратчайшие синхронизирующие слова которых имеют длину (|<2| — I)2, и доказал тем самым, что данную оценку нельзя понизить.

Первой алгоритмической задачей, связанной с синхронизируемостью, является задача проверки данного автомата srf = (Q, Е, S) на синхронизируе-мость. Оказывается, что можно выполнить эту проверку за время 0(|Е||<5|2), используя 0(Q2) пространства (см. [21]). Для этого необходимо построить автомат на парах = где Q^ = Q х Q,.

М ((р,</),*) = (5(р, a), S (q, a)) V (p, g) 6 Q[2] Va G E.

После этого достаточно рассмотреть пары вида (р, р) и проверить, что из этого множества пар можно, идя по обратным ребрам автомата, достичь все остальные пары. Это условие эквивалентно тому, что любую пару (г, s) состояний автомата sf можно склеить, т. е. подходящим словом v G Е* перевести состояния г и s в некоторое состояние р.

В работе [21] Эпштейн (Eppstein) также показал, что для данного автомата = (Q, Е, 8) можно найти некоторое синхронизирующее слово за время 0(|E||Q|2 + |Q|3). Длина такого слова ^ + 0(Q2).

А как найти кратчайшее синхронизирующее автомат srf — (Q, Е, слово? Для этого используем автомат на подмножествах = (2®, Е, А), где 2® обозначает множество всех подмножеств множества Q, а функция Д: 2*2 х Е —> 2^ определена следующим образом:

Д (М, а) = {5{q, a) q G М} УМ С Q Va 6 Е.

Теперь осталось найти кратчайший путь из множества всех состояний Q в некоторое одноэлементное подмножество. Такой подход дает не самую лучшую оценку на длину кратчайшего синхронизирующего автомат srf слова, а именно 2'°' — |Q| — 1, но все же позволяет найти кратчайшее слово.

Саломаа (Salomaa) [35] и Эпштейн [21] доказали, что задача, в которой для заданного автомата srf и заданного числа L требуется определить, имеет ли автомат srf синхронизирующее слово длины L, является NP-полной. По-другому эту задачу можно сформулировать так: проверить, что кратчайшее синхронизирующее слово для автомата имеет длину, не превосходящую L. Самотий (Samotij) в работе [36] также показал, что задача проверки того, что кратчайшее слово, синхронизирующее автомат имеет длину ровно L, является одновременно iVP-трудной и со — NPтрудной.

Не каждый ДКА может быть синхронизирован, но для каждого ДКА srf = (Q, E,<5) можно указать ранг автомата rk (#/) = min{|?(Q, г>)| v е Е*}. Ранг показывает, какое минимальное количество состояний может получиться в образе множества Q под действием различных словтак, для синхронизируемых автоматов ранг равен 1. Как для синхронизируемых автоматов, так и для несинхронизируемых автоматов можно говорить о сжимаемости. Возьмем произвольное натуральное число п. ДКА srf = (Q, Е, S) называется п-сжимаемым, если найдется такое слово w 6 Е*, что |5(Q, w)| < — и, другими словами, dfw (я/) > п. Такое слово w называется п-сжимающим для автомата я/. Будем также говорить, что слово w сжимает данный автомат j/нап состояний. Ясно, что для любого числа 0 < и < Q — rk (stf) автомат srf является п-сжимаемым.

Проверить, является ли данный автомат srf = (Q, Е, S) п-сжимаемым, можно за время 0(|E||Q|2 + Q3 -InQ2), используя те же идеи, что и в работе Эпштейна [21].

В 1983 году Пэн (Pin) в работе [30] обобщил гипотезу Черни:

Гипотеза 1.2 (Pin, 1983). Любой п-сжилшемый ДКА может быть сжат на п словом длины не большей, чем п2.

Однако, Кари (Kari) в 2000 году опроверг эту гипотезу [24], построив автомат с 6-ю состояниями такой, что кратчайшее сжимающее этот автомат на 4 состояния слово имеет длину 17 = 42+1. Других примеров, опровергающих данную гипотезу, пока не найдено.

Синхронизируемости и ее обобщениям посвящено множество работ, в том числе недавние работы Павла Мартюгина [2−4- 26- 27].

6 Заключение.

В главе 2 показано, что для каждого слова w € Е*, не являющегося универсальным гг-сжимающим словом, найдется автомат-контрпример, имеющий не более 2|ги|(п — 1) + 2 состояний. Таким образом, языки Сп (Е) всех n-сжимающих слов над алфавитом Е являются рекурсивными для всех гг., что обобщает известный ранее результат о рекурсивности языка всех 2-сжимающих слов. Кроме того, из линейности представленной оценки следует, что, во-первых, языки Сп являются контекстными, а, во-вторых, задача распознавания тг-сжимающих слов принадлежит классу сложности co-NP.

В главе 3 определены частичные послойные автоматы (основы), задающие классы полных автоматов, и показано, как, читая проверяемое слово w, можно достраивать частичные послойные автоматы до полных автоматов с целью поиска контрпримера. Также показано, что описанные варианты достраивания приводят к неизоморфным между собой автоматам. Кроме того приведена некоторая статистика времени работы построенного таким образом алгоритма проверки слов на тг-сжимаемость.

Глава 4 содержит описание алгоритмов поиска кратчайших универсальных синхронизирующих и универсальных сжимающих слов, а также описание алгоритма построения некоторых коротких универсальных синхронизирующих слов, строящего пересечения языков и отбрасывающего 'дальние' состояния в распознавателях получающихся пересечений. Кроме того, приведены новые примеры кратчайших и достаточно коротких универсальных синхронизирующих и универсальных сжимающих слов.

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

Автор выражает глубокую благодарность своему научному руководителю Д. С. Ананичеву и профессору М. В. Волкову за помощь в подготовке текстов и внимание к работе.