Автомат Мура

Конечный автомат Мура есть пятерка A= (X, Y, Z, f, h), где X, Y, Z, f - означают то же, что и в определении автомата Мили (

· X – конечное множество входов,

· Y – конечное множество выходов,

· Z – конечное множество состояний,

· f: Z*X® Z – отображение (функция переходов),), а

· h - сюръекция: Z®Y, называемая функцией перехода.

При формальном сравнении определений автоматов Мили и Мура, может показаться, что автоматы Мура м.б. заданы как автоматы Мили, у которых выход не зависит от входа, т.е. как автоматы Мили, выходная функция которых удовлетворяет условию: ("x,x'ÎX') ("zÎZ) [g(z,x)= g(z,x')]. Автоматы Мили с этим свойством будем называть входно-независимыми.

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

У автоматов Миливыход, соответствующий некоторому входу и определенному состоянию, порождается во время перехода автомата в следующее состояние.

У автомата Мурасначала порождается выход, а потом происходит переход в следующее состояние, причем выход определяется только состоянием автомата. В частности, автомат Мура порождает некий выход еще перед тем, как получит первый вход- это выход, соответствующий начальному состоянию автомата.

Вопросы и упражнения

Задайте автоматом Мура процесс сортировки по возрастанию массива: 3, 1, 9, 4, 2.

Связь автоматов Мили и автоматов Мура.

Автомат Мура можно представить как частный случай автомата Мили:

Пусть A – автомат Мура. Положим g(z,x)= h(f(z,x)) "zÎZ и "xÎX Тогда B=(X,Y,Z,f,g) – автомат Мили, который для любых непустых входных последовательностей порождает такие же выходные последовательности, как и автомат А, если, конечно, не учитывать самый первый выход автомата А.

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

Теорема. Любой автомат Мили может быть представлен как автомат Мура и обратно.

Вопросы и упражнения

1. Постройте автомат Мура для упр. 2 п.п. 5.2.

2. Постройте автомат Мили для упр. п.п. 5.3.

Автоматы Робина-Скотта

Пример

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

Пример: Некоторая библиотека имеет следующие "либеральные" правила выдачи литературы:

1. любой абонент может брать выбранные книги домой;

2. не существует точных сроков возврата, т.е. абонент возвращает книгу в библиотеку только тогда, когда этого хочет;

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

Рассмотрим двух студентов А и В, которым для их дипломных работ рекомендованы статьи их двух сборников. Студенты не знают друг друга и работают дома. Статьи они читают до тех пор, пока не поймут их содержание. Для понимания некоторой статьи из одного сборника может оказаться необходимой статья из другого. Студент, столкнувшийся с такой "незамкнутой" статьей, должен, таким образом, сохранить у себя сборник с этой статьей до тех пор, пока у него не окажется второго сборника и он не прочтет нужную ему статью.

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

Каждому студенту сопоставим автомат, который может находиться в 4-х состояниях:

0: Ни один из сборников не получен и не заказан.

1: Получен один из сборников, второй не заказан.

2: Получен один из сборников, второй заказан.

3: Получены оба сборника.

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

Для получения ответа на поставленный вопрос, необходимо рассмотреть различные возможные комбинации состояний "автоматов", соответствующих студентам А и В. С этой целью построим прямое произведение графов состояний, причем на ребрах будем указывать действиям которого из студентов они соответствуют. Отбрасывая невозможные сочетания состояний (например, состояние 3 для А и 2 для В), получаем граф, из которого сразу видно, что может возникнуть тупиковая ситуация (из ситуации 22 для обоих студентов нет выхода).

Граф дает возможность определить последовательность действий, приводящиую из ситуации 00 в ситуацию 22. Множество всех таких последовательностей (конечной длины) бесконечно.