Поделиться Поделиться

Эквивалентность автоматов. Минимизация

Рассмотрим два автомата:

Эквивалентность автоматов. Минимизация - Инвестирование -  1 ,

Эквивалентность автоматов. Минимизация - Инвестирование -  2 .

Состояния Эквивалентность автоматов. Минимизация - Инвестирование -  3 из множества Эквивалентность автоматов. Минимизация - Инвестирование -  4 автомата Эквивалентность автоматов. Минимизация - Инвестирование -  5 и соответственно Эквивалентность автоматов. Минимизация - Инвестирование -  6 из множества Эквивалентность автоматов. Минимизация - Инвестирование -  7 автомата В называются неразличимыми, если Эквивалентность автоматов. Минимизация - Инвестирование -  8 .

Автоматы Эквивалентность автоматов. Минимизация - Инвестирование -  5 и Эквивалентность автоматов. Минимизация - Инвестирование -  10 называются неразличимыми, если для любого состояния Эквивалентность автоматов. Минимизация - Инвестирование -  11 существует состояние Эквивалентность автоматов. Минимизация - Инвестирование -  12 , такое, что Эквивалентность автоматов. Минимизация - Инвестирование -  13 , и наоборот, Эквивалентность автоматов. Минимизация - Инвестирование -  14 .

Рассмотрим изменения состояний и выходов автомата с изменением времени. На каждом такте подается входной сигнал (символ), преобразуется внутреннее состояние, возникает сигнал выхода. Рассмотрим следующий такт. Действия аналогичны:

Эквивалентность автоматов. Минимизация - Инвестирование -  15 , Эквивалентность автоматов. Минимизация - Инвестирование -  16 .

Итак, автомат преобразует слова (как и машина Тьюринга, частным случаем которой является конечный автомат).

Рассмотрим состояние Эквивалентность автоматов. Минимизация - Инвестирование -  17 автомата Эквивалентность автоматов. Минимизация - Инвестирование -  5 . Состояние Эквивалентность автоматов. Минимизация - Инвестирование -  19 называется достижимым из состояния Эквивалентность автоматов. Минимизация - Инвестирование -  3 , если существует такое слово Эквивалентность автоматов. Минимизация - Инвестирование -  21 , что Эквивалентность автоматов. Минимизация - Инвестирование -  22 . Достижимые состояния образуют класс достижимых состояний (рис. 4.4).

Эквивалентность автоматов. Минимизация - Инвестирование -  23 Эквивалентность автоматов. Минимизация - Инвестирование -  24

а б

Рис. 4.4. Достижимое состояние (а) и класс достижимых состояний (б)

Рассмотрим два автомата Эквивалентность автоматов. Минимизация - Инвестирование -  25 , Эквивалентность автоматов. Минимизация - Инвестирование -  26 и состояния Эквивалентность автоматов. Минимизация - Инвестирование -  27 . Автоматы называются эквивалентными, если Эквивалентность автоматов. Минимизация - Инвестирование -  28

Иными словами, автоматы называются эквивалентными, если для каждого состояния Эквивалентность автоматов. Минимизация - Инвестирование -  29 существует эквивалентное ему состояние автомата Эквивалентность автоматов. Минимизация - Инвестирование -  30 . Эквивалентные автоматы обладают одинаковым внешним поведением, т.е. на одинаковые входные слова выдают одинаковые внешние слова. Автоматы могут различаться сложностью внутренней структуры, например, мощностью множеств Эквивалентность автоматов. Минимизация - Инвестирование -  31 и Эквивалентность автоматов. Минимизация - Инвестирование -  32 . Среди всех эквивалентных автоматов имеется минимальный. Одной из основных задач является следующая: найти автомат, эквивалентный данному, но обладающий наименьшим количеством внутренних состояний. Такие задачи решаются последовательно путем выявления одного неразличимого состояния, двух неразличимых состояний,…, Эквивалентность автоматов. Минимизация - Инвестирование -  33 неразличимых состояний, которые объединяются в классы Эквивалентность автоматов. Минимизация - Инвестирование -  34 неразличимых состояний.

Пример:

