Автоматы Милли и Мура. Распознавание множеств автоматами

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

.

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

Несмотря на то, что автомат Милли – частный случай автомата Мура, возможности этих двух автоматов совпадают.

Теорема. Для любого автомата Милли существует эквивалентный ему автомат Мура.

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

Разобьем состояния автомата Мура на два класса: класс – выход равен 1, класс – выход равен 0. Это позволяет не рассматривать функцию выходов и определить автомат-распознаватель как систему

.

С каждым таким автоматом свяжем распознаваемый им язык

,

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

Пример. , где , , , , а задается таблицей

Слова, переводящие автомат в состояние 1 – это слова с четным количеством единиц. Поэтому язык .

Теорема анализа. Язык, распознаваемый автоматом, является регулярным.