Класс терминальных языков сетей Петри:
1. Строго мощнее, чем класс языков, порождаемых регулярными грамматиками .
2. Не сравним с классом языков, порождаемых КС грамматиками .
3. Менее мощен, чем класс языков, порождаемых произвольными грамматиками .
Таким образом .

ДОКАЗАТЕЛЬСТВО.
A. Докажем, что .
Произвольный регулярный язык может быть представлен помеченной сетью Петри , порождающей тот же язык в качестве терминального.
Если задана помеченная сеть Петри и регулярная грамматика , то каждому нетерминальному знаку поставим в соответствие позиции .

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

Начальная маркировка такова, что число меток в позиции равно

Пример. Пусть задана регулярная грамматика

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

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

Пример. Пусть есть следующая сеть Петри

Данная сеть Петри порождает строки следующего вида — правильно расставленные скобки. Тогда грамматика порождающая этот язык будет

Очевидно, что грамматика — КС грамматика. Язык невозможно породить регулярной грамматикой.
B. Докажем, что не сравним с , то есть . То есть не все КС языки могут быть представлены сетями Петри, а так же есть языки, представимые сетями Петри, но которые не могут быть порождены КС грамматиками.

Пример. Приведем пример не КС языка, порождаемого сетью Петри.
Рассмотрим язык . Ранее доказывалось, что этот язык порождается контекстной грамматикой (см глава 1).

Однако существует КС язык, на порождаемый сетью Петри.

Пример. Рассмотрим следующую грамматику с продукциями вида . Очевидно, что данная грамматика порождает строки вида .
C. Таким образом получаем:

где КА – конечный автомат,
МА – магазинный автомат,
2-Х МА – двухстековый магазинный автомат,
МТ – машина Тьюринга.
Окончание доказательства.

Вывод. Какова – бы ни была сеть Петри машина Тьюринга лучше.