Вопрос 26. Свободный, префиксный и терминальный языки сети Петри. Теорема о мощности классов языков сети Петри.
Свободный Язык СП : S –это множество последовательностей срабатывания ? переходов сети S
L(S )={ ? ? T* ?? M(l)? R(S): M(0)->M(l)}
Помеченная сеть S^ : (тройка) =<S,A,?>
S- непомеченная сеть петри А – помечающий алфавит ? — помечающее отображение , которое …….
знаки помечающего алфавита и переходв .? :Т?А
Префиксный язык СП – если L(S) – свободный язык СП то L(S^) из всевозможных помечающих последовательностей L(S^) ={?(?)? ? ?L(s)} – префиксный язык СП .
Терминальный язык СП – множество помечающих последовательностей таких , что изначальная маркировка М (0) сеть переходит в маркировки М(f).
Lt (S^, M(f))={ ?(?) ? M(0) ?M(f)}
Теорема(о мощности класса языков СП)
Класс языков –всевозможные языки которые могут быть представлены в рамках рассматриваемой формальной системы
L3- класс языков представляющий регулярные грамм.
L2- класс языков представляющий КС-грамм.
L1- класс языков представляющий Контекстные грамм.
L0- класс языков представляющий произвольн. Граам.
LT – класс языков порожд. СП при всевозможных начальн и заключит. (терминальных) маркировках.
Класс терминальных языков СП :
а) строго меньше , чем класс языков порожд. регулярными грамм.
б) несравним с классом языков порожд. КС-грамм.
в)менее мощен чем класс языков порожд. L0 => универсальное множество L3? L T? L2? L0
Доказательство :
А) регулярный язык может быть представлен в виде помеченной СП следующим образом :
каждому нетерминальному знаку сопоставим …..
в каждой продукции Ai->aAj сопоставим дугу с переходом а?V идущую от PAi к PAj , в качестве заключительной маркировки М(f) выбираем следующую маркировку длинной (n+1) , где n – число нетерминальных знаков , а дополнительные позиции Р соответствуют заключительной сентенциальной форме , когда из строки вывода удаляется единственный нетерминальный знак .
Начальной маркировкой является маркировка М(0)=(,0,0,0…..1, ..,0) где МI=1
Пусть задана грамматика G3 P2(I -> a! AB! BA B-> b! bA A-> a!aB ) V={a,b} W={I,A,B} P={PI,PA,PB,P0}
M0=(1,0,0,0)
Б) Однако существуют сети которые порождают в качестветерминального языка нерегулярный язык .
t1 !-> O->! t2 M0=ML=(0)
[ ] G2 V={[,]} W={I} P={I-> I I ! [I] ! e }
Вывод : язык порождаемый этой СП не может быть представлен регулярной грамматикой
В) LT (класс терминальных языков порождаемый всевозможными СП) – несравним с классом КС- языков те не все КС- языки могут быть представлены СП , а также есть языки (терминальные ) представляемые СП , которые не могут быть порождены СП
Пример КС – языка который порождается СП { a^nb^nc^n ! n>=1} М0=(1,0,0,0,0,0) МL=(0,0,0,0,0,1)
Не может быть реализован КС грамматикой
Однако есть КС язык который не может быть порожден СП {a^n b^n c ! n>= 1 }
P={ I-> Ac A -> aAb!e }
Докажем от противного :
Пусть есть СП L (S^ , ML)=L2
тогда такая сеть должна порождать счетное множество последовательностей срабатывания
зафиксируем некоторую последовательность срабатываний переходов и соответствующую ей последовательность разметок (маркировок )
Если есть две маркировки Мк и МL причем Мк <= ML то терминальный язык порождаемый из Мк будет включен в терминальный язык порождаемый из второй маркировки LkT? LlT
Пусть имеется некоторая последовательность срабатывания ? исходной сети и две маркировки Mi<= Mj
Рассмотрим строку a^ib^ic которая принадлежит языку L2 при достижении разметки Mi порождается
Префикс этой строки а при достижении разметки Mj порождается префикс этой строки a ^i
Пусть сеть S^ ‘ отличается от сети S^ лишь начальной маркировкой Mi а S^’’ отличается от S^ новой начальной маркировкой Mj
Терминальный язык сети S^ ‘ LT (S^ ‘ , Mi ) содержит строки b^ic a LT (S^’’ , Mj ) ………..
В силу монотонности языков (3)
Mi< M j => LT (S^ ‘ , Mi ) ? LT (S^’’ , Mj ) => строка a^jb^ic содержится в терминальном языке сети S^ , что протеворечит о существовани сети порождающей a^nb^nc
Свободный, префиксный и терминальный языки сети Петри. Теорема о мощности классов языков сети Петри.
25 Фев, 2009