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

Конечные автоматы

·  Введение

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

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

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

2.  Поскольку при моделировании конечного автомата на вычислительной машине обработка одного входного символа требует небольшого количества операций, программа работает быстро.

3.  Моделирование конечного автомата требует фиксированного объема памяти, что упрощает проблемы, связанные с управлением памятью.

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

Термин «конечный автомат» в действительности употребляется в разных смыслах — в зависимости от подразумеваемых приложений. В литературе по теории автоматов существует несколько различных формальных определений. Общим в этих определениях является то, что они моделируют вычислительные устройства с фиксированным и конечным объемом памяти, которые читают последовательности входных символов, принадлежащих некоторому конечному множеству. Принципиальные различия в определениях связаны с тем, что автоматы делают на выходе. Следующий раздел начинается с рассмотрения конечного автомата, единственным «выходом» которого является указание на то, «допустима» или нет данная входная цепочка (последовательность символов). «Допустимой» мы называем «правильно построенную» или «синтаксически правильную» цепочку; например, цепочка, которая должна изображать числовую константу, построена не правильно, если содержит две десятичные точки.

2.2.  Конечные распознаватели

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

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

На вход конечного автомата подается цепочка символов из конечного множества, называемого входным алфавитом автомата и представляющего собой совокупность символов, для работы с которыми он предназначен. Как допускаемые, так и отвергаемые автоматом цепочки состоят только из символов входного алфавита. Символы, не принадлежащие входному алфавиту, нельзя подавать на вход автомата. Входной алфавит контролера нечетности состоит из двух символов: 0 и 1.

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

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

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

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

Работу автомата можно описать математически с помощью функции δ, называемой функцией переходов. По текущему состоянию Sтек и текущему входному символу х она дает новое состояние автомата Sнов. Символически эта зависимость описывается так:

δ (Sтек, х) = Sнов

Учитывая, что состояния ЧЕТ и НЕЧЕТ означают соответственно четное и нечетное число прочитанных единиц, определим функцию переходов контролера нечетности следующим образом:

δ (ЧЕТ, 0) = ЧЕТ

δ (ЧЕТ, 1) = НЕЧЕТ

δ (НЕЧЕТ, 0) = НЕЧЕТ

δ (НЕЧЕТ, 1) = ЧЕТ

Эта функция переходов отражает тот факт, что четность меняется тогда и только тогда, когда на входе читается единица.

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

Суммируя все сказанное, можно дать следующее определение конечного распознавателя.

Конечный автомат задается:

1)  конечным множеством входных символов,

2)  конечным множеством состояний,

3)  функцией переходов δ, которая каждой паре, состоящей из входного символа и текущего состояния, приписывает некоторое новое состояние,

4)  состоянием, выделенным в качестве начального, и

5)  подмножеством состояний, выделенных в качестве допускающих или заключительных.

Переход автомата из состояния Sтек в состояние Sнов при чтении входного символа х будем наглядно изображать так:

Sтек х Sнов

Для контролера нечетности, например, можно написать

НЕЧЕТ 1 ЧЕТ

Аналогичным образом можно изобразить последовательность переходов. Например, запись

ЧЕТ 1 НЕЧЕТ 1 ЧЕТ 0 ЧЕТ 1 НЕЧЕТ

показывает, как автомат в состоянии ЧЕТ применяется к цепочке 1101. Первый символ 1 меняет состояние ЧЕТ на НЕЧЕТ, так как δ (ЧЕТ, 1) = НЕЧЕТ. Следующая единица меняет НЕЧЕТ на ЧЕТ. Нуль оставляет автомат в состоянии ЧЕТ. Последняя единица изменяет состояние на НЕЧЕТ. Так как ЧЕТ — начальное, а НЕЧЕТ— допускающее состояние, цепочка 1101 допускается нашим автоматом.

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

ЧЕТ 1 НЕЧЕТ 0 НЕЧЕТ 1 ЧЕТ

