2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Сети Петри и языки
Сообщение11.05.2013, 23:43 
Пусть дана сеть Петри, в которой каждому переходу $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$ вышел комом.

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

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

 
 
 
 Re: Сети Петри и языки
Сообщение12.05.2013, 13:59 
Спасибо!

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group