Cтраница 1
Операция расщепления i-классов выполняется очевидным образом с помощью использования таблиц переходов рассматриваемого множества автоматов. [1]
Всякая нерасщепляемая система обобщенных i-классов состояний автомата является системой инвариантных классов. [2]
Определим теперь так называемую операцию расщепления i-классов. [3]
Для того чтобы получить расщепление правильной системы обобщенных i-классов автомата А, достаточно разбить все состояния автомата А на попарно непересекающиеся множества так, чтобы все состояния, входящие в любое из таких множеств, отмечали бы совместимые между собой обобщенные столбцы i-таблицы автомата А. [4]
В самом деле, пусть N - произвольное множество, возникшее в результате применения операции расщепления к одному из i-классов Kr ( i) данного множества автоматов М, не входящее ни в какое другое множество того же вида, а ат и ап - два произвольных состояния из N. Рассмотрим произвольное слово ptxp, имеющее длину i 1, и будем считать сначала, что рассматриваемое множество М состоит из автоматов Мили. [5]
Если для некоторого i разбиение состояний автомата на ( i -) - 1) - классы совпадает с разбиением на i-классы, то оно является разбиением и на ос-классы. [6]
На практике обычно пользуются следующим приемом минимизации частичных автоматов: мысленно заполняя прочеркнутые места в таблицах переходов и выходов данного частичного автомата А, объединяют состояния в i-классы и минимизируют по тем же самым правилам, что и в случае обычных ( всюду определенных) автоматов. Все или некоторые из возникающих вариантов объединения состояний в классы проверяются, и из полученных канонических минимизаций выбирают ту, которая имеет наименьшее число состояний. [7]