О.Б. Лупанов - Курс лекций по дискретной математике, страница 11

, a(t), поданное на вход конечного автомата. Будем говорить,что слово w принято автоматом, если b(t) ∈ B ′ . Множество всех слов, принимаемых автоматом, будем называтьсобытием, или представимым данным автоматом.Мы будем выяснять вопрос о том, можно ли описать все события. Оказывается, это можно сделать, и ответбудет дан в терминах так называемых регулярных множеств, которые мы сейчас определим.Для начала нам потребуется несколько вспомогательных определений.Определение.

Конкатенация (склейка) двух слов w1 и w2 какого-либо алфавита — это просто слово w1 w2 .Определение. Конкатенация M1 M2 двух множеств M1 и M2 — это множествоM1 M2 := {w1 w2 | w1 ∈ M1 , w2 ∈ M2 } .(2)Конкатенацию множества с самим собой мы будем обозначать в виде степени (не путать с декартовой степенью!). Иначе говоря,M. . M} = M k .(3)| .{zk разОпределение. Итерация данного множества — это множествоhM i := M ∪ M 2 ∪ M 3 ∪ . . .(4)Определение. Одноэлементные подмножества алфавита A по определению являются регулярными множествами.

Далее, если M1 , M2 — регулярные множества, то M1 ∪ M2 , M1 M2 и hM1 i тоже будем называтьрегулярными множествами. Пустое множество тоже будем считать регулярным.Чуть позже мы докажем теорему Клини, которая утверждает, что регулярные множества и представимыемножества — это одно и то же.4.2.2. Свойства регулярных множествВсе однобуквенные слова регулярны по определению. Очевидно, что любое конечное множество слов регулярно.Лемма 4.2. Рассмотрим уравнение X = XC ∪ D на X.

Его решение существует и единственно. Покажем, что множество F0 := D hCi ∪ D является решением. В самом деле, подставим в уравнение:(D hCi ∪ D)C ∪ D = D hCi C ∪ DC ∪ D = D hCi ∪ D.(5)Допустим, что существует какое-либо другое решение F1 6= F0 , то есть F1 = F1 C ∪ D.Пусть сначала F1 * F0 . Рассмотрим самое короткое слово α ∈ F1 r F0 . Ясно, что α ∈/ D, иначе бы α ∈ F0 .Стало быть, α ∈ F1 C и потому имеет вид α = α1 α2 , где α1 ∈ F1 , а α2 ∈ C. Заметим, что α1 ∈ F0 , иначе α небыло бы самым коротким словом в F1 r F0 . Но тогда α ∈ F0 C ⊂ F0 C ∪ D = F0 , противоречие.Пусть теперь F0 * F1 . Дальнейшие рассуждения абсолютно аналогичны, если поменять ролями F0 и F1 :35Возьмём самое короткое α ∈ F0 r F1 .

Ясно, что α ∈/ D, иначе α ∈ F1 . Отсюда следует, что α ∈ F0 C и потомуимеет вид α = α1 α2 , где α1 ∈ F0 , а α2 ∈ C. Но тогда α1 ∈ F1 , иначе α не было бы самым коротким, а тогдаα = α1 α2 ∈ F1 C ⊂ F1 C ∪ D = F1 — противоречие.Значит, на самом деле F0 = F1 , то есть решение единственно. Следствие 4.1. Если коэффициенты в уравнении X = XC ∪ D регулярны, то и решение регулярно.Следствие 4.2. Рассмотрим систему уравнений X1 = X1 R11 ∪ X2 R21 ∪ · · · ∪ Xn Rn1 ∪ R1 ,...Xn = X1 R1n ∪ X2 R2n ∪ · · · ∪ Xn Rnn ∪ Rn ,(6)относительно переменных X1 , . .

. , Xn . Если события Rij регулярны, то решение системы существует, единственно и также регулярно. Докажем для случая двух переменных, для случая бо́льшего их числа всё делается аналогично (и поиндукции).(X1 = X1 R11 ∪ X2 R21 ∪ R1 ,(7)X2 = X1 R12 ∪ X2 R22 ∪ R2 ,Перепишем второе уравнение так: X2 = X2 R22 ∪ (X1 R12 ∪ R2 ) и обозначим второе слагаемое через D, а R22через C. Получаем уравнение X2 = X2 C ∪ D. По лемме у него имеется единственное решениеX2 = D hCi ∪ D = (X1 R12 ∪ R2 ) hR22 i ∪ (X1 R12 ∪ R2 ).(8)Подставим во первое уравнение:X1 = X1 R11 ∪ [(X1 R12 ∪ R2 ) hR22 i ∪ (X1 R12 ∪ R2 )] R21 ∪ R1 .{z}|(9)X2А теперь раскроем скобки и вынесем X1 :X1 = X1 R11 ∪ [R11 hR22 i ∪ R12 ]R21 ∪ [R2 hR22 i ∪ R2 ]R21 ∪ R1 .(10)Опять получилось уравнение, про которое мы уже всё знаем.

Осталось заметить, что все коэффициенты регулярны. 4.2.3. Обобщённые источники. Доказательство теоремы КлиниРассмотрим автомат с набором состояний q1 , . . . , qλ , входным алфавитом A = {a1 , . . . , aν } и выходным алфавитом B = {b1 , . . . , bµ }. Рассмотрим подмножество B ′ ⊂ B.Сейчас мы докажем одну половину теоремы Клини.Утверждение 4.3. Все представимые события регулярны.

Обозначим через Mi множество всех слов, под воздействием которых автомат из состояния q1 попадаетв состояние qi . Через Mi′ обозначим множество букв, при подаче которых в состоянии qi автомат выдаёт буквуиз B ′ . Очевидно, что все представимые слова имеют видλ[Mi Mi′ .(11)i=1Поскольку все множества Mi′ конечны, они регулярны. Значит, осталось доказать, что все множества Mi тожерегулярны.Пусть Rij — множество букв, которые переводят автомат из состояния qi в состояние qj . Множества Rijконечны, а потому регулярные.Выясним, откуда можно прийти в состояние qk .

В него можно прийти из M1 , если нам дадут букву R1k .Кроме того, в него можно прийти из M2 , но только если нам дадут букву из R2k , и так далее. Стало быть,Mk = M1 R1k ∪ M2 R2k ∪ · · · ∪ Mλ Rλk ∪ R1k .(12)Последняя возможность соответствует тому, что мы сразу попали в qk .

Мы видим, что у нас получилась как разтакая система, про решения которой мы всё знаем — все они регулярные. Итак, первая часть теоремы Клинидоказана. 36Определение. Обобщённый источник — это ориентированный конечный граф, в котором выделены двевершины, называемые началом S и концом E соответственно. Некоторым рёбрам приписаны буквы исходногоалфавита.По рёбрам источника можно ходить, соблюдая ориентацию. Рассмотрим все пути в графе по рёбрам из Sв E.

При этом каждому пути естественным образом сопоставляется слово из тех букв, которые написаны нарёбрах. Таким образом, всякий обобщённый источник порождает некоторое множество слов.Пусть нам дано регулярное событие. Покажем, что можно построить обобщённый источник, который порождает в точности это событие.Источник, порождающий какую-либо букву, строится тривиально: это одно ребро из S в E, на которомнаписана эта буква.SaiEРис. 15.

Генератор одной буквыПусть мы умеем строить источники D1 и D2 для событий M1 и M2 соответственно. Тогда источник длясобытия M1 M2 делается так, как показано на рис. 16.S1SDD111111DDE1S2DD222222DDE2EРис. 16. Генератор конкатенацииДля генерации объединения множеств M1 ∪ M2 нужно использовать источник, изображённый на рис. 17.S1DD111111DDE1SES2DD222222DDE2Рис. 17. Генератор объединенияНаконец, для итераций используется источник, изображённый на рис. 18.SS1DD111111DDE1EРис.

18. Генератор итерацийИтак, по регулярному множеству построен источник. А теперь по источнику построим автомат, для которогоданное множество является представимым. Пусть V — множество вершин источника. Рассмотрим автомат, в котором состояниями будут подмножества вершин нашего источника. Таким образом, у него будет 2|V | состояний.В качестве выходного алфавита возьмём B := {0, 1}, а B ′ = {1}.Рассмотрим qi ⊂ V . Рассмотрим то множество вершин, в которое мы можем попасть под действием буквыak из вершин, принадлежащих состоянию qi . Получим какое-то другое подмножество вершин qj .

Таким образомопределена функция перехода: G(ak , qi ) = qj .akОсталось определить отображение выхода: если в qj попала вершина E, то при переходе qi −→qj выдаёмна выход 1, а иначе выдаём 0. Понятно, что такой автомат в случае регулярного события выдаёт единицу, а вслучае нерегулярного — ноль.Это завершает доказательство обещанной теоремы:Теорема 4.4 (Клини). Всякое регулярное событие является представимым, и наоборот.4.2.4. О том, чего не могут автоматыВ заключение мы докажем теорему о том, что не существует никакой конечной полной системы автоматныхфункций.

Иначе говоря, если разрешить использовать в схеме вместо {¬ & ∨} любые автоматные функции, нозапретить ориентированные циклы, то не существует такого конечного набора автоматных функций, схемой изкоторых можно было бы реализовать любой автомат.Лемма 4.5. Пусть есть автомат с λ состояниями. Пусть на вход ему подаётся периодическая последовательность с периодом T . Тогда выходная последовательность периодична с периодом T d, где d 6 λ. Пусть автомату в некоторый момент времени t1 был подан символ a1 . Через T шагов ему снова дадутсимвол a1 .

Возможно, автомат окажется в другом состоянии. Ещё через T шагов он снова окажется c тем жевходным символом, и так далее. Число состояний равно λ, поэтому не более чем через λ таких циклов (обозначимэто количество через d) он по принципу Дирихле дважды побывает в одним и том же состоянии. Начиная сэтого момента всё повторится, а значит, и выход автомата будет периодическим с указанным периодом.

37Через Sl будем обозначать множество периодических последовательностей, у которых длина минимальногоимеет среди своих простых делителей лишь числа не больше l.Следствие 4.3. Пусть на вход автомата c не более чем l состояниями подаётся последовательность изSl . Тогда на выходе тоже будет последовательность из Sl .Следствие 4.4. Пусть есть схема из автоматных функций, каждая из которых имеет не более l состояний. Если на вход подаётся последовательность из Sl , то на выходе будет последовательность из Sl .Замечание. У всей схемы состояний, конечно, может быть будет гораздо больше, но простые делителипериодов всё равно не будут превосходить l.Теорема 4.6. Не существует конечной полной системы автоматных функций.

Допустим, что она существует: F1 , . . . , FN . Пусть λi — количество состояний автомата Fi . Пусть l :=max λi . Рассмотрим автомат, выдающий последовательность (вне зависимости от входных данных)(0, . . . , 0, 1, 0, . . . , 0, 1, . . . ),| {z } | {z }p(13)pгде p — простое число, бо́льшее l. Будем на вход подавать сплошные нули (очевидно, это последовательность изSl ). По доказанному выход любого автомата, построенного на базисе {Fi }, должен быть из Sl , а у этого автоматаэто не так.

Противоречие. 38.