Языки, порождаемые сетью

Метки переходов из используются для синхронизации переходов в системной и в элементных сетях, за счет чего достигается взаимодействие различных слоев рекурсивной сети.

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

Определение 9. Пусть A — некоторый конечный алфавит. Назовем RNP-сеть помеченной, если некоторые переходы в сетях N₁, …, N_k помечены символами из A.

Каждый автономный шаг M₁M₂ помеченной сети порождает символ из A, которым помечен сработавший переход, или пустой символ, если данный переход непомечен. Будем считать, что синхронный шаг может сработать, только если все составляющие его переходы помечены одним и тем же символом из A (или все непомечены). Таким образом, любое исполнение M₀M₁M₂… порождает некоторое слово из A*.

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

Напомним классическое определение контекстно-свободных языков:

Формальная порождающая грамматика G — это формальная система, определяемая четверкой объектов G=V, W, S, R, где V — алфавит терминальных (основных) символов; W — алфавит нетерминальных (вспомогательных) символов; VW=; R — конечное множество правил вывода вида, где и — цепочки в алфавите VW; S — начальный символ (аксиома грамматики).

Языком L (G), порождаемым грамматикой G, называется множество всех цепочек в терминальном алфавите V, выводимых из S в соответствие с правилами R.

Грамматика называется контекстно-свободной (КС-грамматикой), если все ее правила вывода имеют вид A, где AW, (VW)*.