Иногда мы хотим говорить о множестве всех цепочек, распознаваемых некоторым конечным автоматом. Например, контролер нечетности распознает множество цепочек, состоящих из нулей и единиц и содержащих нечетное число единиц. Такие множества обычно называют «регулярными».

Регулярным множеством называется множество цепочек, которое распознается некоторым конечным распознавателем.

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

  Таблица переходов

Один из удобных способов представления конечных автоматов – таблица переходов. Для контроллера нечетности такая таблица изображена на рис. 2.1. Информация размещается в таблице переходов в соответствии со следующими соглашениями:

1.  Столбцы помечены входными символами.

2.  Строки помечены символами состояний.

3.  Элементами таблицы являются символы новых состояний, соответствующих входным символам столбцов и состояниям строк.

4.  Первая строка помечена символом начального состояния.

5.  Строки, соответствующие допускающим (заключительным)состояниям, помечены справа единицами, а строки, соответствующие отвергающим состояниям, помечены справа нулями.

	0	1
ЧЕТ	ЧЕТ	НЕЧЕТ	0
НЕЧЕТ	НЕЧЕТ	ЧЕТ	1

Рис. 2.1.

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

входное множество = {0, 1},

множество состояний = {ЧЕТ, НЕЧЕТ},

переходы δ (ЧЕТ, 0) = ЧЕТ и т. д.,

начальное состояние = ЧЕТ,

допускающие состояния = {НЕЧЕТ}.

	X	y	z
1	1	3	4	1
2	2	1	3	0
3	2	4	4	1
4	3	3	3	0

Входное множество = { х, у, z}

множество состояний = {1,2,3,4}

переходы δ (1, х) = 1, δ (1,у) = 3 и т. д.

начальное состояние = 1

допускающие состояния = {1, 3}

Рис. 2.2.

Еще один автомат изображен на рис. 2.2. Входная цепочка xyzz допускается этим автоматом, так как

1 x 1 y 3 z 4 z 3

и 3 является допускающим состоянием, тогда как цепочка zyx отвергается, потому что

1 z 4 y 3 x 2

и 2 — отвергающее состояние.

  Концевые маркеры и выходы из распознавания

а	b
1	1	2	1
2	E	1	0
E	E	E	0
Рис. 2.3.

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

Рассмотрим автомат, изображенный на рис. 2.3. Он допускает множество цепочек в алфавите {а, b}, таких, что символы b в них либо не встречаются, либо встречаются парами. Например, этот автомат допускает цепочки abb, abba, aaa, abbbbabb, bba, но отвергает baa, abbb и abbab. Состояние 1 «помнит», что обработанная часть цепочки допустима. Если после допустимой части цепочки следует символ b, автомат переходит в состояние 2. В состояние Е он переходит, когда входная цепочка окончательно испорчена вхождением символа а вслед за «неспаренным» b. Таким образом, состояние Е можно назвать «состоянием ошибки», которое запоминает, что обнаружена ошибка.

Пусть теперь нам нужно построить программу или «компилятор», который, прочитав цепочку или «программу» в алфавите {а, b}, вызывает процедуру «ДА», если цепочка принадлежит множеству, распознаваемому автоматом рис. 2.3, и процедуру «НЕТ» в случае, когда цепочка не принадлежит этому множеству. Хотелось бы, конечно, чтобы наш компилятор имитировал работу автомата простым и естественным способом, поскольку именно это мы имели в виду, когда утверждали, что конечный автомат лежит в основе теории построения компиляторов. Однако очевидно, что в модели автомата, изображенного на рис. 2.3, не отражена идея «окончания» входной цепочки. Например, должен ли компилятор после прочтения символов abb выйти из процесса распознавания и перейти на процедуру «ДА», поскольку обработанная часть цепочки принадлежит заданному множеству, или он должен ждать появления дальнейших символов? Если за abb следуют символы bа, то, обработав всю цепочку abbba, автомат должен выйти на процедуру «НЕТ».

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

$BEGIN

a

b