Автомат Состояния Классы состояний
A Эквивалентность автоматов. Минимизация - Инвестирование -  35 1,5,8
6/1 6/2 1/2 5/2 6/1 6/2 8/2 6/1 6/2 Эквивалентность автоматов. Минимизация - Инвестирование -  36 2,9
3/1 7/1 3/2 3/2 7/1 7/2 7/2 4/1 4/1 Эквивалентность автоматов. Минимизация - Инвестирование -  37 3,4,6,7
6/2 3/2 9/1 2/1 6/2 6/1 2/1 6/2 4/2 Эквивалентность автоматов. Минимизация - Инвестирование -  38

На начальном этапе отыскиваем классы Эквивалентность автоматов. Минимизация - Инвестирование -  33 -эквивалентных неразличимых состояний (при Эквивалентность автоматов. Минимизация - Инвестирование -  40 ):

  A Эквивалентность автоматов. Минимизация - Инвестирование -  35 Эквивалентность автоматов. Минимизация - Инвестирование -  36 Эквивалентность автоматов. Минимизация - Инвестирование -  37 Классы
Эквивалентность автоматов. Минимизация - Инвестирование -  35 1,5,8
6/1 6/1 6/1 6/2 6/2 ½ 5/2 6/2 8/2 Эквивалентность автоматов. Минимизация - Инвестирование -  36 2,9
3/1 7/1 4/1 7/1 4/1 3/2 3/2 7/2 7/2 Эквивалентность автоматов. Минимизация - Инвестирование -  37 3,4,7
6/2 6/2 6/2 3/2 4/2 9/1 2/1 6/1 2/1 Эквивалентность автоматов. Минимизация - Инвестирование -  38

Приходим к автомату, внутренние состояния которого отождествляются с найденными классами эквивалентных состояний:

Эквивалентность автоматов. Минимизация - Инвестирование -  48
3/1 3/2 1/2 4/2
3/1 3/1 3/2 3/2
3/1 3/2 2/1 4/1

У полученного и исходного автоматов внешнее поведение одинаково.

Контрольное задание

Воспользовавшись данными, приведенными в табл. 4.2, выполнить следующее:

а) построить граф для каждого из заданных автоматов (рекомендуется использовать VISIO);

б) минимизировать автоматы, построить графы, проверить правильность минимизаций на словах длиной 20;

в) установить, эквивалентны ли заданные автоматы, проверить на слове длиной 20.

Таблица 4.2

Варианты задания

Номер варианта   А                     В              
8/1 8/2 8/1 5/2 8/1 3/2 1/2 8/2 8/2 4/2 7/2 4/2 2/1 4/2 4/2 3/1
7/1 6/1 4/1 7/2 6/1 6/2 7/2 6/2 4/1 1/1 2/1 6/1 5/2 6/1 3/1 2/2
8/2 7/2 8/2 2/1 8/2 2/1 9/1 8/1 4/2 7/1 1/1 1/1 1/2 1/1 1/1 1/2

Окончание табл. 4.2

