Конечные автоматы (стр. 7 )

1)  конечным множеством входных символов, в которое входит концевой маркер;

2)  конечным множеством магазинных символов, включающим маркер дна;

3) конечным множеством состояний, включающим начальное состояние;

4) управляющим устройством, которое каждой комбинации входного символа, магазинного символа и состояния ставит в соответствие выход или переход. Переход в отличие от выхода заключается в выполнении операций над магазином, состоянием и входом, как было описано выше. Операции, которые запрашивали бы входной символ после концевого маркера или выталкивали из магазина, а также вталкивали в него маркер дна, исключаются;

5) начальным содержимым магазина, которое представляет собой (при условии, что верхний символ считается расположенным справа) маркер дна, за которым следует (возможно, пустая) цепочка других магазинных символов.

МП-автомат называется МП-распознавателем, если у него два выхода — ДОПУСТИТЬ и ОТВЕРГНУТЬ. Говорят, что цепочка символов входного алфавита (исключая концевой маркер) допускается распознавателем, если под действием этой цепочки с концевым маркером автомат, начавший работу в своем начальном состоянии и с начальным содержимым магазина, делает ряд переходов, приводящих к выходу ДОПУСТИТЬ. В противном случае цепочка отвергается,

При описании переходов МП-автомата будем обозначать действия автомата словами ВЫТОЛКНУТЬ (или для краткости ВЫТОЛК), ВТОЛКНУТЬ (или ВТОЛК), СОСТОЯНИЕ, СДВИГ и ДЕРЖАТЬ, причем:

ВЫТОЛКНУТЬ означает вытолкнуть верхний символ магазина,

ВТОЛКНУТЬ (А), где А — магазинный символ, означает втолкнуть символ А в магазин,

СОСТОЯНИЕ (s), где s — состояние, означает, что следующим состоянием становится s,

СДВИГ означает, что текущим входным символом становится следующий входной символ. В некоторых реализациях это может означать сдвиг указателя на входе,

ДЕРЖАТЬ означает, что текущий входной символ надо держать до следующего шага, т. е. оставить его текущим (в некоторых реализациях — оставить указатель на прежнем месте).

Когда нам нужно определить переход, который оставляет содержимое магазина неизменным, это выражается в том, что мы опускаем слова ВЫТОЛКНУТЬ и ВТОЛКНУТЬ. Хотя ДЕРЖАТЬ по существу означает, что СДВИГ отсутствует, мы всегда будем записывать операции над входом в явном виде, чтобы читателю было понятнее, что происходит. Если автомат содержит в точности одно состояние, мы будем опускать слово СОСТОЯНИЕ.

Сейчас мы опишем, как применить МП-распознаватель к проблеме скобок. Каждый раз, когда встречается левая скобка, в магазине будет вталкиваться символ А. Когда будет обнаружена соответствующая правая скобка, символ А будет выталкиваться из магазина. Цепочка отвергается, если на входе остаются правые скобки, а магазин пуст (т. е. во входной цепочке есть лишние правые скобки) или если цепочка прочитана до конца, а в магазине остаются символы А (т. е. входная цепочка содержит лишние левые скобки). Цепочка допускается, если к моменту прочтения входной цепочки до конца магазин опустошается. Полное определение таково:

1.  Входное множество {(,), —|}.

2.  Множество магазинных символов {А, s}.

3.  Множество состояний {s}, где s — начальное состояние.

4.  Переходы:

(, A, s = ВТОЛКНУТЬ (A), СОСТОЯНИЕ (s), СДВИГ

(,s, s = ВТОЛКНУТЬ (A), СОСТОЯНИЕ (s), СДВИГ

), A, s = ВЫТОЛКНУТЬ, СОСТОЯНИЕ (s), СДВИГ

),s, s = ДЕРЖАТЬ

—|, A, s = ДЕРЖАТЬ

—|,s, s = ДОПУСТИТЬ

Здесь комбинации входного символа, магазинного символа и состояния расположены слева от знака равенства, а переходы — справа от него.

5.  Начальное содержимое магазина s.

Чтобы продемонстрировать работу автомата, мы изобразили на Рис. 5.3, как он обрабатывает цепочку

