Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 45 стр.

UptoLike

Составители: 

5.7. Автоматы Мили и Мура
Автоматы Мили и Мура являются неинициальными автоматами. В отображении S(x) =
g(q
0
, x) зафиксируем начальное состояние q
0,
в котором автомат находится в начальный
момент времени. Оно существенно влияет на процесс конечного преобразования, т.к.
определяет не только результирующую цепочку, но и множество входных цепочек.
Рассмотрим поведение инициальных автоматов, которые могут начинать работать из
любого указанного состояния. Такой автомат получает на вход одну цепочку бесконечной
длины и перерабатывает её. Реакция такого преобразователя на определенные воздействия
непредсказуема, если неизвестно его начальное состояние. Поэтому необходимо решить две
задачи, имеющие важное практическое значение:
1) определение того состояния автомата, в котором он находится в момент, начиная с
которого исследуется его поведение;
2) распознавание конечного состояния, в которое перешел автомат после завершения
испытательной операции. Это состояние будет начальным для следующей серии испытаний.
Эти задачи анализа получили название экспериментов по распознаванию состояния.
5.7.1. Автомат Мили
Автомат Мили - это пятерка вида M = (К, X, Y, f, g), где:
K - множество состояний автомата;
X - входной алфавит;
Y - выходной алфавит;
f - функция переходов (отображение K X K);
g - функция выходов (отображение K X Y).
Как и любой другой автомат, автомат Мили можно представить в виде таблицы
или графа. В графе переходов автомата Мили на дугах указываются через символ ‘/’
входные и выходные символы. Таблица переходов состоит из двух частей: в левой части
записываются значения функции выходов, в правой части - значения функции переходов.
Пример. Построим преобразователь, который распознает арифметические
выражения, порождаемые грамматикой:
S a+S | aS | +S | S | a
и устраняет из этих выражений избыточные унарные операции. Например, выражение
a+а+а он переведет ваа+а. Во входном языке символ а представляет идентификатор
и перед идентификатором допускается произвольная последовательность знаков унарных
операции + и . Заметим, что входной язык является регулярным множеством.
Пусть M = (К, X, Y, f, g), где
1. К = {q
0
, q
1
, q
2
, q
3
, q
4
},
2. X = {a,+, },
3. Y = X.