Содержание к диссертации
Введение
1 Языки синхронизирующих слов медленно синхронизируемых автоматов 31
1.1 Верхняя оценка синхронизационной сложности идеального языка 32
1.2 Синхронизационная и дескриптивная сложность языков синхронизирующих слов медленно синхронизируемых автоматов 34
1.3 Вопрос о единственности МСА 49
2 Главные идеальные языки и синхронизируемые автоматы 52
2.1 Вопрос о единственности МСА в классе сильно связных автоматов 53
2.2 Алгоритм построения сильно связного МСА для главного идеального языка 56
2.3 Доказательство корректности алгоритма 61
2.4 Синхронизационная сложность главного идеального языка 64
2.5 Синтаксическая полугруппа главного идеального языка 66
3 Конечно порожденные идеальные языки и синхронизиру емые автоматы 75
3.1 Идеальный язык, порожденный ТІ1 75
3.2 Идеальный язык, порожденный множеством слов постоянной длины
3.3 Идеальный язык, порожденный конечным множеством слов 81
3.4 Идеальный язык, порожденный двумя словами 83
4 Вычисление синхронизационной сложности идеальных языков 90
4.1 Принадлежность классу PSPACE 91
4.2 PSPACE-полнота 93
5 Представление регулярных языков синхронизируемыми автоматами 108
5.1 Левые факторы главных левых идеальных языков 109
5.2 Регулярные языки и синхронизируемые автоматы 114
Список литературы
- Синхронизационная и дескриптивная сложность языков синхронизирующих слов медленно синхронизируемых автоматов
- Вопрос о единственности МСА
- Алгоритм построения сильно связного МСА для главного идеального языка
- Идеальный язык, порожденный конечным множеством слов
Введение к работе
Актуальность темы. Всюду в данной работе под словом «язык» понимается формальный язык над конечным фиксированным алфавитом Е, т.е. подмножество свободного моноида Е* над Е. Регулярные языки образуют важный класс формальных языков. Особенностью языков этого класса является возможность компактного описания в различных терминах (например, с помощью регулярных выражений, детерминированных автоматов, недетерминированных автоматов и др.). Разные способы описания имеют разные области применения и разную степень компактности, а изучение связи между различными способами составляет одно из наиболее активно развивающихся направлений в теории сложности формальных систем. Отметим, что для некоторых важных подклассов регулярных языков есть особые методы представления, которые учитывают специфику этих классов. Рассмотрим простой пример одного из таких классов. Слово и Є Е+ называется фактором слова w. если w может быть представлено как w = хиу для некоторых ж, у Є Е*. Язык L С Е* является факториалъным^ если L замкнут относительно взятия факторов, т.е. для всякого w Є L все факторы w также принадлежат L. Любой факториальный язык можно описать с помощью антисловаря^ т.е. списка запрещенных факторов. Большую роль в теории и приложениях формальных языков играют факториальные языки с конечным антисловарем (КАС-языки), см. [3]. Естественным объектом, описывающим КАС-язык, является антисловарь этого языка. Другой важный класс составляют идеальные языки. Напомним, что язык /СЕ* называется двусторонним идеалом^ если / непустой и Е*/Е* С /. Говоря «идеальный язык», или коротко «идеал», мы будем подразумевать, что рассматривается двусторонний идеальный язык. Понятие двустороннего идеала занимает центральное место в теории полугрупп [2]. Идеальные языки как двусторонние идеалы в свободном моноиде Е* активно изучаются в связи с различными приложениями в компьютерных науках на протяжении последних пятидесяти лет [6,10]. Нетрудно проверить, что язык L С Е* является факториалъным тогда и только тогда, когда его дополнение Е* \ L - идеал в Е*. Таким образом, факториальные языки суть в точности дополнения идеальных языков. Идеальные языки возникают также в задачах, связанных с поиском подстроки в строке [8]. Формально поиск в тексте w слова из L С Е* эквивалентен поиску факторов ги, принадлежащих языку E*LE*, который является двусторонним идеалом.
В связи с различными практическими и теоретическими приложениями представляет интерес нахождение объекта для компактного представления идеальных языков. В результате поиска такого объекта возникла идея представления идеальных языков с помощью синхронизируемых автоматов. Автоматы из этого класса можно рассматривать как своеобразные «распознаватели» идеальных языков. Точный смысл этой идее мы придадим чуть позже, а сейчас зафиксируем некоторые определения. Детерминированным конечным автоматом (ДКА) называется тройка я/ = (Q, , ), где Q - конечное множество состояний, Е - конечный входной алфавит, а 5: Q х Е —>> Q - всюду определенная функция переходов. Отметим, что в теории формальных языков к набору данных, определяющему конечный детерминированный автомат, обычно добавляют выделенное начальное состояние qo Є Q я множество F заключительных (или конечных) состояний. Мы также будем пользоваться этим вариантом определения и писать srf = (Q, Е, 5, go, F), когда речь будет идти о языках, распознаваемых автоматами. Для заданного ДКА я/ = (Q, Е, 5, go, F) положим L\pf\ = {w \ S(qo,w) Є F}, при этом будем говорить, что язык L\sf\ принимается (или распознается) автоматом srf. Язык называется регулярным, если он распознается некоторым детерминированным конечным автоматом. В дальнейшем будут рассматриваться только регулярные языки, поэтому для краткости будем опускать термин «регулярный», предполагая, что речь идет именно о таких языках. Всюду ниже будем использовать слово «автомат» в качестве синонима термина «детерминированный конечный автомат». Рассмотрим автомат srf с множеством состояний Q и функцией переходов 5: Q х Е —>> Q, задающей действие букв из заданного алфавита Е на состояния из Q. Автомат srf называется синхронизируемым, если найдется слово w над алфавитом Е, под действием которого все состояния переходят в одно: S(q, w) = 5(q', w) для всех q, qf Є Q. Всякое такое слово w называется синхронизирующим для я/. Таким образом, если исходное состояние автомата неизвестно, то после прочтения синхронизирующего слова его состояние будет однозначно определено. В качестве примера рассмотрим автомат «й^ с четырьмя состояниями, приведенный на рис. 1. Этот автомат синхронизируемый, поскольку слово w = aba переводит каждое состояние в 3.
Синхронизируемые автоматы представляют собой простую и естественную модель систем, устойчивых к ошибкам. Такие автоматы используются во многих прикладных областях (тестирование систем и
Рис. 1: Автомат ^
протоколов, кодирование информации, роботика, биоинформатика), а также возникают в некоторых разделах фундаментальной математики (символическая динамика, теория подстановочных систем). Основы теории синхронизируемых автоматов и их приложения в упомянутых областях обсуждаются довольно подробно в обзоре [20].
С точки зрения приложений важным параметром является длина синхронизирующего слова. Минимум длин синхронизирующих слов автомата srf называется его порогом синхронизации. Для краткости будем называть автомат с п состояниями п-автоматом. В 1964 году Черни [7] построил для каждого п > 1 синхронизируемый п-автомат над двухбук-венным алфавитом с порогом синхронизации (п — I)2. Позднее Черни высказал предположение, что автоматы из этой серии реализуют наихудший случай, т.е. что всякий синхронизируемый п-автомат обладает синхронизирующим словом длины не более (п — I)2. Это предположение получило название гипотезы Черни. Несмотря на простоту формулировки и усилия многочисленных исследователей, гипотеза Черни остается не доказанной и не опровергнутой уже более 50 лет.
Пусть srf - синхронизируемый автомат с входным алфавитом Е. Обозначим через Syn(^) множество всех синхронизирующих слов для автомата &/. Язык всех слов, синхронизирующих «й^, образует регулярный идеал в Е*. С другой стороны, справедливо и обратное утверждение: если / - произвольный регулярный идеал в Е*, то найдется синхронизируемый автомат srf с входным алфавитом Е, для которого / будет множеством синхронизирующих слов. Этот автомат можно использовать как своеобразный распознаватель языка / - для того, чтобы проверить, принадлежит ли какое-то слово w Є Е* языку /, достаточно применить w к каждому состоянию ДКА srf и сравнить получающиеся состояния: w Є I тогда и только тогда, когда все эти состояния совпадают. Таким образом, автомат srf можно рассматривать как сжатое представление языка /. В качестве меры сложности такого представления определим
новую характеристику регулярного языка, являющегося идеалом, связанную с его описанием посредством синхронизируемых автоматов. А именно, синхронизационной сложностью (кратко синхр о сложностью) гс{1) идеального языка / назовем минимальное возможное число состояний в синхронизируемом автомате, для которого / будет множеством синхронизирующих слов. Всякий синхронизируемый автомат, на котором достигается значение синхронизационной сложности идеального языка /, будем называть минимальным синхронизируемым автоматом (кратко МСА) для /.
Отметим, что одной из основных мер описательной сложности регулярных языков является число состояний в минимальном детерминированном конечном автомате, распознающем язык. Эта мера сложности называется дескриптивной сложностью регулярного языка. Изучению этой характеристики регулярных языков и ее поведению при различных операциях над языками посвящено множество работ, см., например, [5,6,19]. Дескриптивную сложность регулярного языка L будем обозначать через sc(L). В рамках общего подхода к изучению различных мер сложности формальных языков возникает группа следующих естественных вопросов.
Как соотносятся между собой синхронизационная и дескриптивная сложность идеального языка?
Определяется ли МСА для заданного идеального языка единственным образом?
Как построить МСА для заданного языка по некоторому его конструктивному представлению (например, по минимальному детерминированному автомату, распознающему язык)?
Существует ли эффективный алгоритм проверки того, что заданный автомат является МСА для заданного языка?
Насколько сложно проверить неравенство гс{1) < для заданного натурального Р.
Систематическому изучению этих вопросов и посвящается диссертация. Обозначим через s^i, минимальный детерминированный автомат, распознающий регулярный язык L. Нетрудно проверить, что для всякого идеального языка / имеет место равенство Syn(^) = /. Это означает,
что синхронизационная сложность произвольного идеального языка / не превосходит его дескриптивной сложности, т.е. гс{1) < sc(I). Теперь возникает естественным образом следующая задача.
Задача 1. Выяснить, насколько большой может быть разность между дескриптивной и синхронизационной сложностью идеального языка.
В диссертации показано, что дескриптивная сложность идеального языка может быть экспоненциально больше синхронизационной сложности. Это означает, что для идеального языка представление посредством синхронизируемого автомата может быть значительно компактнее представления с помощью минимального детерминированного автомата. Из теории формальных языков известно, что недетерминированный автомат, распознающий регулярный язык, также может дать экспоненциальную экономию памяти по сравнению с минимальным детерминированным автоматом для этого языка [11]. Кроме того, для данного регулярного языка недетерминированный автомат с минимальным возможным числом состояний, распознающий этот язык, строится неоднозначно. Оказывается, что для идеального языка также нельзя однозначно восстановить МСА. Далее аналогия между синхронизируемыми детерминированными автоматами и недетерминированными автоматами как объектами для представления языков снова возникнет при определении класса сложности задачи проверки равенства идеальных языков, заданных синхронизируемыми автоматами. Оказывается, что эта задача принадлежит тому же классу сложности, что и задача проверки равенства языков, распознаваемых двумя данными недетерминированными автоматами. Таким образом, можно утверждать, что представление идеального языка посредством синхронизируемого автомата сопоставимо с представлением регулярного языка недетерминированным автоматом в том смысле, что наиболее естественные вопросы, связанные с изучением этих представлений, имеют одни и те же ответы.
Поскольку ответ на вопрос о единственности МСА для заданного идеального языка отрицательный, то возникает следующий вопрос. В каком подклассе синхронизируемых автоматов стоит искать МСА для заданного идеального языка? Классическим подходом в теории синхронизируемых автоматов является рассмотрение двух основных классов: автоматов с нулем и сильно связных автоматов. Выбор этих двух классов обусловлен тем, что для доказательства гипотезы Черни необходимо и достаточно установить ее справедливость в классе автоматов с нулем и в классе сильно связных автоматов [21]. Говорят, что ДКА srf яв-
ляется автоматом с нулем^ если некоторое его состояние переводится всеми буквами алфавита в себя. В классе автоматов с нулем гипотеза Черни верна [18]. Напомним, что автомат srf с множеством состояний Q и функцией переходов 5 называется сильно связным^ если его орграф сильно связен, т.е., другими словами, для всякой пары состояний p,q Є Q найдется слово w1 для которого 6(р, w) = q. В связи с изучением порога синхронизации сильно связных автоматов возникает следующий естественный вопрос: для всякого ли идеального языка / существует сильно связный синхронизируемый автомат вё такой, что Syn(^) = II Отметим, что задача построения сильно связного синхронизируемого автомата ^, в котором Syn(^) = /, нетривиальна. Рейш и Родаро в [17] доказали, что такой автомат вё можно построить для всякого идеального языка / над алфавитом Е, содержащим хотя бы две буквы. Конструкция из [17] сложная с технической точки зрения и дает очень грубую оценку на число состояний в соответствующем сильно связном автомате. Более того, компьютерные эксперименты дают основание предполагать, что эта оценка далека от оптимальной. В связи с этим актуальна следующая задача.
Задача 2. Разработать алгоритм построения сильно связного синхронизируемого автомата с минимальным возможным числом состояний, для которого данный язык является языком синхронизирующих слов.
Предположим теперь, что идеальный язык / задан некоторым синхронизируемым автоматом «й^, язык синхронизирующих слов которого совпадает с /. Пусть гс{1) = п. Последнее равенство означает, что существует синхронизируемый n-автомат вё такой, что Syn(^) = Syn(^) = /, причем вё является минимальным синхронизируемым автоматом для /. Возникает следующий вопрос: насколько сложно проверить равенство языков синхронизирующих слов двух данных автоматов? Как следствие возникает вопрос о классе вычислительной сложности задачи проверки неравенства гс{1) < , где / - язык синхронизирующих слов заданного синхронизируемого автомата - фиксированное натуральное число. Таким образом, представляет интерес решение следующих задач.
Задача 3. Определить класс вычислительной сложности задачи SYN-EQUALITY:
УСЛОВИЕ. Заданы синхронизируемые автоматы srf и вё. ВОПРОС. Верно ли, что Syn(^) = Syn(^)?
Задача 4. Определить класс вычислительной сложности задачи
RESET-INEQUALITY:
УСЛОВИЕ. Заданы синхронизируемый автомат srf и число І Є N.
ВОПРОС. Верно ли, что гс(1) < , где I = Syn(^)?
Пусть дан ДКА я/ = (Q, Е, , до, і"1), распознающий некоторый регулярный язык L. Будем говорить, что srf является синхронизируемым, если таковым является ДКА stf' = (Q, Е, 5). Нетрудно найти множество состояний S С Q, в которые можно синхронизировать srf. Это множество определяется следующим образом: q Є S тогда и только тогда, когда 5(Q, w) = {q} для некоторого w Є Е*.
Если S = F^ то з/ - синхронизируемый ДКА, причем имеет место равенство Syn(j2/) = L\sf\. Предположим теперь, что S ^ F и 5 ^ 0-Возникает вопрос, какую структуру должен иметь язык L, чтобы минимальный автомат, распознающий L, был синхронизируемым? Несложно привести пример, подтверждающий, что класс языков с таким свойством не совпадает с классом всех регулярных языков. Таким образом, представляет интерес решение следующей задачи.
Задача 5. Описать класс языков, распознаваемых синхронизируемыми автоматами.
Актуальность задачи 5 можно объяснить тем фактом, что синхронизирующие слова для автомата, распознающего данный регулярный язык, являются константами этого языка. Константы регулярных языков имеют приложение в биоинформатике в связи с изучением языков сплетения. В частности, в недавней работе Бонницони и Ионошки [4] было показано, что всякий регулярный язык сплетения должен иметь константу. В свою очередь, теоретические результаты, устанавливающие те или иные свойства языков сплетения, играют важную роль в развитии области теории формальных языков, связанной с моделированием биохимических процессов [12].
Целью работы является решение поставленных выше задач 1-5.
Методы исследования. В работе применяются методы комбинаторики слов, теории автоматов, комбинаторных алгоритмов, теории сложности вычислений и теории формальных языков.
Научная новизна. Все результаты диссертации являются новыми.
Теоретическая и практическая ценность. Диссертационная
работа носит теоретический характер. Полученные результаты могут быть использованы в дальнейших исследованиях по синхронизируемым автоматам, в теории сложности формальных систем, теории формальных языков и при чтении специальных курсов для студентов математических специальностей. Ссылки на результаты диссертации присутствуют в работах других авторов: [9,16,17].
Апробация результатов работы. Результаты диссертации докладывались на 38-й международной конференции по современным направлениям в теории и практике компьютерных наук SOFSEM 2012 (Шпиндлерув Млын, Чехия, 2012), 2-м российско-финском симпозиуме по дискретной математике RuFiDiM (Турку, Финляндия, 2012), 6-й научной школе по компьютерным наукам CSEDays 2013 (Екатеринбург, 2013), 9-й международной конференции по комбинаторике слов WORDS 2013 (Турку, Финляндия, 2013), 7-й научной школе по компьютерным наукам CSEDays 2014 (Екатеринбург, 2014), 16-м международном семинаре по описательной сложности формальных систем DCFS 2014 (Турку, Финляндия, 2014), 3-м российско-финском симпозиуме по дискретной математике RuFiDiM (Петрозаводск, 2014), 46-й молодежной школе-конференции «Современные проблемы математики и ее приложений» (Екатеринбург, 2015), 10-й международной конференции по компьютерным наукам CSR 2015 (Листвянка, 2015) на заседаниях семинара «Теоретические компьютерные науки» под рук. М. В. Волкова и семинара «Алгебраические системы» под рук. Л. Н. Шеврина (Екатеринбург, 2012-2015).
Публикации. По теме диссертации опубликовано 10 работ [22] [31]. Из них 4 работы опубликованы в ведущих изданиях, входящих в список ВАК [22] [25]. В работе [22] идея конструкций из теорем 1 и 2 принадлежит Е.В. Прибавкиной, идея конструкции из теоремы 3 принадлежит В.В. Гусеву. Общая схема исследования и доказательства утверждений принадлежат диссертанту. В работе [23] идея алгоритма построения сильно связного автомата принадлежит Е.В. Прибавкиной, предложение 4.1 и идея доказательства теоремы 4.2 принадлежат В.В. Гусеву. Реализация вычислительных экспериментов и доказательства основных утверждений принадлежат диссертанту. Доказательства основных результатов работы [24] при подготовке текста диссертации были качественно улучшены, что позволило, в частности, получить новые,
более сильные, результаты о сложности задачи RESET-INEQUALITY. В совместной работе [25] с Э. Родаро идея доказательства теоремы 5 и основные результаты параграфа 3 принадлежат Э. Родаро, доказательство теоремы 5 и все результаты параграфов 4 и 5 принадлежат диссертанту. Для полноты изложения в диссертации сформулированы без
, полученные 28] представ-
доказательства некоторые результаты параграфа 3 из [25 Э. Родаро. Работы [26], [28] [31] являются тезисами. В лен основной результат опубликованной позднее статьи [22], а также некоторые другие результаты, полученные диссертантом. В тезисах [31] опубликованы без доказательств некоторые результаты, полученные Э. Родаро, связанные с развитием нового подхода к гипотезе Черни, а также сформулированы утверждения, полученные диссертантом, описывающие свойства множества констант регулярного языка.
Структура и объем диссертации. Диссертация состоит из введения, пяти глав и списка литературы. Объем диссертации составляет 125 страниц. Библиографический список содержит 68 наименований.
Синхронизационная и дескриптивная сложность языков синхронизирующих слов медленно синхронизируемых автоматов
Этот список результатов далеко не полный, однако результаты такого рода представляют и самостоятельный интерес, поскольку позволяют выяснить, как влияет то или иное свойство синхронизируемого автомата на длину его кратчайшего синхронизирующего слова. С другой стороны, в результате рассмотрения специальных классов синхронизируемых автоматов иногда удается установить связь между автоматами и объектами другой природы, что может оказаться полезным в соответствующих областях фундаментальной математики. Остановимся чуть подробнее на примере одной из таких связей. ДКА srf = (Q, Е, 6) называется автоматом с нулем, если существует состояние s Є Q, которое переводится всеми буквами алфавита Е в себя. Известно, что длина кратчайшего синхронизирующего слова для произвольного n-автомата с нулем не превосходит —Ц —- [56]. Более того, в [56] для каждого п построен синхронизируемый n-автомат с нулем, для которого кратчайшее синхронизирующее слово имеет длину —Ц —-. Таким образом, в классе автоматов с нулем гипотеза Черни верна. С другой стороны, в работе [5] для произвольного алфавита Е, содержащего хотя бы две буквы, и произвольного к Е построен синхронизируемый автомат с нулем с п = 2к состояниями над алфавитом Е, порог синхронизации которого равен \ + Ц — 1. Соответствующая конструкция из [5] была получена в результате анализа взаимосвязей между синхронизируемыми автоматами с нулем и непокрывающими множествами в свободных моноидах. В свою очередь, покрывающие и непокрываю-щие множества в свободных моноидах играют важную роль в теории кодов и комбинаторике слов в связи с понятием максимальных кодов [55].
Напомним, что язык /СЕ называется двусторонним идеалом, (или просто идеалом), если / непустой и Е /Е С /. Язык /СЕ называется левым, (соответственно, правым) идеалом, если / непустой и Е / С / (соответственно, /Е С /). В данной работе рассматриваются только регулярные языки, поэтому для краткости мы будем опускать термин "регулярный", предполагая, что речь идет именно о таком языке. Говоря "идеальный язык", или коротко "идеал", мы будем подразумевать, что рассматривается двусторонний идеальный язык.
Понятие двустороннего идеала занимает центральное место в теории полугрупп [4]. Идеальные языки как двусторонние идеалы в свободном моноиде Е активно изучаются в связи с различными приложениями в компьютерных науках на протяжении последних пятидесяти лет [14,26,44]. Нетрудно проверить, что язык L С Е является факториалъным (т.е. замкнутым относительно взя тия факторов) тогда и только тогда, когда его дополнение Е \L - идеал вЕ . Таким образом, факториальные языки суть в точности дополнения идеальных языков. Любой факториальный язык молено описать с помощью антисловаря, т.е. списка запрещенных факторов. Большую роль в теории и приложениях формальных языков играют факториальные языки с конечным антисловарем (КАС-языки), см., например, [6]. КАС-языки регулярны и являются в точности дополнениями конечно порожденных идеальных языков, т.е. языков вида E -wiE U ... U Е г%Е , где W\,... ,Wk - слова над алфавитом Е. В свою очередь, конечно порожденные идеальные языки как языки синхронизирующих слов автоматов изучались в цикле совместных работ Прибавкиной и Родаро, см. [48] - [51]. Идеальные языки (из различных классов) возникают также в задачах, связанных с поиском подстроки в строке. Например, пусть текст задан словом w над некоторым алфавитом Е. Заданным шаблоном может быть как конечное множество слов, так и произвольный язык L над Е, представленный регулярным выражением. Появлением шаблона, задаваемого языком L, в тексте w называется тройка (u,x,v) такая, что w = uxv, где х Є L. Таким образом, поиск в тексте w слова из L эквивалентен поиску префиксов w, принадлежащих языку E L, который является левым идеалом, порожденным L [22]. Задачу поиска всех появлений слов из конечного множества L в заданном тексте w можно решить с помощью алгоритма Ахо-Корасик [7]. Еще один пример применения идеальных языков в задачах поиска в тексте по шаблону можно найти в недавней работе [67], где рассматривается задача просмотра и обработки с высокой скоростью пакетов данных, передаваемых по каналам связи.
В связи с различными практическими и теоретическими приложениями представляет интерес нахождение объекта для компактного представления идеальных языков. В диссертации идеальные языки изучаются с точки зрения теории автоматов. Пусть srf - синхронизируемый автомат с входным алфавитом Е. Язык всех слов, синхронизирующих ,$/, образует регулярный идеал в Е . С другой стороны, несложно проверить, что справедливо и обратное утверждение: если / - произвольный регулярный идеал в Е , то найдется синхронизируемый автомат stf с входным алфавитом Е, для которого / будет множеством синхронизирующих слов. Этот автомат можно использовать как своеобразный распознаватель языка / - для того, чтобы проверить, принадлежит ли какое-то слово w Є Е языку /, достаточно применить w к каждому состоянию ДКА stf и сравнить получающиеся состояния: w Є I тогда и только тогда, когда все эти состояния совпадают. Ясно, что описанная проверка занимает 0(гу IQI) времени, где Q - множество состояний stf. Таким образом, автомат stf можно рассматривать как сжатое представление языка /. Одной из основных мер описательной сложности регулярных языков является чис ло состояний в минимальном детерминированном конечном автомате, распознающем язык. Эта мера сложности называется дескриптивной сложностью регулярного языка. Изучению этой характеристики регулярных языков и ее поведению при различных операциях над языками посвящено множество работ (см., например, [15] - [18] и [68]). Эта характеристика регулярных языков удобна при их изучении в связи с реализацией различных алгоритмов. Дескриптивную сложность регулярного языка L будем обозначать через sc{L). В литературе рассматриваются и другие меры сложности представления регулярных языков: недетерминированная сложность, синтаксическая сложность и др. Мы вводим в рассмотрение новую меру сложности регулярных языков, являющихся идеалами, связанную с их представлением посредством синхронизируемых автоматов. А именно, синхронизационной сложностью (кратко син-хросложностъю) гс{1) идеального языка / назовем минимальное возможное число состояний в синхронизируемом автомате, для которого / будет множеством синхронизирующих слов. Всякий синхронизируемый автомат, на котором достигается значение синхронизационной сложности идеального языка /, будем называть минимальным синхронизируемым автоматом (кратко МСА) для /. Обозначим через ,$/L минимальный автомат распознающий регулярный язык L. Нетрудно проверить, что для всякого идеального языка / имеет место равенство Syn(Ig /) = /. Это означает, что синхронизационная сложность произвольного идеального языка / не превосходит его дескриптивной сложности, т.е. гс(1) sc(I). С другой стороны, в первой главе мы покажем, что для всякого натурального п 3 существует идеальный язык 1п такой, что гс(1п) = п и sc(In) = 2п — п. В частности, для языка синхронизиурющих слов n-автомата Черни [20], изображенного на рис. 4, имеют место равенства rc(Syn( ra)) = п и sc(Syn( ra)) = 2п — п при любом п 1. Отметим, что все рассматриваемые языки, дескриптивная сложность которых экспоненциально больше синхросложности, являются языками синхронизирующих слов медленно синхронизируемых n-автоматов, т.е. автоматов с порогом синхронизации близким к (п — 1) . Известные на данный момент серии медленно синхронизируемых автоматов приведены в [8].
Итак, представление идеального языка посредством синхронизируемого автомата может быть значительно компактнее представления с помощью минимального автомата, распознающего язык. В связи с этим в дальнейшем было бы интересно сравнить представление языка с помощью синхронизируемого автомата с другим известным компактным представлением языков — представлением с помощью недетерминированного автомата (оно тоже может дать экспоненциальный выигрыш по памяти по сравнению с представлением с помощью минимального автомата, см., например, [38]).
Вопрос о единственности МСА
Всюду в данной главе будем предполагать, что входной алфавит содержит хотя бы две буквы (если явно не сказано, что рассматривается однобуквенный алфавит). В первой главе мы показали, что для всякого идеала / имеет место неравенство гс{1) sc{I). С другой стороны, синхронизационную сложность идеального языка / можно оценить сверху через значение rdc(I), которое определяется как наименьшее возможное число состояний в сильно связном автомате, для которого данный язык является языком синхронизирующих слов. В самом деле, неравенство rc(I) rdc(I) верно для всякого идеала І. В теории синхронизируемых автоматов класс сильно связных автоматов представляет особый интерес в связи с гипотезой Черни. В частности, гипотеза Черни верна тогда и только тогда, когда rdc(I) y/\\I\\ + 1 для всякого идеального языка І. В связи с этим естественно поставить задачу вычисления значения rdc(I) по различным конструктивным представлениям языка /, например, по минимальному автомату, распознающему /. В данной главе мы рассматриваем класс главных идеальных языков, т.е. языков вида Х ІУХ , где w Є . Мы приводим эффективный алгоритм построения сильно связного синхронизируемого автомата 8$ с гу + 1 состоянием, язык синхронизирующих слов которого совпадает с Iw = Х ІУХ . Далее мы доказываем, что синхронизационная сложность главного идеала Iw, порожденного словом w, равна гу + 1. Таким образом, значение синхронизационной сложности всякого главного идеального языка достигается на некотором сильно связном автомате.
Оказывается, что даже для главного идеального языка сильно связный синхронизируемый автомат с минимальным возможным числом состояний, для которого данный язык является языком синхронизирующих слов, строится неоднозначно. В то же время с помощью компьютерного эксперимента удалось обнаружить, что полугруппы переходов сильно связных МСА для главного идеального языка, порожденного одним и тем же словом, имеют похожую алгебраическую структуру. В связи с этим мы начинаем изучать подробнее структуру синтаксической полугруппы идеального языка и полугруппы переходов автомата, для которого этот язык является языком синхронизирующих слов. Мы устанавливаем, что синтаксическая полугруппа идеального языка / является гомоморфным образом полугруппы переходов S{8) синхронизируемого автомата 8ё, в котором Syn(« ) = /. Это означает, что если полугруппа переходов ДКА Зё, для которого язык / является языком синхронизирующих слов, обладает некоторым свойством, которое сохраняется при гомоморфизме, то и синтаксическая полугруппа / обладает тем же свойством. Поэтому интересно изучить синтаксическую полугруппу идеального языка. Мы находим в данной главе простую формулу для вычисления порядка синтаксической полугруппы главного идеального языка.
Пусть п 1, рассмотрим язык In = Е ага_1&Е над алфавитом Е = {а, Ь}. В примере 1.3 мы показали, что гс(1п) = п + 1 для всякого п Є N. Теперь мы строим для каждого п 1 два различных сильно связных синхронизируемых автомата /п+1 и п+i с п + 1 состоянием над алфавитом Е = {а, Ь}, для которых язык 1п является языком синхронизирующих слов. В качестве примера соответствующие автоматы с шестью состояниями, & и Зё, изображены на рис. 15.
Заметим, что автомат s n+i сильно связен. Действительно, состояния 1. 2, ..., п образуют цикл, помеченный словом ап 1Ь, т.е. 1. аг = 1 + г для всякого 0 г пип.Ь = 1. Кроме того О.Ь = 1и1.Ь = 0. Теперь нужно проверить, что язык синхронизирующих слов ДКА J n+i совпадает с Е ага_16Е . Воспользуемся стандартным алгоритмом нахождения синхронизирующих слов для данного автомата fn+i с помощью его автомата подмножеств V(fn+i)- Рассмотрим соответствующий модифицированный автомат V -i n+i) с уникальным нулевым состоянием s, распознающий язык Syn(Ig4i__i). На рис. 16 изображен ДКА V{.i n i) (для удобства восприятия показаны только достижимые из Q подмножества). Анализируя структуру V (fn+i), легко проверить, что Syn( 4+i) = S ara"16S .
Действительно, состояния 1, 2, ..., п образуют цикл, помеченный словом ап 1Ь, т.е. 1. аг = 1 + г для всякого 0 г п и п .Ъ = 1. Кроме того 0.а = 1и1.Ь = 0. Для всякого нечетного п 1 автоматы !% n-\-i и =2 1-1-1 не являются изоморфными, поскольку в автомате =2 1+1, в отличие от ё%п 1, есть два различных состояния, которые переводятся одной и той же буквой в себя. Модифицированный автомат подмножеств V\ 2k) изображен на рис. 17 слева (снова для удобства восприятия показаны только достижимые из Q подмножества). Анализируя структуру V\9c 2k)i легко проверить, что Syn( 2fc) = S a2fc_26S для всякого к 1.
Осталось построить для каждого четного п = 2к сильно связный автомат Зёп+\ с 2к + 1 состоянием, для которого Syn( 2fc+i) = S a2fc_16S . Множеством состояний Ш п-\-1 является Q = {0,1,... ,п}, действие букв алфавита на состояния $п+1 задается функцией переходов 7, определенной следующим образом:
Предложение 2.1. Для всякого п 1 существуют два различных сильно связных синхронизируемых п + 1-автомата .s$n+i и ёп+\ над Е = {а, Ъ}, язык синхронизирующих слов каждого из которых совпадает с I = Е ага_16Е . 2.2 Алгоритм построения сильно связного МСА для главного идеального языка
Зафиксируем главный идеал Iw = Е ІУЕ , где w Є Е+ и E 1. В этом разделе мы описываем алгоритм построения сильно связного синхронизируемого автомата с гу + 1 состоянием, язык синхронизирующих слов которого совпадает с Iw. Основная идея алгоритма следующая. Мы попытаемся построить сильно связный автомат, в автомате пар которого найдется подавтомат, изоморфный минимальному ДКA s$jw, распознающему Iw.
Для простоты мы приводим конструкцию требуемого автомата только для двухбуквенного алфавита Е = {а, Ь}. Однако алгоритм применим и в общем случае, когда входной алфавит содержит больше двух букв. Пусть w Є Е+. Без ограничения общности будем считать, что w[l] = а. Для произвольной буквы х Є {а, Ь} обозначим через х комплементарную к ней букву, т.е. а = Ъ и 6 = а. Всюду в данном разделе будем предполагать, что ги 1 (для слова w длины 1 требуемый автомат с двумя состояниями строится очевидным образом).
Напомним классическую конструкцию минимального автомата s$jw , распознающего язык Iw = Е ІУЕ . ИЗ теории формальных языков известно, что этот автомат имеет iy + 1 состояние. Множество состояний P{w) содержит все возможные префиксы w (в том числе, пустое слово є и само слово w). Для всякого 0 г гу — 1 действие произвольной буквы х Є Е на состояние ги[1..г] определяется равенством
Алгоритм построения сильно связного МСА для главного идеального языка
Рассмотрим множество всех листьев Н = Q\Q.a = {р\,Р2, , &} Поскольку ДКА с сильно связный, для любого состояния р из Н существует состояние qi такое, что q .b = рц. Поэтому Н С Q. Ь. Мы покажем, что на самом деле Н в точности совпадает с Q. Ъ. Берем лист высоты п. Без ограничения общности, будем считать, что таким листом оказалось состояние р\. Найдем состояние q\, для которого имеет место равенство q\. Ъ = р\ (если таких состояний несколько, то выбираем любое из них). Слово Ъап является синхронизирующим для , т.е. Q .bda l = {q} для некоторого q Є Q. Тогда q = qi. bda l = p\. da l и q .a = s (см. рис. 27). Заметим, что q ф s, поскольку h(j i) = п и pi .da l = q. Предположим, что найдется р Є Q .а П Q .Ъ. Так как р не является листом, то существует состояние q такое, что q .Ь = р. Кроме того, h(p) п. Тогда q.bda l = p.da l = s ф q, получили противоречие с тем, что Ъаа 1 Є Syn( ). Следовательно, Q. а П Q. Ъ = 0. Тем самым мы получаем равенство Н = Q .Ъ. Кроме того, высота каждого листа ri a равна п. Для проверки этого утверждения предположим, рассуждая от противного, что существует лист рт, высота которого меньше п, т.е. h(pm) п. Это означает, что рт .a=s для некоторого п, например, в качестве такого числа можно взять h(pm). Тогда слово Ъаа 1 не будет синхронизирующим для Чд . В самом деле, возьмем состояние qm такое, что qm .Ъ = рт. Получаем, что qm. ban l = рт . an l = s ф q. Возьмем произвольное состояние р Є Q .а. Положим
Покажем, что -1(р, а)\ 2 для всякого р Є Q .а. Для корня s имеем включение {s, q} С 5 1(s, а), поэтому \5 1(s, а)\ 2. Пусть р- произвольное состояние из Q. а. Тогда р не является листом. В силу сильной связности с получаем, что существуют состояние р и слово w Є Ега с w[n] = а такие, что р . w = р. Так как w Є , имеет место равенство Q.w = {р}. Рассмотрим слово w[l..n — 1]. которое не является синхронизирующим для %f, т.е. имеет место неравенство Q.w[l..n — 1] 2. Однако (Q.w[l..n — l]).w[n] = {р}. Таким образом, получаем неравенство \5 (р, а)\ 2. Полож;им Но = {q} и построим множ;е-ства Hi = 8 1(Hi_i,a)J где 1 г п — 1. Получаем, что \НІ\ 2г для всех 1 і п — 1. Тогда crf имеет не меньше 1 + 1 + 2 + 4+... + 2ra_1 = 2п состояний. Итак, мы показали, что \Q\ = 2п. Более того, Q = U Q .w. Из этих ра \w\=n венств следует, что всякому состоянию q из Q мож;но поставить в соответствие однозначно определенное слово w длины п таким образом, что Q .w = {q}. Ясно, что это отображение является изоморфизмом между с и 8$. Замечание 3.1. Если Е = {a, b} U А, где А ф 0, мы снова строим автомат де Брэйна её = (Q, {а, Ь}, 5) над двухбуквенным алфавитом {а, Ь}, затем полагаем 5(и, с) = 5(и, а) для всех и Є Q и с Є А. Таким образом, мы получаем сильно связный автомат с 2п состояниями над алфавитом Е. Ясно, что этот автомат синхронизируемый и язык синхронизирующих его слов совпадает с Е- .
Из теоремы 3.1 следует, что минимальный автомат, распознающий идеальный язык /, и МСА для / могут быть экспоненциально меньше сильно связного синхронизируемого автомата 8$ с минимальным возможным числом состояний, для которого Syn(8) = I. Так например, для In = Е-га получаем равенства sc(In) = rc(In) = п + 1 и rdc(In) = 2п. В частности, это означает, что значение синхронизационной сложности идеального языка, в общем случае, не достигается на сильно связном автомате.
Доказательство. Чтобы построить требуемый автомат 8и, мы модифицируем автомат де Брэйна 8$, который был описан в предыдущем параграфе. В данном параграфе нам будет удобно представлять каждое состояние автомата SS не как слово длины п, а как пару (х, и), где х Є Е и и Є Ега_1. Тогда по определению функции переходов в 8$ получаем, что пара-состояние (х, и) переходит в пару-состояние (z, v) под действием у Є Е тогда и только тогда, когда иу = zv. Формально это можно записать следующим образом: (х, и) — (z, v) =Ї иу = zv. (6)
Теперь мы построим автомат 8и, который получается из автомата де Брэйна 3$ переопределением функции переходов лишь на таких упорядоченных парах ((ж,и), у), для которых иу [/. Для всякого состояния (х,и) автомата SS% и всякой буквы у Є Е возможен ровно один из следующих случаев.
Случай 1: иу Є U. Положим (х,и) — (z,v), где иу = zv, т.е. действие буквы у на {х, и) определяется в этом случае так же, как и в 8$.
В качестве примера, конструкции автомата де Брэйна 8$ для п = 3 и соответствующего автомата «5% для множества U = {ааа, abb, bab} приведены на рис. 28 и рис. 29 соответственно.
Докажем, что построенный автомат 8и сильно связный. Для этого мы покажем, что всякое состояние (х, и) в 8и достижимо из (а, а"--1), и (а, а"--1) достижимо из всякого состояния 8$и. Сначала проверим, что состояние (а, и) достижимо из (а, ап 1) при любом и Є Xті-1. Если и = da l, утверждение, очевидно, верно. Поэтому можно считать, что и = акЪй, где 0 к п — 2, и Є Yln-k-2. По определению функции переходов в 8и получаем
Теперь мы проверим, что состояние (а,ап ) достижимо из любого другого состояния. Применим слово ап к произвольному состоянию (х, и). По определению функции переходов в 8и мы имеем (х, и). ап 1 Є {(а, ап 1), {Ъ, а"--1)}. Если (х, и) . ara_1 = (а, а"--1), то требуемое утверждение доказано. Если оказалось, что (х, и). ап 1 = {Ъ, ап 1), тогда применим к (6, ап 1) букву а и получим (х, и). ап = (а, а"--1). Стало быть, (а, а"--1) достижимо из произвольного состояния {х,и). Тем самым, мы завершаем доказательство сильной связности &и. Далее мы покажем, что Syn( {/) = Е [/Е . Легко видеть, что для всякого слова и Є Ега_1 имеет место включение Q .и С {(а,и), (Ъ,-и)}, кроме того, Q .и Р\ Q .V = 0 для всевозможных различных и, v Є Ега_1. Поэтому Q 5 U Q И- Теперь проверим, что Q = \J Q .и. Действительно, если \и\=п— 1 «=га—1 ап Є U, то получаем (а, а"--1) — (а, и) для всех и Є Ега_1. Если ага С/, то возьмем произвольное слово и Є Ега_1. Предположим, что и = а"--1, тогда и переводит состояние (а, а"--1) или состояние (b, а"--1) в (а, и). Пусть теперь и ф аа 1. т.е. и = а Ъй. Если к - четное (соответственно, нечетное), тогда и переводит (а, а"--1) (соответственно, (Ь, а"--1)) в (а, и). Таким образом, всякое состояние (а,и) принадлежит множеству (J Q .и. Аналогично, всякое состояние (6,и)
Определим теперь отношение эквивалентности на множестве состояний автомата ёт (т-в- на множестве слов длины п) следующим образом. Пусть w,w Є Т. Положим w w тогда и только тогда, когда w = usv, w = u sv, где s Є S, u,u ,v Є X . На множестве Xті \ T отношение определяется тривиально, т.е. для w, w Є Xті \ T мы полагаем w w тогда и только тогда, когда w = w . Легко проверить, что действительно является отношением эквивалентности на Xті. На самом деле, является конгруэнцией на множестве состояний ё$т- Покажем, что, для любого х Є X и любых w,w Є Xті, из w w следует, что w. х w . х. Если w, w Є Xті \ Т, то w = w и требуемое утверждение верно. Если w,w Є Т, то w = usv, w = u sv. Пусть и = и! = Є, тогда w = w и доказывать больше нечего. Предположим, что и, и ф е, тогда usv. х = tsvx и u sv. х = t svx для некоторых t,t Є X . Но слова tsvx и t svx принадлежат одному классу эквивалентности отношения , поскольку эти два слова имеют общий суффикс, содержащий в качестве фактора слово из S. Рассмотрим фактор-автомат ё$т/ - Обозначим через [sv] класс эквивалентности слова usv Є Т, а через [и] - класс эквивалентности слова и Т. Мы утверждаем, что в качестве требуемого автомата cs можно взять построенный автомат т/ - Другими словами, ДКА 3т/ сильно связный, и Syn(« 71/ ) = X S X . Первое свойство, очевидно, выполняется, поскольку фактор-автомат сильно связного автомата является сильно-связным.
Осталось проверить, что Syn(« 71/ ) = X S X . Возьмем произвольное слово s Є S. Для всякого состояния w Є Xті в автомате %т найдется и Є X такое, что w . s = us. Так как множество S антифакториальное, в ё%т/ получаем, что [w] . s = [s]. Таким образом, всякое s Є S является синхронизирующим словом для автомата т/ - Пусть t - некоторое синхронизирующее $т/ слово, тогда существует состояние [w] такое, что имеет место равенство [w \ Л = [w] для всякого состояния [w \ автомата т/ - Если класс [w] содержит всего одно слово, то это означает, что t является синхронизирующим словом для автомата ёт, значит, t содержит некоторое слово из множества S как фактор, т.е. t Є X S X . Рассмотрим случай, когда [w] является классом, содержащим слова вида u,\sv, U2SV,... ,UkSV, к 1. Заметим, что в этом случае щ ф є для каждого і = 1,..., к. Это означает, что t = usv для некоторого и Є X , поэтому
Идеальный язык, порожденный конечным множеством слов
Пусть дан регулярный язык L над алфавитом Е. Тогда L является языком синхронизирующих слов для минимального автомата J&L, распознающего L, в том и только том случае, если L - двусторонний идеал в И . В данной главе мы изучаем класс регулярных языков, представимых синхронизируемыми автоматами. В первом параграфе мы рассматриваем специальный класс C(Ti) всех автоматов над Е вида srf = {Q, ,6,до,{до}), обладающих следующими двумя свойствами: (1) всякое состояние д Є Q достижимо из начального состояния ( и, напротив, до достижимо из всякого состояния д Є Q:
Изучение класса (Е) также позволяет переформулировать гипотезу Черни в терминах порога синхронизации автоматов этого класса. Мы покажем, что всякий автомат stf из (Е) является синхронизируемым, более того, некоторое слово из распознаваемого автоматом stf языка является синхронизирующим для srf. Во втором параграфе данной главы будет сформулировано необходимое и достаточное условие синхронизируемости минимального автомата s$i,. распознающего данный регулярный язык L, некоторым словом из L. Кроме того, мы найдем необходимое и достаточное условие для того, чтобы имело место равенство Syn(Ig ) П L = 0. Таким образом, мы описываем класс всех регулярных языков, представимых синхронизируемыми автоматами. Отметим, что найденная характеризация устанавливает связь между синхронизируемым автоматом, распознающим регулярный язык, и множеством констант этого языка. Понятие константы регулярного языка было введено Шютценберже в [61]. Напомним, что слово w Є Е называется константой для L, если для любых Ui,U2,Us,ii4 Є Е имеет место импликация
Константы Шютценберже имеют приложение в биоинформатике [11,12] в связи с изучением языков сплетения. В частности, в недавней работе Бонницони и Ионошки [12] было показано, что всякий регулярный язык сплетения должен иметь константу. В свою очередь, теоретические результаты, устанавливающие те или иные свойства языков сплетения, играют важную роль в развитии области теории формальных языков, связанной с моделированием биохимических процессов [43].
Из определения класса C(Ti) следует, что всякий ДКА stf Є С(Ті) является сильно связным, но мы докажем следующее более сильное утверждение. Предложение 5.1. Пусть srf Є (Е) и L\sf\ = w 1Y w. Тогда srf - сильно связный синхронизируемый автомат, причем w Є Syn(Ig/). Доказательство. Пусть srf = {Q, Е, ё, qo, {qo}}- Так как srf Є (), то для вся кого q Є Q существует слово и Є Е такое, что qo . и = q. С другой стороны. uw Є w 1T1 w = L[g/], поэтому qo = qo -uw = q .w. Таким образом, мы полу чаем, что q .w = qo для всякого q Є Q, т.е. w Є Syn(Ig/). Из srf Є (Е) следует, по определению класса (Е), что stf является сильно связным. П Зафиксируем ДКА stf = (Q, Е, 8, qo,F). Напомним, что правый язык состояния q Є Q определяется равенством Lq = {и Є Е q .и Є F}. Произвольный автомат из класса (Е) распознает язык вида w Е ІУ, являющийся левым фактором главного левого идеального языка Е ІУ. Мы покажем, что минимальный автомат, распознающий язык w Е ІУ, имеет ІУ + 1 состояние. Определим для всякого w Є Е+ автомат g/(w) = {P(w),Y,,,qn,{qn}}, где п = \w\. P(w) = {qo,, Qn} - множество всех префиксов w, qo = є, qi = w[l..i] для любого 1 і п. Функция переходов определяется равенством ( 7J, а) = (qia)/\sw для всех а Є Е, ( Є P(w). Докажем теперь
Предложение 5.2. ДКА g/(w) является минимальным автоматом, распознающим язык Lw=w lY, w (11) Доказательство. По лемме 2.2 немедленно получаем, что (qi,u) = (Qiu) /\sw для всякого и Є Е , ( Є P(w). Покажем, что верно равенство (11). Пусть и Є Е и (qn,u) = qn. Тогда w = qn = (wu) As w, т.е. wu Є E -w. Обратно, если и Є w 1Y w, т.е. wu Є Е -ш, то (wu) /\sw = w = qn. Отсюда следует, что ,(qn,u) = qn, значит, и Є L[srf(w)\.
Теперь проверим, что s (w) является минимальным автоматом, распознающим w Е ІУ. Заметим, что всякое состояние qi Є P(w) достижимо из начального состояния qn. В самом деле, пусть а - произвольная буква из Е, отличная от w[l], тогда (qn,Q n) = qo, по определению функции переходов . Префикс qi = w[l..i] переводит состояние qo в qi, и мы получаем (qn,anw[l..i\) = qi. Последнее равенство означает, что произвольно выбранное состояние ( достижимо из начального состояния qn. С другой стороны, qi .w[i + l..n] = qn. т.е. заключительное состояние qn достижимо из всякого ( Є P(w). Возьмем теперь произвольные различные состояния Qi, Qj Є P(w). Без ограничения общ ности можно считать, что і j. Рассмотрим слово и = w[j + 1,п]. Получаем, что (qj,u) = qn, но Цсц,ь) ф qn, поскольку \qiu\ \w\. Следовательно, правые языки Lqi и Lq. не совпадают, значит, ( и Qj не эквивалентны.
Пусть дан язык Lw = w 1T1 w для некоторого w Є Е+. Из предложения 5.2 следует, что S LW Є (Е). Оказывается, что все сильно связные синхронизируемые автоматы над заданным алфавитом Е исчерпываются гомоморфными образами автоматов из класса (Е). Более того, имеет место
Теорема 5.1. Пусть srf = {Q, Е, 8} - сильно связный синхронизируемый ДКА, Syn(Ig/) = . Тогда для всякого синхронизирующего слова w Є Syn(Ig/) длины найдется автомат SS Є (), обладающий следующими тремя свойствами:
Напомним, что индексом конгруэнции р для автомата stf называется число состояний в фактор-автомате &/р. Для натурального числа к обозначим через Congfc(=; /) (возможно, пустое) множество всех конгруэнции индекса к для автомата stf. Характеризация класса сильно связных автоматов из теоремы 5.1 позволяет сформулировать следующее утверждение, эквивалентное гипотезе Черни.
Следствие 5.4. Класс сильно связных синхронизируемых автоматов над заданным алфавитом Е в точности описывается гомоморфными образами автоматов из класса (Е).
Доказательство. По предложению 5.1 получаем, что всякий ДКА srf Є (Е) является сильно связным синхронизируемым автоматом, следовательно, его гомоморфный образ также будет сильно связным синхронизируемым автома том. С другой стороны, по теореме 5.1 всякий сильно связный синхронизи руемый автомат над заданным алфавитом Е является гомоморфным образом некоторого ДКА из класса (Е).
Результаты теорем 5.1 и 5.2 принадлежат Э. Родаро, поэтому в данной работе мы приводим лишь их формулировки. Эти утверждения сформулированы также в [78]. Из теоремы 5.2 следует, что для доказательства гипотезы Черни достаточно рассматривать только автоматы из специального класса (Е). В связи с этим нам представляется перспективным изучение структуры автомата, распознающего язык вида w Е гг . Из предложения 5.2 следует, что минимальный ДКА, распознающий Lw = w Е ІУ, принадлежит классу (Е). В этом параграфе мы получим простую формулу для вычисления порядка синтаксической полугруппы языка Lw = w Е гг , где w Є Е+, а также установим, что автомат S LW принадлежит классу FG конечно порожденных синхронизируемых автоматов.