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

2.5.  Пример построения автомата

Чтобы продемонстрировать автоматную технику на конкретном примере, построим автомат для распознавания цепочек, которые могут следовать за словом INTEGER в операторах спецификации Фортрана. Примеры таких операторов:

INTEGER A

INTEGER X, I(3)

INTEGER С (3, J, 4), В

Будем считать, что массивы могут иметь любую размерность, хотя в большинстве стандартов и компиляторов с Фортрана она ограничена. Входной алфавит будет состоять из пяти символов:

v с, ( )

где v — лексема, означающая произвольную переменную, с — лексема, соответствующая целочисленной константе (см. разд. 1.2). Будем считать, что эти лексемы порождаются каким-то другим автоматом.

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

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

INTEGER А ( 3 , J, 4 ) , В

7 8 2

Рис. 2.6.

Заметим, что две запятые помечены номером 5. Действительно, цепочка

4 ) , В

которая следует за второй запятой, могла встретиться и после первой запятой, образуя допустимую цепочку

INTEGER A (3, 4), В

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

INTEGER A (3, В

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

Роли, встречающиеся в нашем примере, словами могут быть описаны так:

2  — имя переменной, описываемой как INTEGER;

3  — левая скобка;

4  — целое число, задающее размерность;

5  — запятая, разделяющая размерности;

6  — переменная, задающая переменную размерность;

7  — правая скобка;

8  — запятая, разделяющая объекты, описываемые как целые.

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

После того как все роли опознаны, дальше автомат можно строить по следующему алгоритму:

1.  Ввести начальное состояние и состояние ошибки

2.  Ввести состояние для каждой роли.

3.  Поместить в таблицу переходы из одного состояния в другое, если соответствующие роли могут следовать одна за другой.

4.  Пополнить таблицу переходами в состояние ошибки.

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

	V	с	,	(	)
1	2	E	E	E	E	0
2	E	E	8	3	E	1
3	6	4	E	E	E	0
4	E	E	5	E	7	0
5	6	4	E	E	E	0
6	E	E	5	E	7	0
7	E	E	8	E	E	1
8	2	E	E	E	E	0
E	E	E	E	E	E	0
Рис. 2.7.

В нашем примере на первом шаге вводится начальное состояние 1 и состояние ошибки Е. На втором шаге мы вводим состояния 2—8, соответствующие ролям, выявленным при интуитивном анализе.

Затем на шаге 3 получаем все нужные переходы. Заметим, что первым символом каждой допустимой цепочки должна быть переменная в роли 2, поэтому заносим в таблицу переход от начального состояния 1 в состояние 2 при чтении входного символа и. Этот

элемент мы видим в таблице, изображенной на рис. 2.7, где показан конечный результат нашего построения. За вхождением символа с ролью 2 может следовать либо вхождение с ролью 3 (как в цепочке на рис. 2.6), либо с ролью 8 (как в цепочке INTEGER А, В). Поэтому для соответствующих входных символов помещаем в таблицу переходы из 2 в 3 и из 2 в 8. Завершая этот анализ, во все остальные ячейки таблицы заносим переходы в состояние Е.

И наконец, выполняем шаг 5. Заметим, что символы, стоящие в конце допустимых цепочек, могут иметь роль 2 или 7, поэтому объявляем состояния 2 и 7 допускающими и на этом завершаем построение таблицы.

Одно из возражений против предложенного метода состоит в том, что построенный автомат не обязательно будет наилучшим в том смысле, что может найтись другой автомат с меньшим числом состояний, который определяет то же множество цепочек. Позднее мы убедимся в том, что автомат, изображенный на рис. 2.7, действительно не является наилучшим. Это возражение будет устранено в разд. 2.11, где будет дан алгоритм приведения произвольного конечного автомата к оптимальному виду.

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

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

2.6.  Пустая цепочка

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

1)  состоит из следующих друг за другом символов,

2)  образуется сцеплением символов.

Однако все это, в сущности, сводится к определению: «цепочка — это последовательность символов». Поэтому будем считать, что читатель не раз имел дело с цепочками и знает, что это такое.

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

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

$BEGIN

$END

Если мы хотим, чтобы пустую цепочку обработал один из автоматов разд. 2.4, необходимо добавить к ней справа концевой маркер, т. е. На вход автомата поступит цепочка

—|

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

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

В терминах переходов это означает, что пустая цепочка, примененная к начальному (или к любому другому состоянию), не вызывает никаких переходов, т. е. Оставляет состояние неизменным. Таким образом, под действием пустой цепочки, примененной к начальному состоянию, распознаватель заканчивает работу в начальном состоянии, которое и определяет допустимость цепочки. Последовательность переходов для пустой цепочки, примененной к произвольному состоянию s, выглядит так:

s

Следовательно, если первое состояние в этой последовательности (s) является начальным, а последнее (тоже s) — допускающим, то пустая цепочка допускается.

Пустая цепочка часто встречается в описаниях языков программирования. Так, в Алголе 60 допустим пустой оператор, т. е. Пустая цепочка.

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

ε =

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

T	T
T	T

Пустую цепочку путают, иногда, с пустым множеством, хотя цепочка и множество, совершенно разные понятия. Пустым (или нулевым) называют множество, не содержащее ни одного элемента; его часто обозначают через φ или ф. Чтобы пояснить это различие, сравним пустое множество { } и множество { ε }. Пустое множество, понятно, не содержит элементов, тогда как множество { ε } содержит один элемент, а именно пустую цепочку ε. На рис. 2.8, а изображен автомат с алфавитом {а, b}, распознающий множество { }. Рис. 2.8, б изображает автомат с тем же входным алфавитом, допускающий множество { ε }. Ясно, что эти автоматы различны. Заметим, что ε не является входом автомата, распознающего { ε }.

a b

a b

0 1

S T

S

S

0   S

а

б

Рис. 2.8. (а) Распознаватель множества { };

(б) Распознаватель множества { ε }.

Символ ε используется в описаниях и сам по себе не является входным символом автомата. Если мы говорим «пусть γ = abba», то это не означает, что мы добавим γ к входному алфавиту автомата. Аналогично не надо думать, что ε принадлежит входному множеству только потому, что мы сказали «пусть ε = ».

Другое заблуждение связано с отождествлением пустой цепочки и знака пробела. Однако выражение 1ε0 обозначает цепочку 10, а не 1 0. Поскольку пустая цепочка не содержит ни одного символа, ее длина равна 0. Длина же цепочки, состоящей из одного символа пробела, равна 1.

2.7.  Эквивалентность состояний

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

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

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

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

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

Применительно к конечным распознавателям, назначение которых — допускать цепочки, эквивалентность состояний можно определить так:

Состояние s конечного распознавателя М эквивалентно состоянию t конечного распознавателя N тогда и только тогда, когда автомат М, начав работу в состоянии s, будет допускать в точности те же цепочки, что и автомат N, начавший работу в состоянии t.

Если два состояния s и t одного автомата эквивалентны, то автомат можно упростить, заменив в таблице переходов все вхождения имен этих состояний каким-нибудь новым именем, а затем удалив одну из двух строк, соответствующих s и t. Например, состояния 4 и 5 автомата, изображенного на рис. 2.9, а, явно имеют одинаковые функции, так как оба они являются допускающими,

a b

a b

a b

1 2 3 X X

0 1 0 1 1   1  4 1  5 1  1 1  3 2 3

0 1 0 1 1   1  X 1  X X 1 1  3 2 3

0 1 0 1   1 2 3 X   1  X 1  X X 1 2 3

1 2 3 4 5

а б в

Рис. 2.9.

оба переходят в состояние 2 при чтении входного символа а и оба переходят в состояние 3 при чтении b. Поэтому мы объединяем состояния 4 и 5 в одно состояние, для которого выбираем имя X. Заменяя в таблице состояний каждое вхождение имен 4 и 5 именем X, мы получаем тем самым таблицу, изображенную на рис. 2.9, б. Две ее строки помечены X; удалив одну из них, получаем упрощенную таблицу состояний на рис. 2.9, в.

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

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

Автоматы М и N эквивалентны тогда и только тогда, когда эквивалентны их начальные состояния.

Если два состояния не эквивалентны, то любая цепочка, под действием которой одно из них переходит в допускающее состояние, а другое — в отвергающее состояние, называется цепочкой, различающей эти два состояния. Состояния а и х на рис. 2.10 не эквивалентны, так как их различает цепочка 101. Символически

a 1 c 0 b 1 c

x 1 y 0 z 1 z

причем состояние с — допускающее, а состояние z — нет. Поскольку а и х — начальные состояния соответствующих автоматов,

0 1

0 1

0 1 0

0 0 1

x y z

a b c

a c b c b a

x y z x x z

Рис. 2.10.

мы показали также, что автоматы, изображенные на рис. 2.10, не эквивалентны. Мы видим, что

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

Заметим, что понятие эквивалентности состояний является отношением эквивалентности в математическом смысле; это отношение рефлексивно (каждое состояние эквивалентно себе), симметрично (из того, что s эквивалентно t, следует, что t эквивалентно s) и транзитивно (если s эквивалентно t, a t эквивалентно и, то s эквивалентно и).

2.8.  Проверка эквивалентности двух состояний

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