6. Использование сетей Петри при переходе от грамматики к минимальному автомату.

Возвратившись к заданной праволинейной грамматике, построим для нее сеть Петри. Это можно сделать, поставив в соответствие нетерминальным символам позиции сети, а терминалам - переходы.

Рисунок 4

Получившаяся на рис.4 сеть является автоматной сетью Петри, ее позиции можно трактовать как состояния конечного автомата, а переходы - как входные символы. Способом, аналогичным рассмотренному в п. 4 устраним недетерминированность автомата, а для полноты соответствия построенной сети Петри распознающему автомату Мура введем заключительную позицию Z, в которую направим дуги из всех переходов, ранее не имеющих исходящих дуг. Окончательно придем к рис. 5.

Рисунок 5

7. Размещение состояний автомата.

Один из способов размещения состояний синхронного автомата состоит в произвольном назначении им кодовых наборов. Рассмотрим такое размещение для нашего случая. Состоянию r_i поставим в соответствие вершину 4-мерного куба с десятичным номером i, который определяется по значения ее двоичных координат z₁, z₂, z₃, z₄ в соответствии с формулой

i= z₁2⁰+z₂2¹+z₃2²+z₄2³. Число внутренних переменных, изменяющих свои значения при переходе автомата из одного состояния в другое, есть расстояние по Хеммингу между этими состояниями. Очевидно, что чем меньше внутренних переменных изменяется при каждом переходе автомата, тем меньше конституент единицы содержат их переключательные функции. В силу этого второй вариант размещения состояний может выполняться в соответствии с критериями минимальности по Хеммингу по всем переходам. Суть такого размещения заключается в максимально возможном использовании соседних кодов. Коды состояний называются соседними, если при переходе автомата из одного состояния в другое изменяет свое значение лишь одна кодирующая переменная.

Собственно кодирование состоит во вложении графа переходов автомата в куб, соответствующий минимальной размерности (в данном случае - в 4 - мерный куб). Вложение будем осуществлять неформально, методом проб и ошибок. В результате придем к картинке на рис.6.

Рисунок 6

Оказалось, что из 22 возможных переходов 17 являются соседними, а 5 имеют расстояние 2. Значение принятого критерия размещения (суммарного расстояния по Хеммингу по всем возможным переходам) в данном случае равно 27. Возможно, существует более эффективное размещение, однако установление этого факта связано с перебором очень большого числа вариантов.

8. Структурный и логический синтез распознающего автомата.

Переходя к синтезу распознающего автомата, необходимо условиться о способе его реализации. Уже выбрана синхронная модель. Теперь примем соответствующую структурную схему, которая изображена на рис.7. Она состоит из комбинационной схемы, реализующей функции возбуждения элементов памяти; памяти, построенной из триггеров по двухрегистровой схеме; дешифратора входных сигналов. При синхронной реализации автомата нет необходимости бороться с функциональными и логическими состояниями в комбинационной схеме и дешифраторе, так как предполагается, что все переходные процессы в этих схемах успевают закончиться к моменту прихода синхросигнала t₁, стробирующего прием информации с выходов комбинационной схемы в триггеры регистра 1. Второй триггерный регистр, прием информации в который стробируется синхросигналом t₂, необходим для того, чтобы сделать все состояния автомата устойчивыми и исключить влияние гонок. Триггеры регистра 1 будем называть вспомогательными, а регистра 2 - основными. Сигнал z₅ является сигналом ОШИБКА, а сигнал z₆ - сигналом принадлежности входной цепочки символов языку с грамматикой G’’. С помощью сигнала НУ осуществляется начальная установка основных триггеров автомата.

Рисунок 7

Следует заметить, что сложность реализации автомата зависит от способа кодирования входных символов. Однако часто полагают, что по определенным соображениям входные символы уже закодированы. Включим в множество входных символов дополнительный символ, которым заканчивается любая входная цепочка, принадлежащая языку. В качестве такого символа может быть использован любой свободный символ, например, х₃, для нашего примера.

Предположим, что входные символы х₀ - х₇ представлены двоичными кодами с помощью трех кодирующих переменных р₁, р₂ и р₃. В структуре автомата выделен дешифратор, преобразующий двоичный код символов, представленных переменными р₁, р₂ и р₃, в унитарный код, в котором только одна из выходных переменных принимает значение 1, в то время как все другие равны 0. Выходы дешифратора обозначим входными символами х₀ -х₇. Если эти символы были закодированы таким образом, что их номера являются десятичными эквивалентами двоичных кодов, то непосредственно из таблицы кодирования, представленной в табл.8, получим х₇=р₁р₂р₃.

