Регулярные выражения и языки (стр. 14 )

Если w начинается символом а, то h(w) начинается с 01. Следовательно, она содер­жит отдельный 0 и поэтому не принадлежит L. Если w заканчивается символом Ь, то в конце h(w) стоит 10, и опять-таки в цепочке h(w) есть изолированный 0. Если в цепочке w дважды подряд встречается а, то h(w) содержит подцепочку 0101. Снова в w есть изолированный нуль. Аналогично, если в w есть два символа b подряд, то h(w) содержит подцепочку 1010 с изолированным 0.

Таким образом, при выполнении хотя бы одного из вышеперечисленных условий цепоч­ка h(w) не принадлежит L. Но если ни одно из условий 1-4 не выполняется, то цепочка w имеет вид baba...ba. Чтобы понять, почему это происходит, предположим, что ни одно из этих условий не выполняется. Тогда невыполнение условия 1 означает, что w должна начинаться символом Ь, а невыполнение 2 — что она должна заканчиваться символом а. Невыполнение условий 3 и 4 говорит, что символы а и b должны чередоваться. Следова­тельно, логическое ИЛИ условий 1-4 эквивалентно утверждению "цепочка w имеет вид, отличный от baba...bcC\ Но выше было доказано, что из логического ИЛИ условий 1-4 следует, что h(w) не принадлежит L. Это утверждение противоположно тому, что нужно доказать, а именно, что "если h(w) принадлежит L, то цепочка w имеет вид babu...ba\ □

Далее докажем, что обратный гомоморфизм регулярного языка также регулярен, и покажем, как эту теорему можно использовать.

Теорема 4.16. Если h— гомоморфизм из алфавита X в алфавит Т, L— регулярный язык над Т, то язык h~l(L) также регулярен.

Доказательство. Начнем с ДКА А для языка L. По А и h строится ДКА для h'l(L) с помощью схемы, представленной на рис. 4.6. Этот ДКА использует состояния автомата А, но переводит входной символ в соответствии с h перед тем, как решить, в какое со­стояние перейти.

Вход о

Рис. 4.6. ДКА для h '(L) применяет гомоморфизм h ко входным символам, а потом имитирует ДКА для L

Формально, пусть L — это ЦА), где ДКА А = (Q, Т, 8, q0, F). Определим ДКА

л

функция переходов /которого строится по правилу y(q, а)= 8 (q, h(a)). Таким образом, переход автомата В по входному символу а является результатом последовательности переходов, совершаемых автоматом А при получении цепочки символов h{a). Напомним, что, хотя h(a) может равняться е, состоять из одного или нескольких символов, функция <5 определена так, чтобы справиться со всеми этими случаями.

С помощью индукции по |vv| легко показать, что у (q„, vv) = 8(q0,h(w)). Поскольку допускающие состояния автоматов А и В совпадают, то В допускает цепочку w тогда и только тогда, когда А допускает цепочку h{w). Иными словами, В допускает только те цепочки, которые принадлежат языку h'l(L). □

Пример 4.17. В этом примере обратный гомоморфизм и некоторые другие свойства замкнутости регулярных множеств используются для доказательства одного необычного свойства конечных автоматов. Предположим, что, допуская входную цепочку, некоторый автомат должен побывать в каждом состоянии хотя бы по одному разу. Точнее, допустим, что А = (Q, Z, 8, q0, F) — ДКА, и нас интересует язык L, состоящий из всех цепочек w в ал­фавите Z*, для которых 8 (q, h vv) принадлежит F, и для каждого состояния q из Q существу­ет некоторый префикс хч цепочки vv, для которого 8 (q0, хч) = q. Будет ли язык L регуляр­ным? Докажем, что такой язык регулярен, хотя доказательство довольно сложное.

