ОТ ГРАММАТИКИ К МИНИМАЛЬНОМУ АВТОМАТУ

Для построения сети Петри рассмотрим полученную в курсовой работе по дисциплине «Теория языков программирования и методы трансляции» праволинейную грамматику G”. Это можно сделать, если поставить в соответствие нетерминальным символам места в сети, а терминальным символам – переходы сети. Обозначим места кружками, а переходы – прямоугольниками (полочками). Будем помечать места и переходы соответствующими терминальными и нетерминальными символами. Поскольку сеть Петри – двудольный граф, соединение дугами мест разрешается только через переходы, а переходов - через места.

Если в правой части некоторого правила вывода из R имеет место катенация терминалов, то в сети Петри между переходами, помеченными терминалами, появляются дополнительные позиции. Эти позиции помечаются символами левой части правила вывода с верхними индексами 1,2,…. Поэтому фрагмент сети Петри, соответствующий первому правилу вывода (S x3, x2, x1, A), будет иметь следующий вид (рис.1).

Рис. 1

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

Построим по полученным правилам вывода R’ сеть Петри (рис.2).

Рис. 2

Построенная сеть представляет собой автоматную сеть Петри, и места можно трактовать как состояния конечного автомата, а переходы – как входные символы. Чтобы обеспечить полное соответствие построенной сети Петри автомату Мура, необходимо ввести не показанную на рис.2 заключительную позицию Z, в которую можно направить дуги из переходов, не имеющих исходящих дуг.

Если теперь рассмотреть отдельные фрагменты сети рис.2, то нетрудно заметить одинаковые фрагменты: места А, В и С с одинаковыми инцидентными им переходами x₁ и x₀, а также еще два идентичных фрагмента с местами D и Е, каждому из которых инцидентны по два выходных перехода x₆ и x₇. Аналогично можно отметить места F1 и F4, F2 и F5, а также F3, F6 и F8. В то же время места S1 и S3 идентичны по входу, т.е. из места S в места S1 и S3 дуги идут через переходы x₃.

Функционирование сети не изменится, если «склеить» идентичные фрагменты, что будет соответствовать минимизации числа состояний автомата. Источником недетерминированности могут быть места, из которых исходят дуги, являющиеся входящими дугами переходов, помеченных одинаковыми терминалами. В данном случае таким местом является начальное состояние S и переходы x₃. Таким образом, производится устранение недетерминированности. В результате получим сеть Петри с минимальным числом мест (рис.3).

Можно также установить взаимнооднозначное соответствие между сетью рис.3 и исходным орграфом.

Для этого местам сети ставятся в соответствие состояния автомата, а переходам – пометки на дугах.

Рис. 3