Рисунок 8 Таблица 8

Символ	p1	p2	p3
x0 x1 x2 x3 x4 x5 x6 x7	0 1 0 1 0 1 0 1	0 0 1 1 0 0 1 1	0 0 0 0 1 1 1 1

Реализация дешифратора показана на рис. 8. Она содержит 8 элементов типа 3 И-НЕ и 14 входных инверторов, причем 3 входных инвертора используются лишь с целью уменьшения нагрузки на входные сигналы. Комбинационная схема автомата реализует функцию его переходов. Исходным заданием для ее построения является граф переходов (рис.3) или таблица переходов (табл.7) и выбранный вариант кодирования состояний. Построить функцию переходов - значит найти переключательную функцию кодирующих (внутренних) переменных. В соответствии со структурной схемой автомата каждая внутренняя переменная представляется состоянием элемента памяти - триггера. По переключательным функциям внутренних переменных могут быть найдены функции возбуждения соответствующих им триггеров. Реализация этих функций образует комбинационную схему автомата. Сложность функций возбуждения и, соответственно, сложность комбинационной схемы существенно зависит от выбора тира триггера. Известны три основных типа триггеров - это D-триггер, RS-триггер и Т-триггер. Поскольку заранее невозможно отдать предпочтение ни одному из этих типов, необходимо построить функции возбуждения для всех указанных типов триггеров. Для нашего примера результаты выполнения этапа представлены в табл. 9.

В графе «Код состояния» таблицы приведены все возможные наборы значений внутренних переменных z₁z₂z₃z₄. В графе «Символ состояния» в соответствии с рис.8 эти наборы помечены условными обозначениями состояний. Четыре набора, которые не соответствуют никаким состояниям, помечены прочерками. Столбцы третьей, четвертой и пятой граф определяют функции возбуждения D, RS, и Т-триггеров соответственно.

После задания всех функций возбуждения триггеров трёх типов необходимо выполнить этап их минимизации. Для нахождения ДНФ функций возбуждения вновь воспользуемся их геометрическим представлением. При выполнении минимизации сначала выписываются импликанты, накрывающие зачернённые вершины (и, возможно, некоторые вершины, помеченные звёздочками). После этого можно считать, что остальная часть функций задана на этих вершинах произвольно. Затем выписываются импликанты, каждая из которых накрывает одинаково отмеченные полузачернённые вершины и, возможно, некоторые вершины с произвольными заданиями, и зачернённые вершины. Функцию покрывают наименьшим числом импликант минимального ранга.

Построим теперь переключательные функции z₅, z₆, представляющие выходные сигналы автомата. Сигнал z₆ принадлежности цепочки входных символов языку с грамматикой G’’ принимает значение 1, если автомат находится в заключительном состоянии r₁₁ или r₁ и на его вход поступает сигнал конца цепочки символов х₃ = 1; в противном случае z₆ = 0. Следовательно, z₆ = x₃z₂z₃z₄. Функция сигнала ошибки может быть построена точно так же, как функция z₁ - z₄, но для уменьшения сложности её реализации воспользуемся следующим соображением. Сигнал ошибки вырабатывается тогда, когда при поступлении очередного входного символа внутреннее состояние автомата не изменяется (кроме случая, когда автомат находится в заключительном состоянии и на его вход подаётся символ конца цепочки). Поэтому для нашего случая z₅ = f₁vf₂vf₃vf₄vz₆, где f_i - функция, принимающая значение 1, если i - й триггер переключается при переходе автомата из одного состояния в другое. Очевидно, что для Т-триггера f_i =T_i, для D-триггера f_i = Z_iD_i v z_i D_i и для RS-триггера f_i = z_i R_I v z_i S_i;. Каждый D и RS-триггер вносит в функцию переключения z₅ сложность, равную 4, а Т-триггер - сложность 1. Эту оценку следует прибавить к оценкам сложности функций переключения, приведенных в табл. 9, и выбрать минимальные по сложности функции возбуждения (и типы) триггеров.

С целью исключения возможного влияния функциональных состязаний, а также с целью фиксации ошибки до момента принятия решения z₅ удобно представить состоянием любого триггера, стробируемого синхросигналом. Сигал z₆ тоже следует стробировать, но это может быть сделано вне автомата.