Номер варианта   А                     В              
3/1 3/2 3/2 5/2 3/1 1/2 8/2 3/1 3/2 6/2 7/2 6/2 6/2 7/2 7/1 7/2
6/1 7/1 7/2 6/2 7/1 6/2 7/2 4/1 4/1 1/2 1/1 4/2 3/2 3/1 3/1 1/2
3/2 6/2 3/1 2/1 3/2 9/1 2/1 3/2 4/2 5/1 4/2 2/1 2/1 1/2 7/2 7/1
3/2 8/1 7/1 2/2 3/2 3/2 3/2 2/2 8/1 7/2 6/2 7/2 7/2 6/2 6/2 6/1
4/1 7/2 7/2 1/1 5/1 1/1 7/1 8/1 8/2 1/2 1/1 4/2 3/2 4/1 1/2 4/1
9/1 1/2 6/2 3/1 9/1 2/1 1/1 4/1 6/2 5/1 3/2 2/1 2/1 1/2 6/1 6/2
3/1 3/2 3/2 5/2 3/1 1/2 8/2 3/1 3/2 7/2 6/2 7/2 7/2 6/2 6/2 6/1
6/1 7/1 7/2 6/2 7/1 6/2 7/2 4/1 4/1 1/2 1/1 4/2 3/2 4/1 1/2 4/1
3/2 6/2 3/1 2/1 3/2 9/1 2/1 3/2 4/2 5/1 3/2 2/1 2/1 1/2 6/1 6/2
6/1 6/2 1/2 5/2 6/1 6/2 8/2 6/1 6/2 6/2 6/2 4/2 6/1 4/2 6/2 4/2
3/1 7/1 3/2 3/2 7/1 7/2 7/2 4/1 4/1 7/1 5/1 7/2 7/1 5/2 5/2 3/2
6/2 6/2 9/1 2/1 6/2 6/1 2/1 6/2 4/2 5/2 3/2 2/1 6/2 1/1 6/1 2/1
3/2 7/1 8/1 2/2 9/2 3/2 3/3 3/2 7/1 7/2 4/2 4/2 1/1 4/2 4/2 3/1
4/1 8/2 8/2 1/1 5/1 1/1 7/1 8/1 7/2 1/1 2/1 6/1 5/2 6/1 3/1 1/2
9/1 1/2 6/2 3/1 9/1 2/1 4/1 1/1 6/2 2/1 7/1 2/1 2/2 2/1 2/1 2/2
3/1 3/2 3/2 5/2 3/1 8/2 1/2 3/1 3/2 7/2 2/2 7/2 7/2 2/2 2/2 2/1
7/1 6/1 6/2 7/2 6/1 6/2 7/2 4/1 4/1 1/2 1/2 4/2 3/2 3/1 1/1 3/1
3/2 7/2 3/1 2/1 3/2 2/1 9/1 3/2 4/2 5/1 2/1 6/1 6/1 1/2 4/2 2/2
8/2 3/1 2/2 2/2 8/2 8/2 9/2 5/1 3/1 7/2 4/2 4/2 1/1 4/2 4/2 3/1
4/1 5/2 3/1 1/1 5/1 1/1 7/1 5/2 3/2 1/1 2/1 6/1 5/2 6/1 3/1 1/2
9/1 1/2 4/1 8/1 1/1 2/1 9/1 6/2 6/2 2/1 7/1 2/1 2/2 2/1 2/1 2/2
1/2 1/2 1/1 5/2 1/1 8/2 3/2 1/1 1/2 5/2 2/2 5/2 5/2 2/1 2/2 2/2
6/2 6/1 7/1 7/2 6/1 6/2 7/2 4/1 4/1 1/2 1/2 4/2 3/2 4/1 1/1 4/1
1/1 7/2 1/2 2/1 1/2 2/1 9/1 1/2 4/2 7/1 2/1 6/1 6/1 2/2 3/2 1/2
6/2 4/2 5/2 4/2 4/1 4/1 8/2 4/1 4/2 5/2 6/2 5/2 5/2 6/1 6/2 6/2
1/2 7/1 1/2 7/2 7/1 1/1 7/2 3/1 3/1 3/2 4/1 1/2 4/2 1/1 4/2 1/1
9/1 1/2 2/1 4/1 4/2 4/2 2/1 4/2 3/2 2/1 3/2 2/1 7/1 6/2 6/1 4/2

Автоматы Мили и Мура. Размеченные графы

Рассмотренные ранее автоматы – это классические автоматы Мили. Автомат Мура – это автомат, выходы которого зависят только от текущего состояния:

Эквивалентность автоматов. Минимизация - Инвестирование -  49 ,

где Эквивалентность автоматов. Минимизация - Инвестирование -  50 Эквивалентность автоматов. Минимизация - Инвестирование -  51 Эквивалентность автоматов. Минимизация - Инвестирование -  52 алфавит входных сигналов; Эквивалентность автоматов. Минимизация - Инвестирование -  53 Эквивалентность автоматов. Минимизация - Инвестирование -  51 Эквивалентность автоматов. Минимизация - Инвестирование -  55 алфавит выходных сигналов; Эквивалентность автоматов. Минимизация - Инвестирование -  56 , Эквивалентность автоматов. Минимизация - Инвестирование -  57 , Эквивалентность автоматов. Минимизация - Инвестирование -  58 .

