Cтраница 3
На практике обычно пользуются следующим приемом минимизации частичных автоматов: мысленно заполняя прочеркнутые места в таблицах переходов и выходов данного частичного автомата А, объединяют состояния в i-классы и минимизируют по тем же самым правилам, что и в случае обычных ( всюду определенных) автоматов. Все или некоторые из возникающих вариантов объединения состояний в классы проверяются, и из полученных канонических минимизаций выбирают ту, которая имеет наименьшее число состояний. [31]
Возникающий здесь параллелизм имеет, однако, место не при минимизации обычных всюду определенных автоматов, а при переходе к более общей задаче минимизации частичных автоматов. [32]
Соответствующий автомат полностью определен, если фг ( а, q) 1 при любых а е А и q Q, в противном случае имеем частичный автомат. Легко заметить, что область определения частичного автомата всегда представляет собой конечно перечислимое множество. [33]
Если функцию переходов произвольного частичного автомата Мили А рассматривать не заданной во всех точках, в которых не задана его функция выходов то возникший таким образом новый частичный автомат Мили В будет, индуцировать то же самое частичное отображение, что и автомат А. [34]
Нетрудно видеть, что в силу определения событий, представленных в автомате, введенное таким образом частичное отображение ф как раз и будет тем частичным отображением, которое индуцируется заданным частичным автоматом А. [35]
Если операция умножения применяется к вполне определенным автоматам, то в результате получаем вполне определенный автомат, если же хотя бы один из исходных автоматов частичный, то в результате получим частичный автомат. [36]
Основной задачей настоящего параграфа является раз работка таких конструктивных приемов, которые позволяли бы по любому данному конечному автомату Мили или Мура А находить эквивалентный ему ( или, в случае частичных автоматов, эквивалентно продолжающий его) автомат Мили или соответственно автомат Мура, которые имели бы наименьшее возможное число состояний. Эта задача носит название задачи минимизации конечных автоматов. Напомним, что вполне определенные автоматы называются эквивалентными, если они индуцируют одно и то же отображение, а частичный автомат А называется эквивалентным продолжением частичного автомата В, если индуцируемое им отображение совпадает с отображением, индуцируемым автоматом В на всех допустимых для автомата В словах. [37]
Говорят, что частичное отображение ф продолжает частичное отображение 5, если область определения отображения ф включает в себя область определения М отображения ty, а на области М оба отображения совпадают. Частичный автомат А называется эквивалентным продолжением частичного автомата В, если частичное отображение, индуцируемое автоматом А, продолжает частичное отображение, индуцируемое автоматом В. [38]
Подобно вполне определенным автоматам частичные автоматы также делятся на автоматы первого и второго рода, автоматы Мили и автоматы Мура. Изоморфизм частичных автоматов предусматривает, чтобы соответствующее изоморфное отображение переводило множества значений, в которых не определены функции переходов или выходов ( обычная или сдвинутая) одного автомата, в множества значений, в которых не определены соответствующие функции другого автомата. [39]
Сущность задачи минимизации частичных автоматов состоит в следующем: дан частичный автомат ( Мура или Мили) А, индуцирующий частичное автоматное отображение ф, определенное на некотором множестве М слов входного алфавита. Требуется построить частичный автомат ( Мура или соответственно Мили) В, который индуцирует частичное автоматное отображение, совпадающее на множестве М с отображением ф, и имеет наименьшее число внутренних состояний среди всех автоматов ( Мура или Мили), удовлетворяющих этому условию. [40]
В клетке диаграммы Вейча ставится О, 1 либо bi в зависимости от того, какое значение имеет функция возбуждения на наборе аргументов, соответствующем этой клетке диаграммы. В случае частичных автоматов некоторые клетки диаграммы оказываются незаполненными. [41]
Отображение К, индуцируемое некоторым автоматом 1 с конечным числом состояний, будем называть автоматным кодированием, а автомат Ч21 - кодирующим автоматом. Аналогичным образом определяются частичные автоматы, для которых функции / ии определены на некотором подмножестве множества S X А и, следовательно, отображение К [ определено на некотором подмножестве слов в А. [42]
Рассмотрим теперь некоторые соотношения между областями определений функций переходов и выходов в частичном автомате. Предположим, что мы имеем частичный автомат Мили А, и пусть для некоторого состояния ai и входного сигнала х его функция выходов не определена. Это означает, очевидно, что переход автомата из состояния а ( в новое состояние под воздействием входного сигнала Xj реализуется лишь при подаче на вход автомата запрещенных входных слов. [43]
Говорят, что частичное отображение ф продолжает частичное отображение 5, если область определения отображения ф включает в себя область определения М отображения ty, а на области М оба отображения совпадают. Частичный автомат А называется эквивалентным продолжением частичного автомата В, если частичное отображение, индуцируемое автоматом А, продолжает частичное отображение, индуцируемое автоматом В. [44]
Соответствующий автомат полностью определен, если фг ( а, q) 1 при любых а е А и q Q, в противном случае имеем частичный автомат. Легко заметить, что область определения частичного автомата всегда представляет собой конечно перечислимое множество. [45]