Взаимные преобразования автоматов

 

Одной из основных задач, решаемых в теории автоматов, является задача эквивалентного преобразования автомата Мили в автомат Мура либо наоборот [4].

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

Преобразование автоматов связано с преобразованием их состоя-ний. На рис. 4.3 представлены преобразования для обоих случаев преобразования автоматов. Видно, что в случае а символы выхода на графе автомата Мура приписываются дуге на графе автомата Мили; в случае б в вершину s_m автомата Мура нельзя поместить несколько сим-волов выхода с дуг автомата Мили, поэтому такое состояние надо "расщеплять":

S_m=(S'_m, S"_m), где S'_m=(s_m, y_n) S"_m=(s_m, y_p).

Аналогично поступают и при преобразованиях на таблицах.

 

а)

 

б)

 

Рис. 4.3. Преобразования автоматов (их состояний):

а) автомата Мура в автомат Мили; б) автомата Мили в автомат Мура

 

Пример 4.3. Рассмотрим преобразование автомата Мили А_А, заданного табл. 4.3 (графом на рис. 4.1) и алфавитами: , , , в автомат Мура А_В. Для автомата А_В определим множество его состояний S_B и функцию выхода; этой информации достаточно для описания автомата А_В.

Состояние расщепляется в два состояния: и (обратите внимание на дуги, входящие в вершину, отождествляющую состояние S₁ и выходные буквы на них - ). Для удобства переобозначим их соответственно: и . Аналогично поступим и с другими состояниями. В результате получим:

Функции выхода автомата А_В определяются выражениями

Согласно схеме б (рис. 4.3) получим следующие переходы:

-из и переход в состояние ;

-из и переход в состояние ;

-из переход в состояние ;

-из переход в состояние ;

-из и переход в состояние ;

-из и переход в состояние ;

Табличное и графическое представления полученного автомата Мура А_В приведены в табл. 4.5 и на рис. 4.4.

 

Таблица 4.5

/y1
/y2
/y1
/y1
/y2

 

Рис. 4.4. Граф автомата Мура А_В

Пример 4.4. Рассмотрим преобразование автомата Мура А₂, задан-ный табл. 4.4, в автомат Мили A'₂. Поскольку оно простое, приведём готовый результат (табл. 4.6); граф можно построить самостоятельно.

 

Таблица 4.6