<<
>>

§3.4. Приведённый автомат

Назовём состояния и автомата неотличимыми, если для всех Состояния и отличимы, если при некотором Положим если и неотличичимы.

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

Множество классов отношения ~ (фактор-множество обозначим через Построим новый автомат В качестве входного и выходного алфавитов автомата возьмём те же множества и которые были у автомата а в качестве множества состояний возьмём множество Надо определить теперь функции и

Пусть Наиболее естественным является следующее определение значения взять какой-нибудь элемент принадлежащий классу найти а затем класс, в котором лежит элемент объявить значением То есть считать, что

(1)

Докажем корректность этого определения, т.е.

независимость от выбора представителя в классе эквивалентности. Пусть Определение будет некорректным, если окажется, что Докажем, что определение корректно. Если то при некотором Это означает, что Следовательно, что противоречит условию. Итак, поэтому определение (1) корректно.

Функцию определим на по формуле

(2)

По определению неотличимости состояний мы имеем поэтому определение (2) корректно.

Автомат называется приведённым автоматом, соответствующим автомату

Докажем, что у приведённого автомата все состояния отличимы друг от друга. Пусть Тогда для всех Отсюда по формуле (2) получаем, что при всех Следовательно, Отсюда следует, что Итак, у автомата неотличимыми являются только совпадающие друг с другом состояния.

Автомат и приведённый автомат работают одинаково: для любой входной последовательности последовательность на выходе автомата и автомата одна и та же: и т.д. (здесь начальное состояние). Решение типовых задач

Пример 1. Построить приведённый автомат для автомата, заданного следующей диаграммой Мура, изображенной на рис. 3.14.

Решение. Вычислим: , , , , . Следовательно, состояние отличимо от всех остальных. Мы получаем (пока) следующее разбиение множества на классы, т.е. непересекающиеся подмножества: (далее это разбиение будет измельчаться).

Далее вычисляем: Отсюда следует, что не может лежать в одном классе с или с или и т.д.

Разбиение, полученное ранее, измельчается до следующего: Положим Покажем, что это окончательное разбиение. Имеем: поэтому Аналогично получаем и т.д., т.е. функция “не разбивает” классы. Следовательно, классы можно считать состояниями нового автомата. Это и есть приведённый автомат, его диаграмма Мура изображена на рисунке 3.15.

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

Решение. Верхняя строка таблицы 11011 определяет разбиение нижняя строка - разбиение Их пересечение это разбиение Докажем, что состояния неотличимы друг от друга.

В столбцах таблицы, соответствующих этим состояниям, мы имеем: значит, функция на состояниях принимает одинаковые значения. Кроме того, другая часть столбцов: такова, что лежат в одном классе разбиения. Это доказывает, что неотличимы. Из таблицы автомата теперь нетрудно получить таблицу приведённого автомата для этого достаточно взять по одному представителю в каждом классе разбиения Таким образом, мы получаем таблицу 3.8:

Задачи для самостоятельного решения

1. Автомат задан диаграммой Мура. Построить диаграмму Мура приведённого автомата

2. Автомат задан таблицей. Построить таблицу приведённого автомата

Ответы

1.

2.

<< | >>
Источник: Дискретная математика. Лекции. 2016

Еще по теме §3.4. Приведённый автомат:

  1. Авторы приведённой типологии корпоративной культуры Бла-зи Дж.
  2. Согласно отчёту НАСА они должны были видеть весь диск Земли
  3. Где же кинофильм о полёте над Луной «от терминатора до терминатора»?
  4. Атлас снимков “Apollo” представляет
  5. Рассказ о посадке А11 Всякая ли местность с большим количеством ям и ямок обязательно находится на Луне?
  6. Указатель слов к разделу «Орфография»
  7. 2.3. Характеристики активных языков
  8. Причины высокой частотности пассива в английском языке
  9. Этимология 500 наиболее высокочастотных существительных русского, немецкого и английского языков
  10. В. Возражения социально психологического порядка
  11. Новые виды и новые проблемы проектирования
  12. УКАЗАТЕЛЬ СЛОВ К РАЗДЕЛУ «ОРФОГРАФИЯ»
  13. ДИМИНУТИВЫ
  14. §3.4. Приведённый автомат
  15. ВВОДНАЯ ЧАСТЬ
  16. §1. Эволюция понятия «базы данных» и его место в системе гражданскоправовых понятий