(

 

Рис. 5.3.

На рисунке показан каждый шаг процесса обработки, начиная с начальной конфигурации на рис. 5.3, а и кончая допускающей конфигурацией на рис. 5.3, з. Такое изображение последовательности конфигураций МП-автомата требует много места, поэтому представим ее в таком более компактном виде:

В этом линейном представлении конфигураций МП-автомата магазин изображен слева, состояние — в середине, а необработанная часть входной цепочки — справа. Эта часть входной цепочки включает текущий входной символ и символы, которые следуют после него.

ВТОЛКНУТЬ(А) СДВИГ	ВЫТОЛКНУТЬ СДВИГ	ОТВЕРГНУТЬ
ВТОЛКНУТЬ(А) СДВИГ	ОТВЕРГНУТЬ	ДОПУСТИТЬ

Рис. 5.4.

Чтобы восстановить всю входную цепочку, нужно вернуться назад, к исходной конфигурации. Информацию, поступающую в управляющее устройство, выделить очень легко, так как символ, расположенный на верху магазина, находится непосредственно слева от состояния, а текущий входной символ — справа от него. Многие из МП-автоматов, применяемых на практике, имеют лишь одно состояние (как в этом примере), и в подобных случаях мы, как правило, опускаем информацию, касающуюся состояний.

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

Мы будем пользоваться таблицами такого вида (т. е. со столбцами для входных символов и строками для символов магазина) как стандартным представлением МП-автоматов с одним состоянием.

5.2. Некоторые обозначения для множеств цепочек

Чтобы привести несколько примеров обработки множеств цепочек МП-автоматом, мы введем некоторые обозначения. Начнем с определения трех операций над множествами цепочек. Применяя эти операции к множествам цепочек, мы получаем другие множества цепочек. Эти три операции — объединение, конкатенация и итерация Клини (или просто итерация).

Объединение. Если Р и Q — множества цепочек, то объединение Р и Q — это множество цепочек, которые принадлежат Р или Q или обоим множествам одновременно. Хотя обычное теоретико-множественное обозначение для объединения — это Р U Q, в теории автоматов объединение множеств часто обозначается как P+Q. Некоторые примеры объединения:

{FOR, IF, THEN} + {DO, IF} = {FOR, IF, THEN, DO};

{AB, X3} + {Y, ε} = {AB, X3, У, ε};

{все цепочки из нулей и единиц, начинающиеся с 0 и заканчивающиеся 1}

+ {все цепочки из нулей и единиц, начинающиеся с 0 и заканчивающиеся 0}

= {все цепочки из нулей и единиц, начинающиеся с 0};

{простые переменные Алгола}

+ {переменные с индексами Алгола}

= {переменные Алгола}.

Конкатенация. Конкатенация, или сцепление двух цепочек, определяется как цепочка, получаемая их соединением, или «приписыванием», друг к другу. Конкатенацией цепочек ОКРЕСТ и НОСТЬ, например, является цепочка ОКРЕСТНОСТЬ. Длина получившейся цепочки равна сумме длин цепочек, участвующих в конкатенации. Так как длина пустой цепочки равна нулю, то в результате ее конкатенации с любой цепочкой последняя не изменится. Например, конкатенацией цепочек ОКРЕСТ и ε остается цепочка ОКРЕСТ длины шесть.

Конкатенацию как операцию над цепочками можно расширить до операции над множествами цепочек. Если P и Q — множества цепочек, то конкатенацией P и Q называется множество, состоящее из всевозможных конкатенации цепочек из P с цепочками из Q. Конкатенация множеств P и Q обозначается P . Q. Точку можно, однако, опускать и писать PQ. Некоторые примеры конкатенации:

{10} {1, 00} = {101, 1000};

{AB, X, ABY}{ε, Y} = {AB, X, ABY, XY, ABYY};

(все буквы} {все цепочки из букв и цифр} =

= {все цепочки, начинающиеся с буквы, за которой следует цепочка из букв и цифр}.

Конкатенация множества R с самим собой, т. e. RR или R . R, обозначается также R2. Например {0, 11}2 = {00, 011, 110, 1111}. Аналогично Ri, где i — целое положительное число, обозначает множество R . R . … . R. Удобно считать, что

R0 = { ε }.

Это определение согласуется с правилом умножения степеней, а именно

Ri . Rj = Ri+j,

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

Итерация Клини. Полезно иметь обозначение для множества всех цепочек, состоящих из символов данного алфавита. Если А — множество символов алфавита, то будем говорить, что А*— множество всех цепочек, составленных из символов множества А. Предполагается, в частности, что А* всегда содержит пустую цепочку ε. Так, {0, 1}* обозначает множество всех цепочек в алфавите {0, 1}.

Описанная операция называется итерацией Клини или просто итерацией.

Итерацию Клини как операцию над алфавитами можно расширить до операции над другими множествами цепочек. Например, {IF, THEN} * обозначает бесконечное множество цепочек, которое включает ε, IF, THEN, IFIF, THENIFTHEN, IF THENIFIF.

Если R — множество цепочек, то мы определим множество R* бесконечным рядом

R* = R0 + R1 + R2 + ... .

В этом выражении + обозначает, разумеется, рассмотренную ыше операцию объединения.

Часто используется вариант итерации Клини, обозначаемый А+ и называемый позитивной итерацией. Если А — некоторое множество цепочек, то множество А+ определяется равенством

А+ = АА*

Таким образом, А+ можно выразить как

А+ = А1 + А2 + А3 + … .

Множество А+ в точности совпадает с множеством А*, за исключением того, что А+ содержит пустую цепочку лишь тогда, когда ее содержит А.

Эти три операции обладают тем свойством, что при их применении к регулярным множествам получается регулярное множество. (Регулярным называется множество, которое можно распознать конечным автоматом.) На самом деле любое регулярное множество цепочек в данном алфавите можно получить путем применения этих трех операций к символам алфавита. В оставшейся части данного раздела мы дополним эти операции некоторыми способами задания множеств, позволяющими получать нерегулярные множества.

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

{1n0n | n > 0}

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

10

111000

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

Еще один пример:

{1n0m | n m > 0}

Эта формула обозначает множество цепочек, состоящих из некоторого числа единиц, за которыми следует такое же или меньшее число нулей; сюда входят, например, цепочки

111000

1110

Аналогичным образом множество

{anbmcmdn | n , m > 0}

состоит из цепочек, в которых после некоторого числа символов а следует некоторое число символов b, затем – некоторое число символов c и некоторое число символов d, причем число символов а равно числу символов d, а число b совпадает с числом c. Этому множеству принадлежат такие, например, цепочки:

abbccd

aaabbbccccddd

Второй способ – это обозначение операции обращения цепочки с помощью верхнего индекса r. Так, например

(abc)r = cba.

Используя операцию обращения, мы можем писать формулы вроде

{w, wr|w принадлежит множеству (0+1)*},

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

0000

Хотя эти новые способы обозначения позволяют задавать нерегулярные множества и описывать работу некоторых МП-автоматов, они не достаточно общие, чтобы описывать реальные языки программирования. Поэтому примерам и упражнениям этой главы недостает непосредственной практической мотивировки с точки зрения языков программирования. Тем не менее их достаточно для выработки правильного интуитивного понимания процессов обработки цепочек с помощью МП-автоматов.

5.3  Пример распознавания множества МП-автоматом

Чтобы привести еще один пример распознавания МП-автоматом, использующим более чем одно состояние, рассмотрим задачу распознавания множества

{0n1n|n>0}.

В качестве первого шага построения МП-распознавателя опишем словами схему распознавания:

Начальный отрезок цепочки, состоящей из нулей, вталкивается в магазин. Затем каждый раз, когда встречается единица, один нуль выталкивается из магазина. Цепочка допускается тогда и только тогда, когда в момент завершения считывания цепочки магазин пуст. Если после первого вхождения единицы встречается нуль, цепочка сразу отвергается.

—|

[s1]

1: s

a

 

 

б

 

Рис. 5.5.

0 1 —|

 

Z Состояние 1 s   СОСТОЯНИЕ (S1) ВТОЛКНУТЬ (Z) СДВИГ	СОСТОЯНИЕ (S2) ВЫТОЛКНУТЬ СДВИГ	ОТВЕРГНУТЬ
СОСТОЯНИЕ (S1) ВТОЛКНУТЬ (Z) СДВИГ	ОТВЕРГНУТЬ	ОТВЕРГНУТЬ

0 1 —|

Z Состояние 2 s

 

ОТВЕРГНУТЬ	СОСТОЯНИЕ (S2) ВЫТОЛКНУТЬ СДВИГ	ОТВЕРГНУТЬ
ОТВЕРГНУТЬ	ОТВЕРГНУТЬ	ДОПУСТИТЬ

Начальное содержимое магазина: s

Рис. 5.6.

Чтобы реализовать эту схему, нужно завести магазинный символ, представляющий входной символ 0. Хотя в качестве магазинного символа можно использовать сам нуль, во избежание путаницы мы предпочитаем пользоваться символом Z. Процесс обработки распадается на две фазы. Первая из них — фаза «вталкивания»; в этой фазе нули, начинающие цепочку, помещаются в магазин. Эти нули представляются магазинными символами Z. Вторая фаза — фаза «выталкивания»; здесь при появлении единицы из магазина удаляется Z, а при появлении нуля, цепочка немедленно отвергается. Чтобы автомат «помнил», в какой фазе он находится, мы введем два состояния s1 и s2, соответствующие этим фазам.

Прежде чем детально определить управление МП-автоматом, посмотрим, как он работает, на примере последовательности конфигураций, возникающей при обработке цепочки , которую он допускает. Эта последовательность конфигураций показана на рис. 5.5, а. Мы изобразили также на рис. 5.5, б последовательность конфигураций автомата, отвергающую цепочку После конфигурации 3 на рис. 5.5, б автомат переходит в состояние s2, запоминая, что началась фаза выталкивания. Затем, встретив на входе нуль, он отвергает цепочку.

Один из удобных способов описания механизма управления заключается в том, чтобы задавать множество управляющих таблиц, по одной для каждого состояния, причем каждая таблица имеет стандартный вид с одним состоянием. Две управляющие таблицы для нашего примера изображены на рис. 5.6. Чтобы установить, какое действие должно выполняться для данной комбинации состояния, входа и магазинного символа, нужно сначала найти управляющую таблицу для данного состояния, а затем по входному и магазинному символам определить нужное действие в выбранной управляющей таблице. На рис. 5.6 комбинация s2, 1, Z вызывает выполнение операций СОСТОЯНИЕ (s2), ВЫТОЛКНУТЬ, СДВИГ.

В итоге полное определение МП-автомата, распознающего множество {0n1n|n>0}, таково:

1)  входное множество {0, 1, —|),

