XVYggbpFw2

Это доказывает теорему в одну сторону и, заодно, дает простой алгоритм построения по регулярному выражению соответствующего автомата.

Докажем теперь, что любой автоматный язык определяется некоторым регулярным выражением. Это доказательство является неплохой иллюстрацией тезиса о том, что ничего не может быть практичнее хорошей теории. “Хорошая теория” в данном случае заключается в гармоничном обобщении понятия конечного автомата, изящно соединяющем автоматы и регулярные выражения. Идея этого соединения просматривается в старом соглашении, по которому несколько дуг, выходящих из вершины A в вершину B, мы изображаем одной дугой, перечисляя их метки (например, a,b,c) через запятую. Ничто не мешает считать эти дуги действительно одной дугой с меткой, обозначающей множество {a,b,c}. А множество это обозначать соответствующим ему регулярным выражением a|b|c:

вместо рисуется .

Итак, обобщенным конечным автоматом будем называть граф,

вершины которого играют точно такую же роль, как и раньше, но метками дуг являются произвольные регулярные выражения над множеством терминалов T. Во время работы такой автомат переходя по дуге с меткой r из состояния A в состояние B, может переместить каретку сразу на несколько клеток “прочитывая” с текущего места терминальное слово при условии, что принадлежит множеству, определяемому регулярным выражением r.

Интересно, что дуги без меток теперь не нужны. Их метками в обобщенном автомате будем считать символ 1. Регулярное выражение 0 тоже может использоваться как метка дуги. Но такая дуга “непроходима” ни при каких обстоятельствах. Стирая такие дуги, мы получим эквивалентный автомат.

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

вследующем. Данный автомат в классе обобщенных автоматов постепенно упрощается и доводится всего до двух состояний, среди которых одно стартовое и одно заключительное. При этом количество переходов (дуг) становится равным четырем. Короче, произвольный автомат превращается

вавтомат вида

( )

Здесь p,q,r,t – не терминалы, а регулярные выражения от терминалов исходного автомата. Нетрудно видеть, что этот автомат распознает язык, задаваемый регулярным выражением

r*pt* + (r*pt*qr*pt*)*

Таким образом надо:

1)Перестроить произвольный автомат так, чтобы он имел единственное заключительное состояние F, отличное от стартового S

2)Заменять несколько дуг между двумя состояниями одной.

3)Научиться удалять из обобщенного автомата любое состояние,

отличное от S и F, перестраивая подходящим образом переходы между оставшимися состояниями.

Применяя сначала пункт 1), а затем, чередуя 2) и 3), мы и получим автомат вида ( ).

Пункт 1) выполнить очень просто. Надо добавить к автомату еще одно состояние и провести в него дуги без меток (т.е. с меткой 1) из каждого заключительного состояния исходного автомата. Затем прежние заключительные состояния из множества заключительных состояний изъять (не из самого автомата, конечно).

Пункт 2) также не представляет проблем. Возьмем в автомате два произвольных состояния A и B (это может быть одно и тоже состояние). Рассмотрим все дуги, из A в B (если они есть). Пусть их метки – это r1,…, rk. Заменяем все эти дуги одной с меткой r1+…+ rk. Очевидно, что получится эквивалентный автомат.

Перейдем к пункту 3). Считаем, что в автомате стартовое состояние S и одно заключительное F . Применив достаточное количество раз пункт 2) можем добиться того, что для любой пары состояний имеется не более одной дуги, идущей из первого во второе. Пусть A – состояние, отличное и от S и от F . Пусть в состояние A имеются переходы из состояний B1,…, Bk с метками q1,…, qk, а из состояния A имеются переходы в состояния C1,…,Ct с метками r1,…, rt. Рассматриваем только такие B1,…, Bk,C1,…,Ct , которые отличны от A. При этом какие то из B1,…, Bk могут совпадать с какими-то из C1,…,Ct. Пусть, наконец, метка дуги, идущей из A в A (петля) имеет метку p. Если такой дуги нет, то p = 0. Для дальнейшего это безразлично.

Выкидываем из автомата состояние A со всеми инцидентными ему дугами. Вместо этого из каждого Bi в каждый Cj проводим новую дугу с меткой ri p*qj. Очевидно, что полученный автомат эквивалентен исходному.

Теорема доказана.

Пример 15.1. Рассмотрим регулярное выражение (b*ab*ab*)*. Оно определяет множество всех слов от букв a,b, в которых число букв a четно. Построим соответствующий автомат.

По алгоритму из доказательства теоремы 15.1 автомат для b* есть:

и автомат для a есть:

Соединяя их последовательно получим автомат для b*ab*ab*:

Опять по алгоритму автомат для итерации есть:

Это искомый автомат. Но его хочется упростить.

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

и занесем все в таблицу:

Действуем по алгоритму, описанному в примере 12.3. Например, в шестой строке (с меткой E) в столбце 1 стоит F. В строке F стоят -| H|G. Добавив их к строке E получим таблицу:

Надо делать это многократно, пока добавляются новые элементы. Потом просто стереть столбец 1:

Теперь надо просто стереть столбец 1:

В этом автомате состояния A,B,D,F,G,I,K,L не достижимы. Вычеркнем эти строки и получим:

Этот автомат не детерминированный. Проделаем процедуру перехода к детерминированному с последующей минимизацией. Детерминированный автомат получится такой:

Граф:

Пример 15.2. Возьмем автомат из примера 14.3, который распознает цепочки, содержащие подслова aba или abba:

и построим ему соответствующее регулярное выражение.

Сначала переделываем его в автомат с единственным заключительным состоянием:

Заменяем дуги, соединяющие одни и те же пары состояний, одной дугой:

Удаляем вершину A:

Удаляем вершину B:

Удаляем вершину C:

Удаляем аналогично D,E,F,G:

Объединяем две дуги в одну:

Теперь записываем регулярное выражение r*pt* + (r*pt*qr*pt*)*, в

котором r = a|b|c, p = aba(a|b|c)* | abba(a|b|c)* = ab(a | ba) (a|b|c)*, q = 0, t =

1 :

(a|b|c)*ab(a | ba) (a|b|c)* + 0* = (a|b|c)*ab(1 | b)a (a|b|c)*.

Окончательный ответ: (a|b|c)*ab (1 | b) a (a|b|c)*.

16. ЛЕВОРЕГУЛЯРНЫЕ И ПРАВОРЕГУЛЯРНЫЕ ГРАММАТИКИ

Вспомним, что по определению регулярной грамматикой называется грамматика, правила которой имеют вид Sили S a или S aA. Это определение имеет явный недостаток. Оно не симметрично. Имеются ввиду правила вида S aA. По-другому такие грамматики называют праворегулярными. Мы знаем, что любой регулярный язык определяется конечным автоматом. Определение же автомата на первый взгляд выглядит вполне симметричным. К сожалению, это впечатление обманчиво. Просто несимметричность не так заметна. На самом деле работа автомата точно согласуется именно с праворегулярными грамматиками.

Что получится, если рассмотреть леворегулярные грамматики – каждое правило которых имеет один из видов: S , S a,S Aa ? Этот класс ничем на хуже класса регулярных. А ему соответствующие автоматы такие же, как обычные, но! Они читают ленту не слева направо, а справа налево!

Любую праворегулярную грамматику G можно переделать в леворегулярную просто заменив каждое правило S aA на правило S Aa. Обозначим эту грамматику за Gleft. Очевидно, слово тогда и только тогда принадлежит языку G, когда inv принадлежит языку Gleft. Здесь inv обо-

ределяется регулярным выражением rinv , которое получено из r по правилам:

1)ainv = a для a T, 0inv = 0 , 1inv = 1;

2)(r)inv = (rinv );

3)(r*)inv = (rinv )*;

4)(r+q)inv = qinv + rinv;

5)(rq)inv = qinv rinv ;

Проще говоря, rinv - это переписывание r в обратном порядке, но не теряя при этом здравый смысл.

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

Теорема 16.1. Любой праворегулярный язык является леворегулярным и наоборот.

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

Таким образом, несимметрия в определении регулярных языков устранена. Классы леворегулярных и праворегулярных языков совпадают.

Пример 16.1. Найдем по грамматике G

S D | E

DDa |Ba

BBb | b

EEc | c

эквивалентную регулярную грамматику.

Пусть L = L(G). Видим, что G – это леворегулярная грамматика. Пусть Gright - праворегулярная

S D | E

DaD | aB

BbB | b

EcE | c

определяющая язык Linv. Действуем по следующему плану:

1.По Gright строим конечный автомат A, определяющий язык Linv.

2.По A находим регулярное выражение r, определяющее Linv.

3.Строим регулярное выражение rinv, определяющее L.

4.По rinv строим автомат Ainv, определяющий L.

5.По Ainv строим регулярную грамматику, определяющую L.

1.Избавимся в Gright от цепочных правил. Получим грамматику

S aD | aB| cE | c D aD | aB

B bB | b E cE | c

Автомат A задается графом (см. доказательство теоремы 12.1):