Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 64

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 64)

Остановимся на пих подробнее. 1. Различные доопределения частичного автомата 5 природят, вообще говоря, к неэквивалентным между собой полным автоматам 5ь .. 5л, соответствующие минимальные автоматы 5нь ...,5„0 могут иметь разное число состояний и также пеэквивалентпы между собой; следовательно, их нельзя получить друг из друга эквивалентными -преобразованиями. Например, рассмотрим три доопределения клетки (2, а,) в табл. 8,8: (2,0), (2,1) и (1,1). В первом случае (при очевидном доопределении остальных клеток) получим автомат 5п где состояния 1 и 2 эквивалентны; во втором случае получим автомат 5м где 1 и 2 не эквивалентны, а эквивалентны 2 и 3; минимальные для них автоматы 5м и 5го имеют по два состояния, но могут оказаться неизоморфпыми, если для 5, доопределить б(1, аз) =3.

Наконец, третье 308 доопределение дает неминимизируемый автомат 5з. Поэтому, во-первых, результат минимизации может силыю зависеть от выбранного доопределения, а во-вторых, этот результат является тупиковым — его нельзя улучшить эквивалентными преобразованиями и надо просто пробовать другой вариант доопределения. Число же этих вариантов очень велико: если 1Яа) =и, ~ 1гз) =й, ба не определена в р клетках таблицы, а Лз — в г клетках, то это число равно пРР'. 2, Даже перебор всех доопределеиий может не привести к минимальному для 5 автомату.

Дело в том, что алгоритм Мили в любом случае даст систему непересекающихся классов совместимости — а ведь эти классы могут пересекаться1 Это иллюстрируется простым, но эффектным примером Полла — Ангера, Автомат 5, заданный табл, 8.6, а, можно Таблица Дб а1 а1 1,— 3,0 2,! 2,0 1,0 1,О С1 с с,о с,, с, о С,, О 309 а б доопределить двумя способами: положив Л(1, а1) =О либо Л(1, а,) =1. Можно проверить, что при любом из этих доопределений полученный автомат не имеет эквивалентных состояний и, следовательно, не минимизируется.

Однако для частичного автомата 5 это означает всего лишь, что он не имеет нетривиальной замкнутой системы непересекающихся классов совместимости. В то же время для 5 существует замкнутая система пересекающихся классов: С1=(1, 2), Са=(!, 8), которая по теореме 8.8 приводит к автомату 5' с двумя состояниями (табл. 8.6, б), покрывающему 5. Этот пример говорит о том, что из-за пересечения классов совместимости число различных вариантов минимизации еще больше числа вариантов доопределения частичного автомата.

Таким образом, приходится искать дополнительные методы построения систем классов совместимости. Кратко остановимся на их' существе. Всякий класс содержит попарно совместимые состояния, поэтому первая задача заключает- ся в нахождении всех совместимых пар состояний, Решение этой задачи основано на том, что пара состояний д и д' несовместима, если либо А(д, а~) чьХ(д', а;), либо пара 6(д, а;) и 6(д', а,) несовместима для некоторых аь иь Это дает простой индуктивный процесс (в некотором смысле дополнительный к алгоритму Мили); на 1-и шаге несовместимыми объявляются все пары д, д', для которых Х(Ч, а ) 4=1(д', а;); на (г+1)-м шаге несовместимыми объявляются все пары и, о', для которых 6(д, а1) и 6(д', а;) уже были определены как несовместимые на предыдущих шагах.

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

Нетрудно, понять, что система всех максимальных классов является полной и замкнутой (для любой совместимой пары у, Ч' 6(9, а) и 6(д', а) также совместимы и, следовательно, лежат по крайней мере в одном максимальном классе), поэтому ей соответствует автомат 5', покрывающий исходный автомат 5, Однако в общем случае он может иметь даже больше состояний, чем 5. (В качестве упражнения предложим читателю построить частичный автомат с пятью состояниями, в котором максимальными классами совместимых состояний будут шесть пар: 12, 23, 34, 43, 14, 23, а остальные четыре пары несовместимы.) Поэтому можно пытаться удалить некоторые классы из этой системы, однако при этом нужно проверять, пе нарушаются ли полнота и замкнутость.

В общем же случае классы минимальной полной и замкнутой системы (С„..„С ) пе обязаны быть максимальными. Различные методы минимизации частичных автоматов, эвристические приемы обхода указанных трудностей перебора и обсуждение случаев, когда эти трудности не столь велики, можно найти в книгах Р. Миллера (14) и А. Д. Закревского (13). Интерпретация автоматов. Основные проблемы абстрактной теории автоматов. Известно, что конечный автомат представляет собой хотя и абстрактную, но с функциональной точки зрения довольно точную модель дискретного (цифрового) вычислительного или управляющего устройства.

Входная буква — это входной сигнал (точнее, комбинация сигналов на всех входах устройства), входное слово— последовательность входных сигналов, поступающих в автомат в дискретные моменты времени (такты) 1=1, 2, 3...; выходное слово — последовательность выходных сигналов, выдаваемых автоматом; состояния автомата — это комбинации состояний запоминающих элементов устройства. Такая интерпретация, безусловно, верна, и именно она довольно долго служила основным стимулом развития и источником задач теории автоматов.

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

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

При подходе к теории автоматов как к части теории алгоритмов центральной проблемой является изучение возможностей автоматов в терминах множеств слов, с которыми работают автоматы. Можно выделить два основных аспекта «работы» автоматов: 1) автоматы распознают входные слова, т. е. отвечают на вопрос, принадлежит ли поданное на вход слово данному множеству (это автоматы-распознаватели); 2) автоматы преобразуют входные слова в выходные, т. е. реализуют автоматные отображения (автоматы-преобразователи). Один аспект можно свести к другому: последовательность ответов распознавателя на входные слова ап, ап ап, аьапаь ... образует выходное слово, которое является автоматным отображением; с другой стороны, все выходные буквы преобразователя можно разбить на два класса С, и С~ и считать, что автомат распознает множество тех слов а, для которых Х(дь а)~С, (и, следовательно, дополнение к этому множеству).

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

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

Характеристики

Список файлов книги