2)  множество магазинных символов {Z, s).

3)  множество состояний {s1, s2}, где s1 — начальное состояние,

4)  переходы, изображенные на рис. 5.6,

5)  начальное содержимое магазина s.

5.4. Расширенные операции над магазином

На самом деле имеется много разных способов определения класса моделей автоматов, переходы которых выбираются в зависимости от входа, состояния и верхних магазинных символов, а операции затрагивают только верхнюю часть магазина. Каждую из этих моделей принято называть автоматом с магазинной памятью. Таким образом, модель автомата, описанная в разд. 5.1,— это как раз пример модели МП-автомата.

В тех случаях, когда может возникнуть недоразумение, мы будем называть МП-автоматы такого типа примитивными МП-автоматами.

Есть несколько причин для того, чтобы начать изучение МП-автоматов с примитивной модели. Одна из них в том, что принципы МП-обработки проявляются в этой модели в простейшей форме. Вторая причина заключается в том, что эта модель — математически определенное понятие, которое можно применять при доказательстве теорем или при решении задач, приведенных в конце этой главы. Она служит стандартной моделью в том смысле, что термин «МП-автомат» сохраняется для всех автоматов, которые используют магазин аналогичным образом и обладают той же способностью распознавания (например, могут распознавать те же множества), что и примитивные МП-автоматы.

