(iii) Пусть М-({о. 2, 6, q, {q}), где b(q, а) = д, а в остальных случаях функция 6 не определена. Тогда

Лемма 2.10. Пусть 1 = 1 [Mj) и LLiM) для конечных автоматов и М. Множества {[) LuL, (ii) LJ. и (iii) Ll являются конечно-автоматными языками.

Доказательство. Пусть М -(Q, 2, Й, q, F) и = (Qa> 2» /а. а)- 63 нотерн общности МОЖНО считэть, что QnQ2=0T так как в npotHBHOM случае состояния можно было бы переименовать.

(i) Пусть M={QiUQ2U {qo\, 2, 6, qQ, f) -недетерминированный конечный автомат, где

(1) - новое состояние,

(2) F=FUF, если eLUL, и F F,U FU {q}, если eL,UL„

(3) (а) 6 ((/о а) -б ((7, а) и б ((72, а) для всех а € 2,

(б) 6(q, a)6i((?, а) для всех g€Qi и а 2,

(в) 6((?, а)=б2((7, а) для всех <? € Qa 2.

Таким образом, автомат М вначале как бы угадывает, какой из автоматов М, ему моделировать. Так как М - недетерминированный автомат, то фактически он моделирует и тот, и другой. Можно показать индукцией по t> 1, что (q, w)\-M{q, е) тогда и только тогда, когда qQii (qi, w)\-M,{q, или (742 и {q, w)[-M(q, е). Отсюда и из определения множества F вытекает, что L(M)L{Mj}(jL (М).

(ii) Чтобы построить конечный автомат М, распознающий язык /.jZ-a, положим М -(Q1UQ2. 2, 6, q, F), где

F, если qF-i, FUF, если €2» а функция б определяется равенствами

(1) 6(f/, a) = y(q, а) для всех qQi~Fi,

(2) б ((7, о) = 61 (7, а)иб2(72» «) для всех qFi*

(3) 6(7, а) = 62 ((7, а) для всех f/Qa-

Таким образом, М начинает работать, моделируя М. Когда М достигает заключительного состояния автомата М, он может недетерминированно вообразить, что находится в начальном состоянии автомата М (равенство (2)), и моделировать М. Пусть xLi и yL. Тогда (q, xy)[-M{q, у) для некоторого qFi. Если х~е, то q~q. Если уфе, то, применяя один раз равенство (2) и нуль или более раз равенство (3), получаем (яу У)\-м(г, для некоторого rF. Если у = е, то qF, так как qF, Отсюда xyL{M), Допустим, что wL(M), Тогда

(t/i, w)\-\i[q, е) для некоторого qF. Рассмотрим отдельно два случая; qF и qF. Пусть q£F. Тогда w - xay для некоторого а€2, удовлетворяющего условиям

где rF, sQ-i и 62 (л, а) содержит s. Следовательно, €1 и ayL.. Пусть теперь qFj. Тогда qF. и eL. Таким образом, Отсюда заключаем, что L{M) = LL2.

(iii) Построим автомат М (Qi (J j*?}, 2, б, q, /"U {<?}), где q - новое состояние, не принадлежащее Q, который допускает язык Ll. Определим функцию б равенствами

(1) б((7, a)--6i((7, а), если qQ~Fi и аб2,

(2) 6(9, a) = 6i((7, й)иб, (9i» «), если qF и а€2,

(3) 6(9, a) = 6i((7i а) для а2.

Таким образом, когда М попадает в заключительное состояние автомата М, он может на выбор либо продолжать моделирование Мт, либо начать заново моделирование М с начального состояния. Доказательство того, что L(M) = L{, аналогично доказательству части (ii). Заметим, что eL(M), так как q - заключительное состояние. □

Теорема 2.4. Дзь/к допускается конечным автоматом тогда и только тогда, когда он является регулярным множеством.

Доказательство. Теорема непосредственно следует из теоремы 2.2 и лемм 2.8-2.10. □

2.2,5. Резюме

Результаты разд. 2,2 можно сформулировать в виде следующей теоремы.

Теорема 2.5. Утверждения

(1) L - регулярное множество,

(2) L - праволинейный язык,

(3) L~~конечно-автоматный язык,

(4) L - недетерминированный конечно-автоматный язык,

(5) L обозначается регулярным выражением

эквивалентны. □

УПРАЖНЕНИЯ

2.2.1. Какие из следующих множеств регулярны? Для тех, которые регулярны, напишите регулярные выражения.

(а) Множество цепочек с равным числом нулей и единиц.

(6) Множество цепочек из {О, 1}* с четным числом нулей и нечетным числом единиц.

(в) Множество цепочек из {О, 1}*, длины которых делятся на 3.

(г) Множество цепочек из {О, 1}*, не содержащих подцепочки 101.

2.2.2. Покажите, что множество регулярных выражений в алфавите -2 является КС-языком.

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

2.2.4. Пусть L-регулярное множество. Прямо из определения регулярного множества получите, что - регулярное множество. Указание: Докажите это индукцией по числу применений определения регулярного множества, использованных при построении L как регулярного множества.

2.2.5. Докажите следующие тождества для произвольных регулярных выражений а, р и у:

(а) а(Р + у) = ар + ау, (ж) (а + Р) у := ау + Ру.

(б) а + (Р + у)-(а + р) + у. (3) 0*6,

(в) а(Ру) = (аР)у, (и) а* = а--а*,

(г) ае = еа = а, (к) (а*)* = а*,

(д) 0а-а0 = 0, (л) (а + Р)* = (а*р*)*,

(е) аа = а, (м) а0 = а.

2.2.6. Решите систему уравнений с регулярными коэффициентами

Л,==(01*+1)Л + Л2 Л.И + Ы + ООЛз Лз = е*-Л1 + Л2

2.2.7. Рассмотрите уравнение (2.2.18) Х = аХ + р

где а и р-регулярные выражения в алфавите 2 и Х2. Покажите, что

(а) если еа, то X - а*р-единственное решение уравнения (2.2.18);

(б) если еа, то а*р - наименьшая неподвижная точка уравнения (2.2.18), но решений бесконечно много;

(в) в любом случае каждое решение уравнения (2.2.18) имеет вид а*(ри/-). где L - некоторый (не обязательно регулярный) язык.

2.2.8. Решите стандартную систему, состоящую из двух уравнений общего вида

X = а,Х + aY +

крд+р,к+рз

2.2.9. Восполните детали доказательства леммы 2.4.

2.2.10. Докажите лемму 2.5.

2.2.11. Найдите праволинейные грамматики для тех множеств упр. 2.2.1, которые регулярны.

Определение. Грамматика G = (N, 2, Р, 5) называется лево-линейной, если каждое правило множества Р имеет вид А-Bw или А->w.

2.2.12. Покажите, что язык является регулярным множеством тогда и только тогда, когда он порождается леволинейной грамматикой. Указание: Воспользуйтесь упр. 2.2.4.

Определение. Праволинейная грамматика G=(N, 2, Р, S) называется регулярной (или автоматной), если

(1) все ее правила, за исключением S->е, имеют вид Л->йВ или Л-а, где SN, а2,

(2) если 5-принадлежит Р, то 5 не встречается в правых частях правил.

2.2.13. Покажите, что каждое регулярное множество порождается регулярной грамматикой. Указание: Это можно сделать несколькими способами. Один из них состоит в том, чтобы применить к праволинейной грамматике G последовательность преобразований, которая переведет G в эквивалентную регулярную грамматику. Другой способ-построить регулярную грамматику по конечному автомату.

2.2.14. Постройте регулярную грамматику для регулярного множества, порождаемого праволинейной грамматикой с правилами

Л-ВС

В->0В 1В011

С-Ш\\С\е

2.2.15. Опишите алгоритм, который по данной регулярной грамматике G и цепочке w определяет, принадлежит ли w язы-ку L(G).

2.2.16. Докажите утверждение (2.2.16) из доказательства теоремы 2.3.

2.2.17. Дополните доказательство леммы 2.7 (iii).

Определение. Правило А - сс праволинейной грамматики G(N, 2,Р, 5) называется бесполезным, если в множестве 2* не существует таких цепочек w я х, что 5=* wAwa=* WX

гл. 2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ

2.2.18. Постройте алгоритм, преобразующий праволинейную грамматику в эквивалентную ей грамматику без бесполезных правил.

*2.2.19. Пусть G(N, 2, Р, 5) -праволинейная грамматика.

nycTbN={i.....Л„}каи = х, + х-{-... гдеv4,--iy...

...\x,„Aj-это все правила вида Л;->yAj. Положим а - х... ... -\-х, где Afxl.. .-это все правила вида Ау. Пусть, наконец, Q будет системой уравнений в стандартной формеЛ-а,-о + а,.1Л1 + а.2Л2+ ... +а-„Л„. Покажите, чтоL{G)- наименьшая неподвижная точка системы Q. Указание: Воспользуйтесь леммой 2.3.

2.2.20. Покажите, что язык L{G) из примера 2.10 - это множество цепочек в алфавите {0,1}, длина которых делится на 3.

2.2.21. Найдите детерминированные и недетерминированные конечные автоматы для тех множеств из упр. 2.2.1, которые регулярны.

2.2.22. Покажите, что конечный автомат из примера 2.11 допускает язык (О + 1)*00(0 + 1)*.

2.2.23. Докажите, что конечный автомат из примера 2.12 допускает язык {wa\a{l, 2, 3} и а входит в w\.

2.2.24. Дополните доказательство леммы 2.10(111).

*2.2.25. Двусторонний конечный автомат состоит из (недетерминированного) управляющего устройства с конечным числом состояний и входной головки, которая может двигаться по входной цепочке влево, вправо или оставаться неподвижной. Покажите, что язык допускается двусторонним конечным автоматом тогда и только тогда, когда он является регулярным множеством. Указание: Постройте детерминированный односторонний конечный автомат, который, прочитав входную цепочку w=ye, помещает во внутреннюю память управляющего устройства конечную таблицу, указывающую для каждого состояния q двустороннего автомата, в каком состоянии (если таковое существует) он сойдет с правого конца цепочки w, начав работу на этом правом конце в состоянии q.

*2.2.26. Покажите, что если позволить односторонним конечным автоматам сдвигать входную головку ие на каждом такте, то это не увеличит класса определяемых ими языков.

**2.2.27. Покажите, что для любого п существует регулярное множество, которое допускается недетерминированным конечным автоматом с п состояниями, но для распознавания которого детерминированным конечным автоматом требуется 2" состояний.

2.3. СВОЙСТВА РЕГУЛЯРНЫХ МНОЖЕСТВ

2.2.28. Покажите, что каждый язык, допускаемый двусторонним конечным автоматом с п состояниями, допускается односторонним конечным автоматом с 2"""* состояниями.

**2.2.29. Сколько различных языков в алфавите {О, 1} определяются (а) недетерминированными, (б) детерминированными и (в) двусторонними конечными автоматами с двумя состояниями?

Определение. Множество S целых чисел образует арифметическую прогрессию, если его можно записать в виде 5{с, с + р, с-[-2р, ..., cip, ...}. UycTb S {L) = {i\\w\ = i для некоторого wL} для любого языка L.

**2.2.30. Покажите, что для каждого регулярного языка L множество S{L) можно представить в виде объединения конечного числа арифметических прогрессий.

Открытая проблема

2.2.31. Насколько приведенная в упр. 2.2.28 верхняя граница числа состояний одностороннего автомата, моделирующего двусторонний конечный автомат, близка к наименьшему возможному числу состояний? )

Замечания по литературе

Регулярные выражения были определены Клинн [1956]. Дополнительную информацию о регулярных выражениях можно найти в работах Мак-Нотоиа и Ямады [1960] и Бжо.зовского [1962] 2). Саломаа [1966а] описал две системы аксиом для регулярных выражений з). .Хомский и Миллер [1958] доказали эквивалентность регулярных грамматик и регулярных выражений, а Рабин н Скотт [1959] -эквивалентность детерминированных и недетерминированных конечных автоматов. Упр. 2.2.25 взято из работ Рабина и Скотта [1959] н Шепердсоиа [1959.

2.3. СВОЙСТВА РЕГУЛЯРНЫХ МНОЖЕСТВ

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

2.3.1. Минимизация конечных автоматов

По данному конечному автомату М можно найти наименьший эквивалентный ему конечный автомат, исключив все недостижимые состояния и затем склеив лишние состояния. Лишние

) В связи с этой проблемой см. работу ХаргыаЕЕса[1970]. -Прим. перев.

) О регулярных выражениях написано много, см. монографин, упоминаемые в замечаниях по литературе к разд. 2.3. -Прим. перев.

) В связи с этим см. также работы Редько [1964] и Саломаа [19666] - Прим. перев.