состояния, отличные от q , в которые он тоже может перейти за один такт.

ЗаписьС!-означает, что СС, а С(, [-м (для - что существуют такие конфигурации С, .... C ,, что Q -lO+i для всех 0i<,k. С\-/С означает, что С\-~С для некоторого 1, а С \-м С - чтоС1-м С для некоторого > 0. Таким образом, отношения и 1-м являются соответственно транзитивным и рефлексивно-транзитивным замыканием отношения 1-, Будем опускать нижний индекс-Af там, где это не приведет к недоразумениям.

Говорят,что автомат допускает цепочку MJ,ecли (o.te?) -*{q,e) для некоторого qF. Языком, определяемым (распознаваемым, допускаемым) автоматом М (обозначается L [М)), называется множество входных цепочек, допускаемых автоматом М, т. е.

L{M)=={w\wX* и (qt,, w)\-*(q, е) для некоторого qF)

Приведем два примера конечных автоматов. Первый--простой „детерминированный" автомат; второй пример показывает использование недетермпиизма.

Пример 2.11. Пусть М==({р, q, г], {О, 1}, б. р, {г}) -конечный автомат, где б задается табл. 2.1.

Таблица 2Л

М допускает все цепочки нулей и единиц, содержащие два стоящих рядом нуля. Начальное состояние р можно интерпретировать так: ,два стоящих рядом нуля еще не появились и предыдущий символ не был нулем*. Состояние q означает, что ,два стоящих рядом нуля еще не появились, но предыдущий символ был нулем". Состояние г означает, что „два стоящих рядом нуля уже появились". Заметим, что, попав в состояние г, автомат М остается в этом состоянии.

Для входа 01001 единственной возможной последовательностью конфигураций, начинающейся конфигурацией (р, 01001),

будет

(р, 01001) 1-(, 1001) Н(Р,001) Н(<?,01) 1-(г. 1) Ь {г, е)

Таким образом, 01001 L(M). Dj

Пример 2.12. Построим недетерминированный конечный автомат, допускающий цепочки в алфавите {1,2,3}, у которых последний символ цепочки уже появлялся в ней раньше. Иными словами, цепочка 121 допускается, а 31312-нет. Введем состояние (/о, смысл которого в том, что автомат в этом состоянии не пытается ничего распознать, он (или какой-то его экземпляр) находится в так называемом нейтральном состоянии. Введем также состояния q, q. и q, смысл которых в том, что они „делают предположение" о том, что последний символ цепочки совпадает с индексом состояния. Кроме того, пусть будет одно заключительное состояние Qf. Находясь в состоянии q, автомат может остаться в нем или перейти в состояние q, если а -очередной символ, Находясь в состоянии q, экземпляр автомата может перейти в состояние q, если видит символ а. Из состояния qf автомат никуда не переходит, так как вопрос о том, допускается ли входная цепочка, решается один только раз.

Таблица 2.2

когда автомат сочтет входной символ „последним". Формально автомат М определяется как пятерка

M-({q„ q, q. Я-,. 9/}, {U 2. 3}, 6, q,,, {qf\)

где й задается табл. 2.2.

Процесс порождения конфигураций для входа 12321 показан на рис. 2.2.

гл. 2. .9лел1Енты ТЕОРИИ языков

Так как {q, 12321)b*(?/, то 12321 Заметим, что

некоторые конфигурации на рис. 2.2 повторяются. Поэтому для представления конфигураций, в которые попадает автомат М, по-видимому, больше подходит ориентированный ациклический граф. □

que) qz*y-(g2»e)

Рис. 2.2. Конфигурации автомата М.

Часто бывает удобно графическое представление конечного автомата.

Определение. Пусть M = (Q, 2, 6, f) -недетерминированный конечный автомат. Диаграммой (или графом переходов) автомата М называют неупорядоченный помеченный граф, вершины которого помечены именами состояний и в котором есть дуга (p,q), если суи;ествует такой символ а 6 2, что qk(P )- Кроме того, дуга (р, q) помечается списком, состоящим из таких а, что qb{p, а).

На рис. 2.3 показаны диаграммы автоматов из примеров 2.11 и. 2.12. Начальное состояние указывается иа диаграммах направленной в него стрелкой, помеченной словом „начало", а заключительные состояния обводятся кружком.

Определим детерминированный конечный автомат как частный случай недетерминированного.

Определение. Пусть M(Q, 2, q, F) - недетерминированный конечный автомат. Назовем автомат М детерминированным, если множество 6 [q, а) содержит не более одного состояния для любых qQ и й$2. Если (q,a) всегда содержит точно одно состояние, то автомат М назовем полностью определенным.

Таким образом, автомат из примера 2.11 - полностью определенный детерминированный конечный автомат. В дальнейшем конечным автоматом будем называть полностью определенный детерминированный конечный автомат.

Один из наиболее важных результатов теории конечных автоматов состоит в том, что класс языков, определяемых недетерминированными конечными автоматами, совпадает с классом

2,2. РЕГУЛЯРНЫЕ МНОЖЕСТВА, ИХ РАСПОЗНАВЛНИЕ И ПОРОЖДЕ НИЕ

языков, определяемых полностью определенными детерминированными конечными автоматами. Сейчас мы это докажем.

Соглашение. Так как нам придется рассматривать в основном детерминированные , конечные автоматы, мы будем писать 6(9, а) = р вместо b{q,a) = {p}, когда автомат с функцией пере-

ИйЧМО

7.2,3

S пример 2.12

Рнс. 2.3. Диаграммы автоматов.

ХОДОВ б детерминированный. Если 6(9, о) = 0, то часто будем говорить, что 6 (q, а) не определено.

Теорема 2.3. Если L=J.{M) для некоторого недетерминированного конечного автомата М, то L = L(M) для некоторого конечного автомата М.

Доказательство. Пусть M = (Q, 2, б, q, F). Построим M = {Q 2, 6, ql F) следующим образом:

(1) Q==(Q), т. е. состояниями автоматам являются множества состояний автомата М;

(2) qo={qb с п

(3) F состоит из всех таких подмножеств Л множества V,

что ЗпЕф0;

(4) 6(S, a)S для всех SQ, где S =p\?>{q, а) содержит р для некоторого qS\.

Оставляем в качестве упражнения доказательство индукцией по i утверждения

(2.2.16) (5, w)\-!,(S,e) тогда и только тогда, когда = {р\(Яу ИЬм [Р.е) для некоторого qS].

Отсюда, в частности, следует, что ({J, w)i. [S, е) для некоторого S F тогда и только тогда, когда (9, w)\-~%{p е) для некоторого pF. Итак, L{M) = L{M). П

Пример 2,13. Построим конечный автомат M = {Q, {1,2,3}, й. {9о}» ). допускающий язык L{M), определяемый автоматом М из примера 2.12. Так как М имеет 5 состояний, то, казалось бы, М должен иметь 32 состояния. Однако не все они достижимы из начального состояния. Состояние р называется дости-окимым, если существует такая цепочка w, что (о, w)\-*{p,e),

\ 2 3

Рис. 2.4. Функция переходов автомата М\

где -начальное состояние. Мы будем строить только достижимые состояния.

Начнем с замечания, что состояние {q\ достижимо. 6 ({J, а) {Яц, Яа) для а=\, 2 и 3. Рассмотрим состояние {q, J, Имеем б({(7о, q\, \){q, q, q}. Продолжая в том же духе, получаем, что множество состояний автомата М (оно является состоянием автомата М) достижимо тогда и только тогда, когда

(1) оно содержит и

(2) если оно содержит q, то содержит также и j, q или 3,

Множество всех достижимых состояний автомата М вместе с функцией 6 приведено на рис. 2.4.

Начальным состоянием автомата М является Л, а множество заключительных состояний -{£, Я, J, К, М, N, Р}. □

2.2.4. Конечные автоматы и регулярные множества

Покажем, что язык является регулярным множеством тогда и только тогда, когда он определяется конечным автоматом. Для этого мы докажем сначала, что конечно-автоматный язык определяется праволинейной грамматикой, а затем- что множество конечно-автоматных языков содержит языки 0, {е\, {й:} для всех символов а и замкнуто относительно объединения, конкатенации и итерации. Таким образом, каждое регулярное множество оказывается конечно-автоматным языком.

Лемма 2.8. Если L-=L{M) для некоторого конечного автомата М, то L - L(G) для некоторой праволинейной грамматики G.

Доказательство. Пусть M(Q, S, б, q, Р) -конечный автомат (детерминированный, разумеется). Возьмем грамматику G=-={Q, 2, Р, i/o), где Р определяется так:

(1) Если f){q, а) -г, то Р содержит правило q-ar.

(2) Если pF, то р-еР.

Можно показать, что каждый шаг вывода в грамматике G имитирует такт автомата М: Докажем индукцией по /, что

(2.2.17) qw для qQ тогда и только тогда, когда {q, w) 1- (г, е) для некоторого rF.

Базис. Для i = 0 очевидно, что qe тогда и только тогда, когда [q, e)"{q, е) для qF.

Шаг индукции. Предположим, что (2.2.17) истинно для /, и возьмем w = ax, где \x\=i. Тогда q::>-w равносильно тому, что q asax для некоторого sQ. Но qras равносильно b(q, a)= s. По предположению индукции sх тогда и только тогда, когда (s, х) ]-(г, е) для некоторого rF. Следовательно, qz--w равносильно [q, w) \- (г, е) для некоторого г £ Итак, утверждение (2.2.17) истинно для всех iO.

Отсюда заключаем, что qw тогда и только тогда, когда (q isy-*(г, е) для некоторого rF. Таким образом, Z-(G) 1{М). □

Лемма 2.9. Пусть - конечный алфавит. Множества (i) 0, (ii) {е} и (iii) {а} для всех йХ являются конечно-автоматными языками.

Доказательство. (1) Любой конечный автомат с пустым множеством заключительных состояний допускает 0.

(ii) Пусть M = {{q,}, 2. б, q„ {q,}), где 6 ((/ц, а) ие определено ни для каких а2. Тогда L(M)==={e}.