Мы называем примитивные автоматы «примитивными» по той причине, что их переходы включают не более одной операции вталкивания или выталкивания. Эти операции можно было бы использовать при аппаратной реализации МП-автомата в некоторой реальной машине. Однако, если МП-автомат взять за основу при разработке программной реализации алгоритмов, эти операции оказываются неестественно ограниченными. В данном разделе мы будем рассматривать операции над магазином с точки зрения их программирования.

Как только по состоянию, магазинному символу и входу выбран переход, с точки зрения программирования разумно сделать как можно больше, прежде чем вновь обращаться к управляющей, информации и выбирать новый переход. Другими словами, разработчик может захотеть связать с переходами более общие процедуры и не ограничивать работу с магазином операциями вталкивания и выталкивания одного символа. Предположим, например, что надо поместить в магазин два символа. При желании можно втолкнуть в магазин первый символ и перейти в состояние, единственное назначение которого — поместить в магазин второй символ при следующем переходе. Однако этот метод с двумя переходами является неэффективным и неестественным по сравнению с другим очевидным, методом, когда оба вталкивания выполняются одной процедурой перехода. Так как переход с двумя вталкиваниями можно промоделировать с помощью двух переходов примитивного МП-автомата, мы можем назвать такое вталкивание двух символов «расширенной операцией над магазином», а термин МП-автомат распространим на устройства, которые могут вталкивать в магазин по два символа сразу.

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