Автомат Мура – частный случай автомата Мили.

Оказывается, для каждого автомата Мили существует эквивалентный ему автомат Мура. Для доказательства каждое из состояний расщепляется на несколько состояний, для каждого из которых выход зависит только от состояния, но не от входа.

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

  Эквивалентность автоматов. Минимизация - Инвестирование -  59 Эквивалентность автоматов. Минимизация - Инвестирование -  60 Эквивалентность автоматов. Минимизация - Инвестирование -  61 Эквивалентность автоматов. Минимизация - Инвестирование -  61
Эквивалентность автоматов. Минимизация - Инвестирование -  63 Эквивалентность автоматов. Минимизация - Инвестирование -  64 Эквивалентность автоматов. Минимизация - Инвестирование -  65 Эквивалентность автоматов. Минимизация - Инвестирование -  66 Эквивалентность автоматов. Минимизация - Инвестирование -  67
Эквивалентность автоматов. Минимизация - Инвестирование -  68 Эквивалентность автоматов. Минимизация - Инвестирование -  64 Эквивалентность автоматов. Минимизация - Инвестирование -  65 Эквивалентность автоматов. Минимизация - Инвестирование -  67 Эквивалентность автоматов. Минимизация - Инвестирование -  66
Эквивалентность автоматов. Минимизация - Инвестирование -  73 Эквивалентность автоматов. Минимизация - Инвестирование -  66 Эквивалентность автоматов. Минимизация - Инвестирование -  65 Эквивалентность автоматов. Минимизация - Инвестирование -  67 Эквивалентность автоматов. Минимизация - Инвестирование -  66
Эквивалентность автоматов. Минимизация - Инвестирование -  78 Эквивалентность автоматов. Минимизация - Инвестирование -  65 Эквивалентность автоматов. Минимизация - Инвестирование -  64 Эквивалентность автоматов. Минимизация - Инвестирование -  64 Эквивалентность автоматов. Минимизация - Инвестирование -  65

Несколько изменяется представление графа. Обозначение выхода ставится возле каждого узла (рис. 4.5).

Эквивалентность автоматов. Минимизация - Инвестирование -  83

Рис. 4.5. Графическое представление автомата Мура

Автоматные языки

Общая теория конечных автоматов сводится к анализу и синтезу автоматов. Анализ: по Эквивалентность автоматов. Минимизация - Инвестирование -  63 и Эквивалентность автоматов. Минимизация - Инвестирование -  85 изучить особенности внешнего поведения автомата. Синтез: по внешнему поведению построить функции Эквивалентность автоматов. Минимизация - Инвестирование -  63 и Эквивалентность автоматов. Минимизация - Инвестирование -  85 . Вторая задача значительно сложнее первой.

Частные случаи практически важных КА (конечных автоматов):

– сумматор;

– задержка Эквивалентность автоматов. Минимизация - Инвестирование -  88 (автомат задержки – это автомат Мура);

– счетчик.

Автоматы подразделяются на преобразователи и распознаватели. Иногда вместо распознавателя употребляется термин «акцептор». Все предыдущие автоматы являлись преобразователями. В настоящее время одно из основных применений автомата – установление факта принадлежности подстроки данной строке.

Рассмотрим задачу: установить наличие в заданной строке слова «резец». Синтез соответствующего автомата начинается с построения графа (рис. 4.6).

Эквивалентность автоматов. Минимизация - Инвестирование -  89

Рис. 4.6. Граф распознавания заданного слова

По графу строим таблицу, описывающую работу автомата-распознавателя:

  Эквивалентность автоматов. Минимизация - Инвестирование -  90 Эквивалентность автоматов. Минимизация - Инвестирование -  91 Эквивалентность автоматов. Минимизация - Инвестирование -  65 Эквивалентность автоматов. Минимизация - Инвестирование -  66 Эквивалентность автоматов. Минимизация - Инвестирование -  94
