Материал на экзамен

ляется метка, являющаяся конечным множеством упорядоченных пар из , так, что пара принадлежит метке дуги тогда и только тогда, когда .

Как видно, метка каждой дуги конечного автомата с выходом есть конечное соответствие, функциональное по второй компоненте (т.е. частичное отображение из в ). Область определения этого соответствия называется входной меткой дуги, а область значений — выходной меткой дуги (диаграммы конечного автомата с выходом).

На рис. 7.37 показана диаграмма конечного автомата с выходом, у

, множество состояний при начальном состоянии и заключительном — . Функции переходов и выходов определяются метками дуг. Обычно при изображении диаграмм упо-

рядоченная пара записывается через косую черту:

Можно показать, что два сформулированных выше определения конечного автомата с выходом равносильны и тем самым существует взаимно однозначное соответствие между конечными автоматами с выходом (в смысле второго определения) и ориентированными графами, дуги которых размечены над декартовым произведением двух алфавитов так, как это описано в первом определении. Исходя из этого, мы можем отождествить конечные автоматы с выходом и их диаграммы.

, метки дуг которого получаются «стиранием» всех выходных символов в упорядоченных парах, которыми помечены дуги исходного конечного автомата с выходом (на каждой дуге остает-

ся только ее входная метка). Этот детерминированный конечный автомат будем называть входной проекцией конечного автомата с выходом или V-проекцией конечного автомата с выходом . Входная проекция конечного автомата с выходом, диаграмма которого изображена на рис. 7.37, показана на рис. 7.38.

Функцию выходов конечного автомата с выходом можно доопре-

делить до некоторого отображения из в . Для этого фиксируем произвольно состояние и входную цепочку . Тогда в

единственный путь в (и, следовательно, в диаграмме ), ведущий из в некоторое состояние , на котором читается цепочка . Пусть — входной символ, принадлежащий входной метке не-

которой дуги, исходящей из . Тогда положим , если ; (заметим, что при этом для любых и имеется , т.е. функция выходов конечного автомата с выходом есть сужение функции на подмножество ). В частности, для любой входной цепочки , допускаемой конечным автоматом , положим

(7.11)

функция определенная выражением (7.11), называется функцией, вычисляемой конечным автоматом с выходом .

Так, для конечного автомата на рис. 7.37 имеем, например,

. Можно показать, что функция , вычисляемая данным конечным автоматом, есть биекция регулярного языка

в алфавите , такая, что для каждой

цепочки первого языка цепочка получается заменой каждого вхождения символа символом 0 и заменой каждого вхождения символа символом 1.

Функция из в называется ограниченно детерминированной функцией (или ОД-функцией), если она вычисляется некоторым конечным автоматом с выходом.

Замечание 7.13. Термин «ограниченно детерминированная функция» связан с тем, что множество всех функций вида

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

Таким образом, каждый конечный автомат с выходом вычисляет некоторую ОД-функцию. С интуитивной точки зрения это значит, что

конечный автомат с выходом работает как «детерминированный преобразователь» слов (цепочек) во входном алфавите в слова (цепочки) в выходном алфавите. В отличие от обычного конечного автомата, который является чистым «распознавателем», конечный автомат с выходом снабжен выходной лентой, на которую записывается выходная

цепочка для заданной входной цепочки (рис. 7.39).

Для конечных автоматов с выходом может быть поставлена задача структурного синтеза. Содержательно ее можно представить как задачу, аналогичную задаче реализации булевой функции или булева оператора схемой из функциональных элементов. Однако в отличие от СФЭ, реализующей булев оператор, «схема», которая реализует ОДфункцию (или, что то же, вычисляющий ее конечный автомат с выходом), должна помимо функциональных элементов, каждый из которых вычисляет некоторую булеву функцию из заданного конечного множества функций, содержать так называемые элементы задержки, позволяющие хранить информацию о текущем состоянии автомата.

Чтобы объяснить это, представим себе (на интуитивном уровне) процесс работы конечного автомата с выходом во времени.

В начальный момент времени (время дискретно) блок управления конечного автомата с выходом находится в начальном состоянии

. Предположим, что в произвольный момент времени состояние есть . Пусть в этот момент времени конечный автомат считывает с входной ленты символ . Тогда в этот же момент времени на выходной ленте появится выходной символ , а его

устройство управления перейдет в состояние , в котором и останется до следующего момента времени . При этом выполняются соотношения

(7.12)

Эти соотношения называют каноническими уравнениями данного

конечного автомата с выходом.

Из канонических уравнений (7.12) вытекает, что «схема», реализующая конечный автомат с выходом, должна иметь « память» о состоянии устройства управления в предыдущий момент времени. Эта «память» реализуется с помощью так называемых элементов задержки, или триггеров.

