Асинхронные автоматы: классификация и тестирование (стр. 7 )

Заметим, что если для некоторого допустимого слова uw имеет место W(ueω)<W(uw), то из определения отношения "<" следует, что W(ueω) содержит хотя бы одно конечное слово. Поэтому необходимым и достаточным условием отсутствия в W(ueω)  конечных слов является отсутствие недопустимых слов вида uw и для всех допустимых слов вида uw равенство (с учетом свойства 2) W(ueω)=W(uw).

Пример автомата класса M`f0, не моделируемого классом A0 из-за нарушения свойства 3, приведен на рис.2.4.7. В этом автомате для X={x, x`} W(eω)={yω} и в тоже время существует недопустимое слово xx`w, где w - любое бесконечное слово.

Рис.2.4.7

Теорема об автомате без смешанных состояний и e-переходов доказана.

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

2.5. Общая картина взаимосвязей классов асинхронных автоматов с точки зрения словарной функции

Если рассматривать автоматы, в которых e-переходы определены только в принимающих состояниях (не определены в смешанных состояниях), то, очевидно, мы получим следующие классы автоматов Bi=Mi1∩Mi2=Mi1∩Mi3=Mi2∩Mi3, Bf=Mf1∩Mf2=Mf1∩Mf3=Mf2∩Mf3,

B`f=M`f1∩M`f2=M`f1∩M`f3=M`f2∩M`f3.

Теперь определим разбиение класса всех асинхронных автоматов на непересекающиеся области (таб.2.5.1)

область	определение	смешанные состояния	e-переходы	состояния с одними e-переходами	имп. фак.	e-переходы в смешанных состояниях	приоритет в смешанных состояниях	финальная допустимость
a0=	A0	нет	нет	нет	-	нет	-	совпадает
a1=	A1\A0	нет	есть	нет	-	нет	-	совпадает
a=	A\A1	нет	есть	есть	-	нет	-	совпадает
mi0=	Mi0\A0	есть	нет	нет	имп.	нет	-	совпадает
bi=	Bi\(A∪Mi0)	есть	есть	-	имп.	нет	-	совпадает
mi1=	Mi1\Bi	есть	есть	-	имп.	есть	пос. и пуст.	совпадает
mi2=	Mi2\Bi	есть	есть	-	имп.	есть	e-переходы	совпадает
mi3=	Mi3\Bi	есть	есть	-	имп.	есть	равный	совпадает
m`f0=	M`f0\A0	есть	нет	нет	фак.	нет	-	совпадает
mf0=	Mf0\M`f0	есть	нет	нет	фак.	нет	-	нет
b`f=	B`f\(A∪M`f0)	есть	есть	-	фак.	нет	-	совпадает
bf=	Bf\(B`f∪Mf0)	есть	есть	-	фак.	нет	-	нет
m`f1=	M`f1\B`f	есть	есть	-	фак.	есть	пос. и пуст.	совпадает
m`f2=	M`f2\B`f	есть	есть	-	фак.	есть	e-переходы	совпадает
m`f3=	M`f3\B`f	есть	есть	-	фак.	есть	равный	совпадает
mf1=	Mf1\Bf	есть	есть	-	фак.	есть	пос. и пуст.	нет
mf2=	Mf2\Bf	есть	есть	-	фак.	есть	e-переходы	нет
mf3=	Mf3\Bf	есть	есть	-	фак.	есть	равный	нет

Таб.2.5.1

Теперь можно представить классы автоматов как объединения областей (таб.2.5.2).

класс

базовое выражение

области разбиения

a0

a1

a

mi0

bi

mi1

mi2

mi3

m`f0

mf0

b`f

bf

m`f1

m`f2

m`f3

mf1

mf2

mf3

A0

= a0

A1

= A0∪a1

A

= A1∪a

Mi0

= A0∪mi0

Bi

= A∪Mi0∪bi

Mi1

= Bi∪mi1

Mi2

= Bi∪mi2

Mi3

= Bi∪mi3

M`f0

= A0∪m`f0

Mf0

= M`f0∪mf0

B`f

= A∪M`f0∪b`f

Bf

= B`f∪Mf0∪bf

M`f1

= B`f∪m`f1

M`f2

= B`f∪m`f2

M`f3

= B`f∪m`f3

Mf1

= Bf∪mf1

Mf2

= Bf∪mf2

Mf3

= Bf∪mf3

Таб.2.5.2