b

$END

Если работа идет в режиме разделения времени, то маркер конца файла устанавливается операционной системой. Если весь вход задается на одной перфокарте, то конец файла можно обнаружить, используя тот факт, что число символов на карте не больше 80.

A b —|

1 2 E

1	2	ДА
НЕТ	1	НЕТ

1	2	ДА
E	1	НЕТ
E	E	НЕТ

1 2

a b —|

а б

Рис. 2.4.

В описанных выше ситуациях будем считать, что цепочка, подаваемая на вход автомата, имеет концевой маркер. Пусть это будет символ —|. Тогда цепочка abb поступит на вход автомата в виде

abb —|

Автомат, изображенный на рис. 2.3, нужно изменить так, чтобы он умел обрабатывать дополнительный символ —|. Преобразованный автомат изображен на рис. 2.4, а. Символ «ДА» — это сокращенное указание на то, что работа закончена, и автомат должен выйти на процедуру «ДА». Новое состояние не наступает, так как на этом автомат свою работу заканчивает.

С введением концевого маркера необходимо заметить, что следует различать алфавит обрабатываемого языка и входной алфавит автомата, осуществляющего обработку. В рассматриваемом примере алфавит языка по-прежнему {а,b} и концевой маркер в описании языка не участвует. Входным алфавитом автомата, распознающего этот язык (рис. 2.3), также остается {а,b}, тогда как входным алфавитом автомата, обрабатывающего тот же язык (рис. 2.4,а), будет {а,b, —|}.

Метод, с помощью которого мы получили обрабатывающий автомат из распознающего, очень прост. Мы добавили столбец, помеченный концевым маркером, и поместили «ДА» в строки, соответствующие допускающим состояниям, и «НЕТ» — в строки, соответствующие отвергающим состояниям. Ясно, что этим же способом 'каждый распознаватель может быть преобразован в обрабатывающий автомат. Поэтому очевидно, что любая техника построения конечных распознавателей потенциально применима и при построении обрабатывающих автоматов (процессоров).

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

Допустим, нам хочется построить автомат, который при обнаружении первой же ошибки передает управление некоторой внешней процедуре, обрабатывающей ошибки. Эта процедура либо прерывает процесс обработки цепочки, либо восстанавливает нужное состояние и возобновляет обработку с целью обнаружения дальнейших ошибок. Возвращаясь к рис. 2.4, а, напомним, что если автомат попал в состояние Е, то входная цепочка будет отвергнута. Поэтому первый же переход в это состояние означает, что обнаружена ошибка. Если мы решили прерывать процесс, как только обнаружена ошибка, то все переходы в состояние Е в таблице переходов нужно заменить вызовами процедуры «НЕТ». Результат замены изображен на рис. 2.4, б. Состояние Е удалено из автомата, так как отсутствие переходов в него означает, что автомат никогда не достигнет этого состояния, исходя из начального. Первоначально состояние Е было введено, чтобы обеспечить дочитывание входной цепочки после того, как обнаружена ошибка. Теперь в нем нет надобности, так как мы решили, что при обнаружении ошибки автомат должен выходить из процесса распознавания.

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

Детекция может встречаться при обработке как допустимых, так и ошибочных цепочек. Рассмотрим, например, задачу распознавания цепочек из нулей и единиц, содержащих хотя бы одну пару стоящих рядом единиц. Соответствующий распознаватель показан на рис. 2.5, а. Он переходит в состояние С при обнаружении пары 11.

0	1
А	А	В	0
В	А	С	0
С	С	С	1
а

0	1	—|
А	А	В	НЕТ
В	А	ДА	НЕТ
б

Рис. 2.5.

Если мы хотим получить распознаватель, который выходит на «ДА», как только обнаружена пара единиц, то переходы в состояние С нужно заменить на «ДА». Распознаватель рис. 2.5а превратится, таким образом, в процессор, изображенный на рис. 2.5б. В нем нет состояния С, так как переходы в него отсутствуют.