Использование сетей Петри при переходе от грамматики к минимальному автомату
Возвратимся к заданной праволинейной грамматике G’. Построим для нее сеть Петри. Это можно сделать, поставив в соответствие нетерминальным символам позиции (кружки) сети, а терминалам – переходы (палочки) сети. Будем помечать позиции и переходы соответствующими нетерминалами и терминалами. Поскольку сеть Петри является двудольным графом, соединение дугами позиций разрешается только через переходы, а переходов – через позиции. Если в правой части некоторого правила вывода из R’ имеет место конкатенация терминалов, то в сети Петри между переходами, помеченными терминалами, должны появиться дополнительные позиции, которые можно помечать символами левой части правил вывода с верхними индексами 1,2,… Так, фрагмент сети Петри, соответствующий первому правилу вывода (Sx7 x3 x7A), будет иметь вид:
S
x7
S1
x3
S2
x7
A
При построении остальных фрагментов, соответствующих последцющим правилам вывода, следует использовать ранее обозначенные позиции. Таким образом, позиции могут иметь несколько входящих и исходящих дуг, а переходы – в точности по одной входящей и не более чем по одной исходящей дуге. Построим сеть Петри для данного атомата.
x1
x4
x5
x1
x0
S1
S2
A
D
x0
S
x0
x7
x5
x2
S3
S4
B
x2
x5
x3
x5
x0
E
x1
x2
C
x6
x3
x3
x3
F1
F2
F3
F
x7
x0
x3
x3
x3
F4
F5
F6
F8
x5
x3
x3
F7
Рис. 7 Сеть Петри, соответствующая исходной грамматике
Можно установить взаимно-однозначное соответствие между сетью рис.8 и графом переходов минимального автомата рис.5. Позициям сети рис.8 для наглядности приписаны обозначения состояний (в скобках), переходам – пометки на дугах рис.5.
От рисунка 8 можно перейти к графу переходов автомата, устранив переходы и взвесив дуги наименованиями этих переходов.
x0
x0
S2 (r5)
A, B,С(r0)
S1,S3(r4)
x5
D, E (r1)
S(r11)
x1
x5
S4 (r6)
x7
x1
Z (r10)
x3
x4
x2
F3,F6, F8 (r3)
F1(r8)
x6
x3
F2, F5, F7 (r2)
x3
F (r7)
x7
x3
x5
x0
x3
F4 (r9)
Рис.8 Сеть Петри, полученная в результате упрощения
Размещение состояний автомата
На этапе кодирования (размещения) состояний автомата осуществляется выбор способа размещения, существенно зависящего от типа реализуемого автомата (синхронный или асинхронный). Для асинхронного автомата необходимо применить противогоночное кодирование, например, соседнее или квазисоседнее размещение. Синхронный автомат не требует противогоночного размещения, и его состояния могут быть закодированы кодами минимальной длины. Далее будем предполагать, что реализуемый автомат является асинхронным.
Длина кода измеряется числом переменных (двоичных), набор значений которых образует кодовую комбинацию из нулей и единиц. Наименьшее число переменных, необходимых для кодирования синхронного автомата с N состояниями, определяется как n = [log2N].
Один из способов размещения состояний синхронного автомата состоит в произвольном назначении им кодовых наборов. Состоянию r1поставим в соответствие вершину 4-мерного куба с десятичным номером i, который определяется по значению ее двоичных координат z1, z2, z3, z4 в соответствии с формулой i = z120 + z221 + z322 + z423. В этом случае вершине с координатами 0000 соответствует состояние r0, вершине с координатами 1000 – r3. При таком варианте кодирования переход автомата из одного состояния в другое в общем случае может сопровождаться изменениями значений нескольких кодирующих (внутренних) переменных.
Собственно кодирование состоит во вложении графа переходов автомата в куб, соответствующий минимальной размерности.
r11111
r5
x0
x1
x0
x3
x7
r4
r7
r8
r9
r2
r3
x6
x4
r1
r0
x5
x3
x0
x7
x5
x2
x5
r6
r10550000000000
x1
x3
x3
x3
Рис.9 Результат вложения графа минимального автомата в 4-мерный куб