Р0 =({1, 2, 3, 4}, {5, 6, 7}),
так как 1, 2, 3 и 4 — отвергающие состояния, а 5, 6 и 7 — допускающие состояния. Ни одно из состояний первого блока не эквивалентно ни одному состоянию второго блока, поскольку такие пары состояний нарушают условие подобия (см. разд. 2.8).
Теперь посмотрим, что происходит с состояниями блока {1,2, 3, 4} под действием входного символа а. Состояния 3 и 4 переходят в состояния, принадлежащие первому блоку (а именно в состояния 1 и 4 соответственно), тогда как состояния 1 и 2 переходят в состояния, принадлежащие второму блоку (а именно в состояния 6 и 7 соответственно).
Это означает, что для любого состояния из множества {1, 2} и любого состояния из (3, 4} соответствующие состояния-преемники по входу а будут неэквивалентны. Это нарушает условие преемственности, и потому мы можем заключить, что ни одно состояние из множества {1, 2} не эквивалентно ни одному состоянию из множества {3, 4}. Это позволяет произвести новое разбиение:
Р1 =({1, 2}, {3,4}, {5, 6, 7}),
причем состояния из разных блоков всегда не эквивалентны. Мы говорим, что получили Р1 из Р0, разбивая блок {1, 2, 3, 4} относительно входа а.
Теперь попытаемся найти такой входной символ и такой блок в Р1 чтобы его можно было разбить относительно этого входного символа и получить тем самым новое разбиение. Для этого разбиения также будет выполняться свойство неэквивалентности состояний, принадлежащих разным блокам. Повторяем процесс до того момента, когда дальнейшее разбиение становится невозможным. Так как мы не устанавливаем порядок, в котором входные символы и блоки проверяются на возможность разбиения, последовательность разбиений можно порождать многими способами. Последнее разбиение, однако, будет одним и тем же во всех случаях. В нашем примере после Р1 можно продолжать процесс следующим образом:
|
|
|
|
|
|
1 3 1 3 1 5 1 6 1 3 1 1 4 2 |
{6,7} {3} {1,2} {5} {4} {6,7} {6,7} {3} {4} {1,2} |
|
|
Рис. 2.18.
Разбивая блок {3, 4} из Р1 относительно а, получаем
Р2 = ({1, 2}, {3}, {4}, {5, 6, 7}).
Разбивая {5, 6, 7} из Р2 относительно а или b, получаем
Р3 =({1, 2}, {3}, {4}, {5}, {6, 7}).
Р3 не допускает дальнейшего разбиения. Чтобы убедиться в этом, заметим, что все состояния блока {1, 2} переходят относительно а в состояния блока {6, 7}, а относительно b — в состояния блока {3}. Аналогично блок {6, 7} переходит в блоки {4} и {1, 2} относительно а и b соответственно. Оставшиеся блоки имеют по одному элементу и поэтому автоматически исключают дальнейшее разбиение.
Когда процедура закончена, состояния внутри каждого блока эквивалентны. В нашем примере эквивалентны состояния 1 и 2, 6 и 7. Чтобы понять, почему эти состояния должны быть эквивалентными, можно рассуждать следующим образом. Поскольку дальнейшее разбиение невозможно, входные символы, примененные к состояниям одного блока, переводят их в состояния, которые снова принадлежат одному блоку. Так как это положение справедливо для всех блоков и всех входных символов, оно должно выполняться и тогда, когда входные символы образуют входные цепочки. Вследствие того, что Р0 было разбиением на допускающие и отвергающие состояния, каждый блок любого последующего разбиения содержит либо только допускающие, либо только отвергающие состояния. Таким образом, если для пары состояний существует различающая цепочка, то она переводит их в разные блоки. Отсюда мы заключаем, что состояния, принадлежащие одному блоку в последнем разбиении, не могут иметь различающих цепочек и должны быть эквивалентными.
Блоки последнего разбиения можно использовать для построения нового автомата, который эквивалентен исходному и не содержит эквивалентных состояний. Такой автомат для нашего примера изображен на рис. 2.18, б. Множество состояний нового автомата — это множество блоков последнего разбиения. Переходы нового автомата мы получили из старого, прослеживая переходы из блока в блок для каждого входного символа. Так, на рис. 2.18, б элементом таблицы для состояния {1, 2} и входа а является состояние {6, 7}, потому что состояния блока {1,2} последнего разбиения Р3 переходят в состояния блока {6, 7} при входе а. Начальным состоянием нового автомата будет просто блок, содержащий начальное состояние исходного автомата, а допускающими состояниями будут те блоки, которые содержат допускающие состояния исходного автомата.
Автомат, изображенный на рис. 2.18,б, не имеет недостижимых состояний и является поэтому минимальным для автомата рис. 2.18, а.
В общем случае процедура разбиения должна сопровождаться выбрасыванием недостижимых состояний в целях получения минимального автомата. Не имеет значения, которая из двух процедур выполняется первой.
Теперь попытаемся привести автомат, изображенный на рис. 2.7 и предназначенный для распознавания цепочек, которые могут следовать за словом INTEGER в операторе Фортрана. Прежде всего, замечаем, что автомат не имеет недостижимых состояний. Затем применяем процедуру разбиения. Сначала строим разбиение Р0, разделяя допускающие и отвергающие состояния:
Р0 = ({1, 3, 4, 5, 6, 8, Е}, {2, 7}).
Разбивая {1, 3, 4, 5, 6, 8, Е} относительно входа v получаем
Р0 = ({1, 8}, {3, 4,5, 6, Е}, {2,7}).
Разбивая {3, 4, 5, 6, Е} относительно входа ) получаем
Р0 = ({1, 8}, {3, 5, Е}, {4,6}, {2,7}).
Разбивая {3, 5, E} относительно входа v получаем
Р0 = ({1,8}, {3,5}, {Е}, {4, 6}, {2, 7}).
Разбивая {2, 7} относительно входа ( получаем
Р0 = ({1,8}, {3,5}, {Е}, {4,6}, {2}, {7}).
Никакое дальнейшее разбиение невозможно, поэтому Р4 — последнее разбиение, которое выявляет эквивалентные состояния.
|
2 E E E E E E A B E C C E E E E E B E 7 E E A E E E E E E E |
|
|
Рис. 2.19.
Обозначая символами А, В и С блоки {1, 8}, {3, 5} и {4, 6} соответственно, а символом Е — соответствующий одноэлементный блок, мы получаем на рис. 2.19 таблицу переходов, которая изображает минимальный автомат для автомата рис. 2.7. Таким образом
получен автомат с шестью состояниями, который выполняет ту же работу, что и построенный нами сначала автомат с девятью состояниями.
Вспомнив толкование состояний, данное в разд. 2.5, можно следующим образом интерпретировать полученные классы эквивалентности:
{1, 8} — должен начаться непустой список объектов,
{3, 5} — должна появиться размерность,
{4, 6} — только что задана размерность.
Попрактиковавшись, можно научиться опознавать роли, которые приводят к одной и той же ситуации, и получать тем самым исходные автоматы меньшего объема. Однако, каким бы ни было число включенных в исходный автомат ненужных состояний, с помощью описанного алгоритма его можно привести к минимальному конечному автомату.
2.12. Недетерминированные автоматы
Теперь мы введем принадлежащее теории автоматов понятие недетерминированного автомата. Этот термин может привести в недоумение, так как в русском и других языках понятие автомата, в сущности, не позволяет применять к нему прилагательное «недетерминированный». Поэтому в первую очередь надо иметь в виду, что недетерминированный автомат неудобно интерпретировать как модель поведения некоторого физического устройства. Еще одним поводом для недоразумений является то, что термин «недетерминированный» наводит на мысль о чем-то случайном, однако в недетерминированном автомате ничего случайного нет. Таким образом, второе, что нужно иметь в виду,— это то, что никакие вероятности здесь ни при чем.
Недетерминированный автомат — это просто формализм для определения множеств цепочек. Слово «автомат» присутствует в его названии потому, что этот формализм является обобщением формализма, используемого для определения обычного детерминированного автомата. Недетерминированные конечные распознаватели важны, поскольку:
1) для заданного множества иногда легче найти недетерминированное описание;
2) существует процедура для превращения произвольного недетерминированного конечного распознавателя в обычный конечный распознаватель.
Недетерминированный конечный распознаватель представляет собой обычный распознаватель с той разницей, что значениями его функции переходов являются множества состояний, а не отдельные состояния, и вместо одного начального состояния задается множество начальных состояний. Таким образом, можно дать следующее определение:
Недетерминированный конечный распознаватель задается:
1) конечным множеством входных символов,
2) конечным множеством состояний,
3) функцией переходов δ, которая каждой паре, состоящей из состояния и входного символа, ставит в соответствие множество новых состояний,
4) подмножеством состояний, выделенных в качестве начальных,
5) подмножеством состояний, выделенных в качестве допускающих.
Если состояние sнов принадлежит множеству новых состояний, приписанному функцией переходов «текущему» состоянию sтек и входному символу х, то мы пишем
sтек X sнов
Этим обозначением можно, конечно, пользоваться и в том случае, когда мы предпочитаем не интерпретировать его как переход некоторого реального автомата. Говорят, что автомат допускает входную цепочку, если она позволяет связать одно из его начальных состояний с одним из допускающих. Так, если для некоторого автомата справедливо
s0 X1 s1 X2 s2 X3 s3
где s0 — начальное, a s3 — допускающее состояние, то мы будем говорить, что входная цепочка x1x2x3 допускается этим автоматом. Перефразировав последний абзац несколько более формально, мы получаем следующее определение:
Входная цепочка длины n допускается недетерминированным конечным распознавателем тогда и только тогда, когда можно найти последовательность состояний s0 … sn, такую, что s0 — начальное состояние, sn — допускающее состояние, и для всех i, таких, что 0 < i ≤ n, состояние si принадлежит множеству новых состояний, приписанных функцией переходов состоянию si-1 для i-ro элемента входной цепочки.
Способ представления конечных распознавателей с помощью таблицы переходов легко распространяется и на представление недетерминированных конечных распознавателей. Необходимо сделать лишь два изменения. Во-первых, каждый элемент таблицы должен содержать множество состояний. Мы указываем это множество, просто перечисляя его элементы и не заключая их в скобки. Второе изменение состоит в том, что начальные состояния указываются с помощью стрелок, расположенных перед метками соответствующих строк. Если таких стрелок нет, подразумевается, что есть только одно начальное состояние, а именно состояние, соответствующее первой строке.
|
|
A
|
A, B C B C A, C |
δ (A, 0)={A, В},
δ (В, 0) = {В},
δ (С, 0)={ },
Рис. 2.20. |
δ (A, 1)={С},
δ (В, 1) = {С},
δ (С, 1) = {А, С}.
Цепочка 11 — одна из допускаемых автоматом цепочек, так как
B 1 C 1 C
причем В — начальное состояние, а С — допускающее. Существования одной этой последовательности переходов достаточно для того, чтобы показать допустимость входной цепочки 11, и существование другой последовательности переходов из начального состояния в отвергающее, например
B 1 C 1 A
на это не влияет.
Один из переходов недетерминированного распознавателя, а именно δ (С, 0) является переходом в пустое множество. Это попросту означает, что для состояния С и входа 0 дальнейшие переходы невозможны. Такой элемент таблицы переходов может препятствовать существованию последовательности переходов для некоторой входной цепочки. В данном примере такой цепочкой является 10; так как 1 переводит оба начальных состояния в состояние С, множество преемников которого пусто. Такие входные цепочки просто отвергаются наряду со всеми прочими цепочками, которые не могут перевести начальное состояние в заключительное.
«Работу» недетерминированного автомата можно интерпретировать двояким образом. Покажем это на примере автомата, приведенного на рис. 2.20. Пусть автомат находится в состоянии A, и к нему применяется входная цепочка, начинающаяся с 0. Тогда можно представить себе один из следующих вариантов:
1. Автомат осуществляет выбор, переходя либо в А, либо в В, т. е. В одно из новых состояний, соответствующих старому состоянию А и входу 0. Автомат продолжает работать подобным образом, и при этом возможно много выборов. Если имеется какая-нибудь последовательность выборов, при которой автомат под действием входной цепочки заканчивает работу в допускающем состоянии, то говорят, что эта входная цепочка допускается автоматом. Подчеркнем, что достаточно только одной последовательности выборов, приводящей к допускающему состоянию, и автомат допускает данный вход, даже если имеется много других последовательностей выборов, которые не ведут к допускающему состоянию.
2. Автомат распадается на два автомата, один — в состоянии А, а другой — в состоянии В. При продолжении обработки входа происходит дальнейшее деление каждого автомата в соответствии с возможностями, содержащимися в таблице переходов. Когда вход обработан, цепочка допускается, если один из результирующих автоматов находится в допускающем состоянии.
Эти две интерпретации эквивалентны, и обе полезны для понимания недетерминированного автомата. Однако автомат служит не для моделирования этих ситуаций. Его назначение состоит в определении допустимого множества входных цепочек.
Пример
Построим недетерминированный автомат с входным алфавитом
{А, Л, Н, О, С, Ь}
,который допускает только две цепочки ЛАССО и ЛАНЬ.
Применяя технику пометки символов, находим следующие очевидные роли:
с0 — начальное состояние
Л1 — Л в ЛАССО
a1 — А в ЛАССО
C1 — первое С в ЛАССО
С2 — второе С в ЛАССО
О — О в ЛАССО
Л2 — Л в ЛАНЬ
A2 — А в ЛАНЬ
Н — Н в ЛАНЬ
Ь — Ь в ЛАНЬ
Затем эти роли преобразуются в таблицу переходов, изображенную на рис. 2.21. Недетерминированность проявляется двояким образом. Во-первых, поскольку оба Л — из ЛАССО и из ЛАНЬ — могут встречаться сразу после начального состояния, мы просто помещаем как Л1 так и Л2 в этот элемент таблицы. Во-вторых, во-многих местах встречается буква, которая не может быть правильным продолжением слова, и эти места просто оставляются незаполненными или пустыми как указание на то, что продолжение невозможно.
|
|
Л1, Л2 a1 C1 C2 О a2 Н Ь |
Рис. 2.21.
Это освобождает нас от введения состояния ошибки, что мы делали в разд. 2.5, когда пытались непосредственно по ролям строить детерминированную таблицу.
2.13. Эквивалентность недетерминированных и детерминированных конечных распознавателей
Понятие недетерминированного конечного распознавателя приобретает практическое значение благодаря следующему факту:
Для каждого недетерминированного конечного распознавателя существует детерминированный конечный распознаватель, который допускает в точности те же входные цепочки, что и недетерминированный.
В данном разделе мы покажем, как можно найти этот эквивалентный детерминированный автомат.
Основная идея построения заключается в том, что после обработки отдельной входной цепочки состояние детерминированного автомата будет представлять собой множество всех состояний недетерминированного автомата, которые он может достичь из начальных состояний после применения данной цепочки. Переходы детерминированного автомата можно получить из недетерминированных переходов, вычисляя множество состояний, которые могут следовать после данного множества при различных входных символах. Допустимость цепочки определяется по тому, является ли последнее детерминированное состояние, которого он достиг, множеством недетерминированных состояний, включающим хотя бы одно допускающее состояние. Результирующий детерминированный автомат является конечным, так как существует лишь конечное число подмножеств недетерминированных состояний.
Если недетерминированный автомат имеет n состояний, то эквивалентный детерминированный автомат, который мы только что описали, может, вообще говоря, иметь 2n состояний, по числу подмножеств исходного множества состояний. На практике многие из этих подмножеств представляют собой недостижимые состояния. В приводимой ниже процедуре переходы строятся только для тех подмножеств, которые действительно необходимы.
Процедура задается следующими пятью шагами. Пусть Мн — недетерминированный автомат, а Мд — эквивалентный ему детерминированный автомат, который нужно построить.
1. Пометить первую строку таблицы переходов для Мд множеством начальных состояний автомата Мн. Применить к этому множеству шаг 2.
2. По данному множеству состояний S, помечающему строку таблицы переходов автомата Мд, для которой переходы еще не вычислены, вычислить те состояния Мн, которые могут быть достигнуты из S с помощью каждого входного символа х, и поместить множества последующих состояний в соответствующие ячейки таблицы для Мд. Символически это выражается так. Если δ — функция недетерминированных переходов, то функция детерминированных переходов δ' задается формулой
δ' (S, x)={ s|s принадлежит δ (t, к) для некоторого t из S }
3. Для каждого нового множества, порожденного переходами на шаге 2, посмотреть, имеется ли уже в Мд строка, помеченная этим множеством. Если нет, то создать новую строку и пометить ее этим множеством. Если множество уже использовалось как метка, никаких действий не требуется.
4. Если в таблице автомата Мд есть строка, для которой еще не вычислены переходы, вернуться назад и применить к этой строке шаг 2. Если все переходы вычислены, перейти к шагу 5.
5. Пометить строку как допускающее состояние автомата Мд тогда и только тогда, когда она содержит допускающее состояние недетерминированного автомата. В противном случае пометить как отвергающее состояние.
Проиллюстрируем эту процедуру на примере недетерминированного автомата рис. 2.20. Результат применения шага 1 изображен на рис. 2.22, а. Применяя шаг 2 к {А, В}, обнаруживаем, что
δ' ({А, В}, 0) = {A, В} и δ' ({А, В}, 1) = {С}. См. рис. 2.22, б.
Применяя шаг 3, мы видим, что уже имеется строка для {А, В}, но не для {С}. Поэтому создаем новую строку для {С}, получая тем самым конфигурацию на рис. 2.22, в.
Переходя к шагу 4, обнаруживаем, что надо применить шаг 2 к {С}. После того как это сделано, на шаге 3 выясняется, что нужны еще две строки (рис. 2.22, г). Применение шага 2 к {A, С} и к пустому множеству { } дает нам переходы в множества, которые уже являются именами состояний. Этот результат изображен на рис. 2.22, д.
Теперь шаг 4 предписывает нам перейти к шагу 5. Состояние {А, В} отмечается как допускающее, поскольку оно содержит допускающее состояние В; состояния {С} и {A, С} отмечаются как допускающие, так как содержат допускающее состояние С. Пустое множество, разумеется, не содержит допускающего состояния и поэтому помечается как отвергающее.
Результат приведен на рис. 2.22, е, где изображен окончательный вариант детерминированного автомата, эквивалентного исходному недетерминированному. Чтобы напомнить, что множества на рис. 2.22, е — это просто имена состояний нового автомата, мы подставляем новый набор имен, получая на рис. 2.22, ж таблицу состояний, которая задает тот же самый автомат, но в более простых обозначениях.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
{ } {A, C} |
{ } {A, C} { } { } {A, B} {A, C} |
{А, В} {С}
|
|
{ } { } {A, B} {A, C} |
1
1 4 1 3 1 4 |
Рис. 2.22.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 |
