Сети Петри и языки

[arseniiv]

Пусть дана сеть Петри, в которой каждому переходу $t$ соответствует некоторая строка $s(t)$. Каждой последовательности разрешённых переходов $(p_1, \ldots, p_n)$, переводящей маркировку $(0, \ldots, 0)$ в $(0, \ldots, 0)$, поставим в соответствие строку $s(p_1)\cdots s(p_n)$. Пусть язык сети — это множество всех таких строк.

Скажите, где можно почитать исследования по таким вот языкам и их грамматикам. Не совсем понятно, обязательно ли грамматика будет контекстно-свободной и как её получить из сети.

Например, сеть с позициями $\{1,2\}$, переходами $\{1,2,3\}$, входными позициями переходов $\left(\varnothing, \{1\}, \{2\} \right)$, выходными позициями $\left( \{1\}, \{2\}, \varnothing \right)$ и строками $\{l, c, r\}$. У языка аналогичной сети с двумя переходами со строками $\{l, r\}$ есть очевидная грамматика $S \to \varepsilon, \; S \to l S r S$, строки этого языка — правильные скобочные последовательности. Пока никак не дойдёт, есть ли и какая КС-грамматика для языка указанной выше сети; первый блин $S \to \varepsilon, \; S \to l S c S r S$ вышел комом.

[Xaositect]

Посмотрите по ссылкам от этой статьи: https://www.google.ru/url?sa=t&rct=j&q= ... GE&cad=rjt (там немного другое определение - рассматриваются переходы из пустого состояния в любое, а не из пустого в пустое)

Касательно примера, то это язык не контекстно-свободный, доказать это можно, например, с помощью леммы о накачке для контекстно-свободных языков, аналогично стандартному примеру $\{0^n1^n2^n|n\in\mathbb{N}\}$.

[arseniiv]

Спасибо!