Cтраница 2
Рассмотрим отображение, индуцируемое частичным автоматом. Будем подавать на вход автомата, установленного предварительно в начальное состояние, различные слова входного алфавита. В этом случае говорят, что входное слово р является запрещенным для данного частичного автомата. Совокупность всех запрещенных слов образует область запрета данного автомата. Слова, не являющиеся запрещенными, называются допустимыми, а их совокупность - множеством допустимых слов автомата. [16]
Наряду с полностью определенными рассматривает частичные автоматы, у которых область определения функций б ( a, z) или К ( a, z) отлична от Ay Z. Моменты переходов автомата из состояния в состояние могут разделяться равными или неравными промежутками. [17]
Наконец, совершаем переход к частичному автомату. [18]
Из определения допустимых слов ( для любого данного частичного автомата А) вытекает, что в случае, когда входное словоpxtix - L... Обычно к числу начальных отрезков слова р причисляют само это слово, а также пустое слово, не содержащее ни одной буквы. Сделанное замечание позволяет сформулировать следующее предложение. [19]
На практике обычно пользуются следующим приемом минимизации частичных автоматов: мысленно заполняя прочеркнутые места в таблицах переходов и выходов данного частичного автомата А, объединяют состояния в i-классы и минимизируют по тем же самым правилам, что и в случае обычных ( всюду определенных) автоматов. Все или некоторые из возникающих вариантов объединения состояний в классы проверяются, и из полученных канонических минимизаций выбирают ту, которая имеет наименьшее число состояний. [20]
Несколько сложнее обстоит дело с понятием эквивалентности частичных автоматов. Для того чтобы определить это понятие, необходимо прежде всего установить, что следует понимать под отображением, индуцируемым данным частичным автоматом А. Для этой цели, как и прежде, мы будем подавать на вход частичного автомата ( приведенного предварительно в начальное состояние) различные входные слова. А, мы можем столкнуться с положением, когда соответствующий ей выходной сигнал не определен. [21]
Еще одно замечание касается способов практического использования понятия частичного автомата. Обычно все реально существующие автоматы являются вполне определенными. Однако они могут быть поставлены в такие условия, что некоторые слова их входного алфавита никогда не подаются на их вход. [22]
Уже на этом примере видно, что для частичных автоматов / - классы, вообще говоря, пересекаются между собой. То же самое имеет место и для оо-классов. [23]
Сущность задачи минимизации частичных автоматов состоит в следующем: дан частичный автомат ( Мура или Мили) А, индуцирующий частичное автоматное отображение ф, определенное на некотором множестве М слов входного алфавита. Требуется построить частичный автомат ( Мура или соответственно Мили) В, который индуцирует частичное автоматное отображение, совпадающее на множестве М с отображением ф, и имеет наименьшее число внутренних состояний среди всех автоматов ( Мура или Мили), удовлетворяющих этому условию. [24]
В структурной теории принято несколько отличное от абстрактной теории понимание частичных автоматов. [25]
Отображение ф множества входных слов в множество выходных слов, индуцируемое частичным автоматом А, является, таким образом, частичным отображением, областью определения которого служит множество всех допустимых слов данного автомата. Образ ф ( р) любого допустимого слова при этом отображении определяется точно так же, как и для вполне определенных автоматов. [26]
Определим понятие связного автомата [113], которое играет важную роль при изучении частичных автоматов. [27]
Рассмотрим теперь некоторые соотношения между областями определений функций переходов и выходов в частичном автомате. Предположим, что мы имеем частичный автомат Мили А, и пусть для некоторого состояния ai и входного сигнала х его функция выходов не определена. Это означает, очевидно, что переход автомата из состояния а ( в новое состояние под воздействием входного сигнала Xj реализуется лишь при подаче на вход автомата запрещенных входных слов. [28]
Если отображение ф множества слов в алфавите Ж в множество слов в алфавите 3) задается частичным автоматом, то оно будет, разумеется, лишь частичным отображением, определенным не на всех словах. Однако для него по-прежнему будут выполняться оба условия автоматности при дополнительном предположении, что ф ( /) существует. [29]
Запрещенными здесь и далее будем называть все слова во входном алфавите, которые при подаче их на вход данного частичного автомата приведут хотя бы для одного составляющего их входного сигнала к не определенному в автомате выходному сигналу. [30]