О моделирующих возможностях сетей Петри.

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

Однако важен и вопрос о том, насколько широкий класс объектов могут моделировать сети Петри. В п. 2.1.3. говорилось о свободном языке сети Петри, который представляет собой некоторое подмножество всех слов в алфавите Т. Множество свободных языков всех сетей Петри образует класс свободных языков сетей Петри.

В ряде случаев язык сети Петри можно изменить, связав с некоторыми переходами сети N определенные символы из алфавита А, и часть переходов оставить непомеченными (вернее, помеченными пустым символом λ). В этом случае говорят о помеченной сети Петри (PN, ∑ ), где ∑: Т → А – помечающая функция, ставящая в соответствие переходам t_j € T символы а_{к €} А. Ясно, что обычная сеть Петри есть частный случай помеченной сети Петри при Т = A={t₁...t_n}.

Помеченную сеть Петри можно рассматривать как генератор слов и изучать ее возможности с точки зрения математической лингвистики.

Рассмотренные в п. 2.1.5. расширения сетей Петри порождают другие классы языков.

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

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

В [8, 9] доказываются следующие утверждения:

1.Класс помеченных сетей Петри строго мощнее класса конечных автоматов и строго менее мощен, чем класс машин Тьюринга.

2.Классы ингибиторных сетей и сетей с приоритетами строго мощнее класса сетей Петри и равномощны классу машин Тьюринга.

3.Класс раскрашенных сетей при конечном количестве цветов равномощен классу сетей Петри.

4. Класс самомодифицируемых сетей эквивалентен классу ингибиторных сетей и сетей с приоритетами.