Конструированию «схемы» предшествует двоичное кодирование входных и выходных символов, а также состояний устройства управления. Это значит, что каждому состоянию или символу однозначно сопоставляется булев вектор (набор) соответствующей размерности. В общем виде искомая «схема» должна содержать два блока: назовем их комбинационной частью (КЧ) и запоминающей частью (ЗЧ) (рис. 7.40). На вход комбинационной части поступают в каждый момент

времени двоичный код входного символа (булев вектор ) и

двоичный код состояния от запоминающей части (булев вектор ), а с выхода комбинационной части снимается двоичный код выходного

символа (булев вектор ) и двоичный код следующего состояния (булев вектор ).

Если через и обозначить булевы операторы, сопоставленные в результате указанного выше двоичного кодирования функциям перехода и выхода соответственно, то канонические уравнения примут вид

(7.13)

Таким образом, комбинационная часть строится как некая схема из функциональных элементов, реализующая булев оператор, определяемый первыми двумя уравнениями (7.13), тогда как запоминающая часть содержит необходимое число триггеров и реализует «задержку»

. Каждый триггер есть устройство преобразования «одноразрядного двоичного сигнала» (с математической точки зрения булева вектора размерности 1), состоящего в задержке этого сигнала «на один такт». Иначе говоря, если в момент времени на вход

триггера поступает сигнал, в момент с выхода триггера

снимается сигнал . Обычно рассматривают триггеры с двумя выходами: прямым и инверсным. Прямой выход работает так, как описано выше, а инверсный выдает сигнал, являющийся отрицанием сигнала прямого выхода (рис. 7.41).

Теперь обсудим вопрос о размерности булевых векторов, кодирующих состояния и символы обоих алфавитов. Произвольное непустое конеч-

ное множество может быть «закодировано» двоич-

ными числами таким образом: нумеруем элементы от 0 до и эти номера записываем в двоичной системе счисления. Нетрудно со-

образить, что тогда разрядность этих чисел (или, что то же самое, размерность соответствующих булевых векторов) составит

(ближайшее целое, большее ). Так, если , то для того, чтобы закодировать числа от 0 до 14, нужны четырехразрядные двоич-

ные коды, поскольку . Заметим, что в общем случае, по-

скольку число не будет целым, не все двоичные числа соответствующей разрядности будут использованы. Так, при не будет использовано число 1111 (двоичный код числа 15).

Тогда размерности булевых векторов (кодов входных символов), (кодов выходных символов), и (кодов текущего и нового состояний) соответственно будут равны:

Предлагается следующий алгоритм определения булевых операторов и в (7.13).

1.Составляется таблица для функций переходов и выходов исходного конечного автомата с выходом (табл. 7.1).

2.По составленной таблице (см. табл. 7.1) строят так называемую структурную таблицу (табл. 7.2), в которой каждый символ (входной и

выходной) и каждое состояние заменяются их двоичным кодом, причем так, что если набор есть код текущего состояния , набор есть код входного символа , то

тогда и только тогда, когда набор есть код выходного символа , a

тогда и только тогда, когда набор есть код состояния

.

Структурная таблица есть не что иное, как таблица, задающая некоторый булев оператор (вообще говоря, частичный, так как не все векторы соответствующей размерности служат кодами элементов множеств

) из в . Этот оператор может быть реализован некоторой схемой из функциональных элементов (как правило, над стандартным базисом). Вектор поступает (в некоторый момент времени ) на входы к триггеров, с прямых выходов которых (в мо-

мент времени ) снимается вектор , то есть . Таким образом, если в начальный момент времени с выхода за-

поминающей части снимается вектор , код начального состояния

и триггеры запоминающей части будут хранить уже информацию о новом состоянии до момента времени и т.д.

В этом небольшом дополнении мы никак не можем сколько-нибудь подробно и строго обсуждать математическую теорию реализации ОД-функций «схемами» с элементами задержки. Разумеется, нет и речи о каких-либо доказательствах. Также мы не решаем «инженернотехнические» проблемы структурного синтеза, в частности проблемы «аппаратной реализации» триггеров. Наша цель здесь — показать в рамках самого элементарного изложения связь между теорией конечных автоматов и теорией булевых функций. Эта связь состоит в том, что теория булевых функций дает аппарат для структурного синтеза конечных автоматов (с выходом), т.е. для перехода от описания

Для частичных булевых функций

Составим карты Карно и найдем для каждой из них минимальную ДНФ.

Для функции карта Карно изображена на рис. 7.43. Единственная склейка дает . Для второй функции получим (рис. 7.44)

. Для функции имеем (рис. 7.45) минимальную ДНФ . Наконец, для функции по карте Карно, изображенной на рис. 7.46, находим .