Cтраница 2
Как было установлено в предыдущем параграфе, любое автоматное отображение ф может быть задано конечным множеством М событий во входном алфавите этого отображения. Конечное событие можно задать, перечислив все его элементы. Однако, как уже отмечалось выше, нашей основной целью является рассмотрение отображений с произвольными областями определения. Ясно, что в случае, когда область определения отображения ф бесконечна, хотя бы одно из событий множества М также будет бесконечным. [16]
Результатом первого этапа является сокращенная таблица соответствия автоматного отображения, в которое превратилось исходное отображение р в результате применения операции выравнивания длин слов. [17]
Таким образом, из теоремы 5.2 вытекает, что произвольные автоматные отображения можно задавать с помощью разбиений множества ( Х) всех слов во входном алфавите на конечное число попарно непересекающихся событий. [18]
Сформулируем теперь важное предложение, которое подводит базу под изучение автоматных отображений. [19]
Заметим, что в ряде случаев при превращении заданного отображения в автоматное отображение можно применять не стандартную операцию выравнивания, а какой-нибудь более экономный ( с точки зрения числа дописываемых букв) вариант операции выравнивания. В частности, если само исходное отображение было автоматным, то можно считать, что применяется нулевая операция выравнивания, при которой никакого дописывания пустых букв вообще не происходит. [20]
В связи с некоторыми криптографическими приложениями исследуются свойства полугруппы, порожденной автоматными отображениями обратимого автомата. Основное внимание уделяется изучению орбит этой группы. [21]
Как указывалось выше, абстрактный автомат рассматривается нами как устройство для реализации автоматных отображений. [22]
Из доказательства предложения 2.1 вытекает существование единого конструктивного приема, позволяющего по любому автоматному отображению с конечной областью определения ( заданному на конечном множестве слов) строить индуцирующий это отображение конечный автомат Мили или Мура. Нашей же целью является разработка более общего конструктивного приема, позволяющего строить конечные автоматы Мили и Мура, индуцирующие заданное автоматное отображение не только для случая конечной области определения, авсякий раз, когда такие автоматы существуют. [23]
Как известно, класс взаимно однозначных отображений замкнут относительно суперпозиции, класс конечно автоматных отображений тоже замкнут относительно этой операции, алфавитное кодирование - конечно автоматное отображение веса 1 и алфавитные отображения образуют замкнутый подкласс. [24]
Отображения ( вообще говоря, частичные), индуцируемые абстрактными автоматами, мы будем называть автоматными отображениями. [25]
Два автомата Мили тогда и только тогда эквивалентны между собой ( в смысле совпадения индуцируемых ими автоматных отображений), когда эквивалентны их начальные состояния. [26]
Указанные условия называются условиями автомат-поста отображения, а любое алфавитное отображение, удовлетворяющее этим условиям, является автоматным отображением. [27]
В результате, заменив каждый такой класс эквивалентных состояний одной вершиной, получим минимизированный граф переходов, задающий то же автоматное отображение, что и исходный граф переходов. [28]
Сущность задачи минимизации частичных автоматов состоит в следующем: дан частичный автомат ( Мура или Мили) А, индуцирующий частичное автоматное отображение ф, определенное на некотором множестве М слов входного алфавита. Требуется построить частичный автомат ( Мура или соответственно Мили) В, который индуцирует частичное автоматное отображение, совпадающее на множестве М с отображением ф, и имеет наименьшее число внутренних состояний среди всех автоматов ( Мура или Мили), удовлетворяющих этому условию. [29]
Реализация автомата на современных логических и запоминающих элементах, в том числе многозначных структурах, обусловливает необходимость при его проектировании в переводе автоматного отображения с языка переходов на соответствующий структурный язык. [30]