Начнем с языка M-L(A), т. е. множества цепочек, допускаемых автоматом А обычным путем, независимо от того, в какие состояния он переходит, обрабатывая входную цепочку. Заметим, что LqM, так как определение языка L накладывает дополнительные ограниче­ния на цепочки из ЦА). Доказательство регулярности языка L начинается с использования обратного гомоморфизма для вставки состояний автомата А во входные символы. Точнее, определим новый алфавит Т как состоящий из символов, которые можно представить в ви­де троек \paq], где pwq — состояния из Q, а — символ из Z, и 8(р, а) = q.

Таким образом, символы алфавита Г представляют переходы автомата А. Важно по­нимать, что запись [paq] представляет собой единый символ, а не конкатенацию трех символов. Можно обозначить этот символ одной буквой, но при этом трудно описать его связь cp, qna.

Теперь определим гомоморфизм h([paq]) = а для всех р, а и q. Это значит, что гомо­морфизм h удаляет из каждого символа алфавита Т компоненты, представляющие со­стояния, и оставляет только символ из Z. Первый шаг доказательства регулярности языка L состоит в построении языка L, = h~l(M). Поскольку язык М регулярен, то согласно тео­реме 4.16 язык Li также регулярен. Цепочками языка Li будут цепочки из М, к каждому символу которых присоединяется пара состояний, представляющая некоторый переход автомата.

В качестве простого примера рассмотрим автомат с двумя состояниями, представ­ленный на рис. 4.4, а. Алфавит Х= {0, 1}, а алфавит Т состоит из четырех символов [pQq], [q$q], [pip] и [q\q]. Например, поскольку по символу 0 есть переход из р в q, то \pOq] — один из символов алфавита Т. Так как цепочка 101 допускается этим автоматом, применив к ней обратный гомоморфизм /Г1, получим 23 = 8 цепочек, две из которых, на­пример, равны [p\p]\pQq][q\q] и [q\q][q0q]\p\p].

Теперь по языку построим язык L с помощью ряда операций, сохраняющих регу­лярность языков. Наша первая цель — исключить все те цепочки языка Lh в которых со­стояния указаны неправильно. Поскольку каждый символ вида \paq\ означает, что авто­мат был в состоянии р, прочитал а и затем перешел в состояние q, последовательность таких символов, представляющая допускающее вычисление в автомате А, должна удов­летворять следующим трем условиям.

Первым состоянием в первом символе должно быть q0 — начальное состояние А. Каждый переход автомата должен начинаться там, где закончился предыдущий, т. е. пер­вое состояние в символе должно равняться второму состоянию в предыдущем символе. Второе состояние в последнем символе должно принадлежать F. Если выполняются первые два условия, то и это условие будет выполнено, поскольку каждая цепочка языка L, образована из цепочки, допускаемой автоматом А.

и	Язык автомата А
Обратный гомоморфизм
L	1	Цепочки языка М, в которые вставлены компоненты состояний
i	'	Пересечение с регулярным языком
L	2	Добавить условие, что первым является начальное состояние
'	Разница с регулярным языком
1	3	Добавить условие, что смежные состояния должны совпадать
Разница с регулярными языками
'4	Добавить условие, что на пути встречаются все состояния
Гомоморфизм
L	Удалить компоненты состояний, оставляя только символы

Рис. 4.7. Построение языка L по языку М с помощью операций, сохраняющих регулярность языков

План построения языка L представлен на рис. 4.7.

Условие 1 обеспечивается пересечением языка Li со множеством цепочек, которые на­чинаются символом вида [qoaq] для некоторого символа а и состояния q. Пусть Ei — вы­ражение [qnQ^h] + [qoOiCji] + ..., где a, q, — все пары из X X Q, для которых S(qfl, а,) = q,. Пусть L2 = L] П L{E;T). Регулярное выражение Е, Т обозначает все цепочки из Т*, которые начинаются стартовым состоянием (здесь Т можно рассматривать как сумму всех его сим­волов). Поэтому язык /,2 состоит из всех цепочек, полученных в результате применения об­ратного гомоморфизма /Г1 к языку М, у которых первым компонентом в первом символе является начальное состояние, т. е. язык L2 удовлетворяет условию 1.