р Эквивалентность автоматов. Минимизация - Инвестирование -  91 /0 н/0 н/0 н/0 н/0
е н/0 Эквивалентность автоматов. Минимизация - Инвестирование -  65 /0 н/0 Эквивалентность автоматов. Минимизация - Инвестирование -  94 /0 н/0
з н/0 н/0 Эквивалентность автоматов. Минимизация - Инвестирование -  66 /0 н/0 н/0
ц н/0 н/0 н/0 н/0 н/1
S н/0 н/0 н/0 н/0 н/0

Далее подаем некоторую строку. Подстрока считается выявленной, если на выходе появляется единица:

а с б л к р р е з а р е з е ц у -
- - - - - - - - - - - - - - - - - -

Полученные таблицы для реализации функции Эквивалентность автоматов. Минимизация - Инвестирование -  63 допускают сжатие путем составления массива номеров строк и столбцов, отличных от н/0. Количество операций имеет порядок длины слова при автоматном распознавании.

В качестве задания осуществить проверку наличия какого-нибудь слова (или предложения) в произвольно выбранном тексте. Например, рассмотреть исходный текст некоторой программы на алгоритмическом языке PASCAL и проверить наличие выражения «for I := » в этом тексте.

Основной технический аппарат при изучении автоматных языков – акцепторы, автоматы-распознаватели. Распознаватели осуществляют выделение всех входных предложений, принадлежащих языку. Автоматные языки – очень узкий класс всех возможных языков.

Словарь – это конечное множество.

Элементы словаря – символы (буквы).

Предложение – все конечные последовательности символов из заданного словаря.

Эквивалентность автоматов. Минимизация - Инвестирование -  100 – множество всех цепочек, построенных по данному словарю.

Множество Эквивалентность автоматов. Минимизация - Инвестирование -  100 содержит бесконечное количество элементов.

Грамматика – конечный механизм задания языка.

Существует два вида грамматик – порождающая и распознающая: первая – это механизм, позволяющий строить все допустимые предложения, вторая – отсеивает из множества Эквивалентность автоматов. Минимизация - Инвестирование -  100 те предложения, которые не принадлежат языку.

Синтаксис – правила построения языка.

Возможности автоматов

Конечные автоматы позволяют избежать использования в программах, реализующих алгоритмы, условного оператора «if», а также операторов выбора (например, «case»). Поэтому «автоматный» стиль программирования предпочтителен при построении сложных программ. Рассмотрим несколько примеров, демонстрирующих преимущества использования автоматов в процессе решения некоторых задач.

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

 
1/0 2/1 3/2 4/3 5/4 6/5 0/6

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

 
0/- 0/- 0/- 0/- 0/- 0/-
1/0 2/1 3/2 4/3 5/4 0/5

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

Счетчик является примером так называемых автономных автоматов, входной алфавит которых содержит единственный символ. Если считать, что в каждой вершине графа имеется один выход, причем выходной сигнал совпадает с номером состояния, то он является эквивалентом отношения порядка, а граф автономного автомата – это простой ориентированный граф [2, 3]. Для входного слова достаточной длины выходное слово автономного автомата содержит периодически повторяющееся подслово.

Проверка четности. Пусть входной алфавит содержит два символа – ноль и единицу. Требуется построить алгоритм, согласно которому на выходе повторяется входное слово, но после каждого подслова, содержащего три символа, должен быть вставлен символ «0», если количество единиц в подслове четно, и символ «1» в противном случае.

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

Это требование удовлетворяется введением такого выходного алфавита: Эквивалентность автоматов. Минимизация - Инвестирование -  104 . Выход после третьего символа состоит из двойки символов: «00», «01», «10», «11». Обозначим состояния автомата как «-», «0», «1», «00», «01», «10», «11», подразумевая под «-» стартовое состояние. После этого оказывается возможным построение автомата проверки четности в следующем виде:

  -
0/0 00/0 10/0 -/00 -/01 -/01 -/00
1/1 01/1 11/1 -/11 -/10 -/10 -/11