В этом разделе мы введем расширенную операцию над магазином, назовем ее ЗАМЕНИТЬ и проиллюстрируем ее использование. Другие расширенные операции будут вводиться в последующих главах по мере надобности.

Операция ЗАМЕНИТЬ состоит в выталкивании верхнего символа магазина и последующем выполнении нескольких вталкиваний. Последовательность символов, которые операция ЗАМЕНИТЬ должна помещать в магазин, указывается в качестве ее аргумента. Так, мы пишем

ЗАМЕНИТЬ (ABC)

если в магазин нужно поместить ABC. Это эквивалентно последовательности операций

ВЫТОЛКНУТЬ

ВТОЛКНУТЬ(A)

ВТОЛКНУТЬ(В)

ВТОЛКНУТЬ(С)

Таким образом, левый символ последовательности помещается в магазин первым и оказывается ниже остальных символов этой последовательности. Если операция ЗАМЕНИТЬ (ABC) применяется к магазину

s X Y Z

то новый магазин выглядит так:

s X Y А В С

Операция ЗАМЕНИТЬ широко и систематически используется в последующих главах. В данный момент мы рассматриваем ее просто как сокращение для последовательности примитивных операций над магазином, которую программист может включить как часть одной процедуры перехода.

Чтобы проиллюстрировать использование операции ЗАМЕНИТЬ, вернемся к задаче распознавания множества {0n1n|n>0}. В разд. 5.3 мы видели, что можно построить распознаватель, который работает в двух фазах — «вталкивания» и «выталкивания». Мы строили такой автомат, пользуясь для запоминания фазы управляющим состоянием. Теперь для этой же задачи построим другой МП-автомат.

Новый МП-автомат использует тот же метод счета, что и предыдущий автомат. Z вталкивается в магазин при каждом появлении на входе символа 0 и выталкивается из него при каждом появлении на входе символа 1. Однако для различения фаз вталкивания и выталкивания используется иная стратегия.

0 1 —|

X Z s

 

ЗАМЕНИТЬ (ZX) СДВИГ	вытолкнуть ДЕРЖАТЬ	ОТВЕРГНУТЬ
ОТВЕРГНУТЬ	ВЫТОЛКНУТЬ сдвиг	ОТВЕРГНУТЬ
ОТВЕРГНУТЬ	ОТВЕРГНУТЬ	допустить

Начальное содержимое магазина: s X

Рис. 5.7.

Во время фазы вталкивания в верхней ячейке магазина хранится новый магазинный символ X. Единственное его назначение — напоминать управляющему устройству, что автомат находится в фазе вталкивания. Когда впервые встречается единица, X выталкивается из магазина и автомат начинает сопоставлять символы Z и единицы. Наличие процедуры ЗАМЕНИТЬ позволяет нам реализовать этот алгоритм с помощью единственного состояния, как показано на рис. 5.7. Последовательность конфигураций при распознавании цепочки показана на рис. 5.8. Эту последовательность конфигураций можно сравнить с рис. 5.5, а, где изображена обработка этой же цепочки предыдущим автоматом.

1:	s X	—|
2:	s Z X	—|
3:	s Z Z X	—|
4:	s Z Z Z X	1 1 1 —|
5:	s Z Z Z	1 1 1 —|
6:	s Z Z	1 1 —|
7:	s Z	1 —|
8:	s	—|
9:	ДОПУСТИТЬ

Рис. 5.8.