Выполним кодирование состояний и выходов, сопоставляя состояние «-» и номер 0, «0» – номер 1, «1» – 2, «00» – 3, «01» – 4, «10» – 5, «11» – 6; выход «0» и номер элемента алфавита 0, выход «1» и номер 1, «00» – 2, «01» – 3, «10» – 4, «11» – 5. Тогда таблица построенного автомата примет такой вид:

 
1/0 3/0 5/0 0/2 0/3 0/3 0/2
2/1 4/1 6/1 0/5 0/4 0/4 0/5

Граф этого автомата изображен на рис. 4.7.

Отметим, что состояния 3 и 6 эквивалентны. Это же относится и к паре состояний 4 и 5. Поэтому в данном случае имеется возможность минимизировать найденный автомат, объединив состояния 3, 6 в класс 3 эквивалентных состояний, а классы 4, 5 – в класс 4. Минимизированный автомат, эквивалентный исходному, в таком случае можно изобразить графически (рис. 4.8) и в виде таблицы:

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

Если поставлена задача проверить четность в словах длиной n, то граф неминимизированного автомата будет содержать Эквивалентность автоматов. Минимизация - Инвестирование -  105 вершин, а минимизированного – Эквивалентность автоматов. Минимизация - Инвестирование -  106 .

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

Эквивалентность автоматов. Минимизация - Инвестирование -  107

Рис. 4.7. Граф автомата проверки четности

Эквивалентность автоматов. Минимизация - Инвестирование -  108

Рис. 4.8. Минимизированный автомат проверки четности

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

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

Учитывая, что слагаемые можно переставлять, кодировщик представим в виде матрицы X:

Эквивалентность автоматов. Минимизация - Инвестирование -  50
0 (0+0) 1 (0+1) 2 (0+2)
1 (1+0) 2 (1+1) 3 (1+2)
2 (2+0) 3 (2+1) 4 (2+2)

Например, пара цифр (1,2) кодируется как элемент X[1,2] = 3, как и пара цифр (2,1). Автомат суммирования может быть задан в виде матрицы Эквивалентность автоматов. Минимизация - Инвестирование -  5 :

Эквивалентность автоматов. Минимизация - Инвестирование -  5
0/0 (0+0 = 0·3 + 0) 0/1 (0+1= 0·3 + 1)
0/1 (1+0 = 0·3 + 1) 0/2 (1+1= 0·3 + 2)
0/2 (2+0 = 0·3 + 2) 1/0 (2+1= 1·3 + 0)
1/0 (3+0 = 1·3 + 0) 1/1 (3+1= 1·3 + 1)
1/1 (4+0 = 1·3 + 1) 1/2 (4+1= 1·3 + 2)

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

Эквивалентность автоматов. Минимизация - Инвестирование -  112

Рис. 4.9. Автоматное суммирование

Достоинством автоматного суммирования является то, что все действия ограничиваются нахождением элементов матриц X и А.

Автоматное декодирование. Рассмотрим основную идею на примере. Пусть задана таблица кодов, получаемых как пути в дереве (рис. 4.10). С движением от узла влево сопоставим символ «а», прямо – «б», вправо – «в». Таблица кодов имеет следующий вид:

Р а Т ва Л бба
К ба Ы ббб С вб
О бв У вв М ббв

В качестве номеров состояний автомата примем номера узлов, не являющихся листами; корень дерева имеет номер 0.

Эквивалентность автоматов. Минимизация - Инвестирование -  113

Рис. 4.10. Дерево кодирования

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

 
а 0/Р 0/К 0/Т 0/Л
б 1/- 3/- 0/С 0/Ы
в 2/- 0/О 0/У 0/М

Для проверки работоспособности построенного автомата предлагается самостоятельно получить выходное слово, если на вход подается слово «бабвабвббвбббвбббабв». Входное слово следует подавать в порядке слева направо (первый входной символ – б, второй – а, третий – б и т.д.).

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

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

Краткий перечень задач, для которых отсутствует алгоритм решения, таков [1]:

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

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

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

4. Проблема тотальности. По произвольному заданному алгоритму определить, будет ли он завершаться во всех возможных наборах.

← Предыдущая страница | Следующая страница →