Применение сетей Петри для анализа КС-грамматик

Предложена схема использования сетей Петри для исследования некоторых свойств КС-грамматик. Метод позволяет, в частности, исследовать заданную КС-грамматику на пустоту и конечность порождаемого языка, используя дерево покрываемости соответствующей сети Петри. Кроме того, предложенный метод позволяет...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2011
Автор:	Спекторский, И.Я.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2011
Назва видання:	Системні дослідження та інформаційні технології
Теми:	Математичні методи, моделі, проблеми і технології дослідження складних систем
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/50134
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Применение сетей Петри для анализа КС-грамматик / И.Я. Спекторский // Систем. дослідж. та інформ. технології. — 2011. — № 4. — С. 129-133. — Бібліогр.: 6 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-50134
record_format	dspace
spelling	irk-123456789-501342013-10-06T03:06:43Z Применение сетей Петри для анализа КС-грамматик Спекторский, И.Я. Математичні методи, моделі, проблеми і технології дослідження складних систем Предложена схема использования сетей Петри для исследования некоторых свойств КС-грамматик. Метод позволяет, в частности, исследовать заданную КС-грамматику на пустоту и конечность порождаемого языка, используя дерево покрываемости соответствующей сети Петри. Кроме того, предложенный метод позволяет сформулировать необходимые условия порождения заданного слова КС-грамматикой в терминах матричного анализа соответствующей сети. Запропоновано схему використання мереж Петрі для дослідження деяких властивостей КВ-граматик. Метод дозволяє, зокрема, досліджувати задану КВ-граматику на порожність та скінченність породжуваної мови, використовуючи дерево покриття відповідної мережі Петрі. Крім того, запропонований метод дозволяє сформулювати необхідні умови породження заданого слова КВ-граматикою в термінах матричного аналізу відповідної мережі. The scheme of the use of Petri nets for the study of some properties of the CF-grammars is proposed. This method, enables, in particular, to investigate the emptiness and finiteness of language, generated by given CF-grammar, using tree cover of the relevant Petri net. Additionally, the proposed method allows to formulate the necessary conditions for the generation of a given word by CF-grammar in terms of a matrix analysis of the relevant network. 2011 Article Применение сетей Петри для анализа КС-грамматик / И.Я. Спекторский // Систем. дослідж. та інформ. технології. — 2011. — № 4. — С. 129-133. — Бібліогр.: 6 назв. — рос. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/50134 519.71 ru Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Математичні методи, моделі, проблеми і технології дослідження складних систем Математичні методи, моделі, проблеми і технології дослідження складних систем
spellingShingle	Математичні методи, моделі, проблеми і технології дослідження складних систем Математичні методи, моделі, проблеми і технології дослідження складних систем Спекторский, И.Я. Применение сетей Петри для анализа КС-грамматик Системні дослідження та інформаційні технології
description	Предложена схема использования сетей Петри для исследования некоторых свойств КС-грамматик. Метод позволяет, в частности, исследовать заданную КС-грамматику на пустоту и конечность порождаемого языка, используя дерево покрываемости соответствующей сети Петри. Кроме того, предложенный метод позволяет сформулировать необходимые условия порождения заданного слова КС-грамматикой в терминах матричного анализа соответствующей сети.
format	Article
author	Спекторский, И.Я.
author_facet	Спекторский, И.Я.
author_sort	Спекторский, И.Я.
title	Применение сетей Петри для анализа КС-грамматик
title_short	Применение сетей Петри для анализа КС-грамматик
title_full	Применение сетей Петри для анализа КС-грамматик
title_fullStr	Применение сетей Петри для анализа КС-грамматик
title_full_unstemmed	Применение сетей Петри для анализа КС-грамматик
title_sort	применение сетей петри для анализа кс-грамматик
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2011
topic_facet	Математичні методи, моделі, проблеми і технології дослідження складних систем
url	http://dspace.nbuv.gov.ua/handle/123456789/50134
citation_txt	Применение сетей Петри для анализа КС-грамматик / И.Я. Спекторский // Систем. дослідж. та інформ. технології. — 2011. — № 4. — С. 129-133. — Бібліогр.: 6 назв. — рос.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT spektorskijiâ primeneniesetejpetridlâanalizaksgrammatik
first_indexed	2025-07-04T11:37:25Z
last_indexed	2025-07-04T11:37:25Z
_version_	1836716178703122432
fulltext	© И.Я. Спекторский, 2011 Системні дослідження та інформаційні технології, 2011, № 4 129 УДК 519.71 ПРИМЕНЕНИЕ СЕТЕЙ ПЕТРИ ДЛЯ АНАЛИЗА КС-ГРАММАТИК И.Я. СПЕКТОРСКИЙ Предложена схема использования сетей Петри для исследования некоторых свойств КС-грамматик. Метод позволяет, в частности, исследовать заданную КС-грамматику на пустоту и конечность порождаемого языка, используя дере- во покрываемости соответствующей сети Петри. Кроме того, предложенный метод позволяет сформулировать необходимые условия порождения заданного слова КС-грамматикой в терминах матричного анализа соответствующей сети. ВВЕДЕНИЕ В работах [1–3] описан следующий метод представления формальных язы- ков с помощью порождающих сетей Петри: каждому переходу сети сопос- тавляется либо один из символов терминального алфавита, либо «пустой символ» λ , и каждая последовательность запусков переходов сети, заканчи- вающаяся в одной из выделенных «терминальных» маркировок, определяет слово порождаемого языка. В зависимости от множества терминальных маркировок и наличия λ -переходов определяют более десяти различных классов языков, порождаемых сетями Петри [1], которые не вписываются в классическую иерархию Хомского — строго включают класс регулярных языков, строго вложены в класс контекстно-зависимых языков, и несравни- мы с классом контекстно-свободных языков [4–6]. Метод анализа, предложенный в данной работе, не предполагает пол- ного описания языка сетью Петри, и поэтому, в частности, не дает критерия порождаемости данного слова заданной формальной грамматикой, но позволяет с помощью сети Петри контролировать количество вхождений каждой буквы терминального алфавита в порождаемое слово и, как следст- вие, исследовать порождаемый язык на пустоту и конечность. ОПРЕДЕЛЕНИЕ СЕТИ ПЕТРИ ДЛЯ ЗАДАННОЙ КС-ГРАММАТИКИ Пусть >Σ=< SPNG ,,, — контекстно-свободная порождающая грамматика (КС-грамматика), где N — нетерминальный алфавит, Σ — терминальный алфавит, P — множество продукций, NS∈ — источник. Для грамматики G введем в рассмотрение сеть Петри GN с множеством позиций Σ∪N , множеством переходов P и весовой функцией ,W определяемой для про- дукции β→A , а также символа Σ∈ξ соотношениями: ξβξβ \|\|),( =→AW (количество вхождений ξ в β ), ⎩ ⎨ ⎧ ≠ = =→ . если,0 , если,1 ),( A A AW ξ ξ βξ И.Я. Спекторский ISSN 1681–6048 System Research & Information Technologies, 2011, № 4 130 Пример 1. Рассмотрим формальную грамматику >=< SPcbaASG ,},,,{},,{ , где множе- ство продукций }\|,\|{ εcAAAaSabSP →→= . Сеть Петри, соответствующая грамматике G , изображена на рис. 1. Легко увидеть, что данная грамматика порождает язык :)({ nmn abca 0≥n , }0≥m , причем каждое слово nmn abca )( порождается последователь- ностью применений продукций (запусков переходов) →→ SaSabS n ()( )())( ε→→→ AcAAA m , что приводит к маркировке ),,,0,0( mnn (предпо- лагая порядок позиций в соответствии с перечислением в определении грамматики, т.е. cbaAS ,,,, ). АНАЛИЗ С ПОМОЩЬЮ ДЕРЕВА ПОКРЫВАЕМОСТИ Ряд свойств сети Петри GN при фиксированной начальной маркировке ( },,,2,1{ …… n= — множество натуральных чисел) эффективно анализи- руются с помощью дерева покрываемости [1, 2]. Символ NA∈ называют порождающим, если * wA⇒ для некоторого Σ∈w . Очевидно, что все продукции, содержащие непорождающие симво- лы, можно исключить из P , не сужая язык, порождаемый грамматикой. Продукцию β→A называют рекурсивной, если β содержит A . Очевидно, что исключение рекурсивных продукций не влияет на порождаемость или непорождаемость нетерминальных символов. Через Aµ ( NA∈ ) обозначим такую маркировку, что ⎩ ⎨ ⎧ Σ∪∈ = = }.{\)( если,0 , если,1 AN A A ξ ξ µ Через AT обозначим дерево покрываемости для начальной маркировки Aµ . Через nr AT обозначим дерево покрываемости для начальной маркировки Aµ , построенное без учета переходов, соответствующих рекурсивным про- дукциям. Справедливость следующих двух теорем устанавливается непосредст- венно из построения сети Петри по заданной КС-грамматике. aSabS → AS → ε→A cAA → S a b c A 2 Рис. 1. Сеть Петри для грамматики с продукциями ε\|,\| cAAAaSabS →→ Применение сетей Петри для анализа КС-грамматик Системні дослідження та інформаційні технології, 2011, № 4 131 Теорема 1. Символ NA∈ является порождающим тогда и только тог- да, когда дерево nr AT содержит не менее одной маркировки µ , такой, что 0)( =ξµ для всех N∈ξ . Следствие. Язык, порождаемый грамматикой G , является непустым тогда и только тогда, когда дерево nr ST содержит не менее одной маркиров- ки µ такой, что 0)( =ξµ для всех N∈ξ (т.е., когда порождающим является источник S ). Теорема 2. Грамматика G порождает бесконечный язык тогда и только тогда, когда дерево ST содержит не менее одной маркировки µ , такой, что 0)( =ξµ для всех N∈ξ , и ωµ =)(a для некоторого Σ∈a . Пример 2. Рассмотрим формальную грамматику },,,{},,{ cbaASG =< >SP, , где множество продукций }\|,\|{ εcAcAaSabSP →→= . Сеть Петри, соответствующая грамматике G , изображена на рис. 2. Для анализа порождаемого языка на пустоту и конечность построим дерево nr ST (рис. 3) и дерево ST (рис. 4). При по- строении дерева nr ST , в соответствии с определением, была исключена рекур- сивная продукция aSabS → . Порядок позиций при записи маркировок предпо- лагался в соответствии с перечислением в определении грамматики, т.е. ,, AS cba ,, . Поскольку nr ST содержит маркировки µ , удовлетворяющие условию 0)( =ξµ для всех },{ AS∈ξ (например, маркировку (0, 0, 0, 0, 2)), заданная грамматика порождает непустой язык. Далее, дерево ST содержит марки- ровки µ , удовлетворяющие условию 0)( =ξµ для всех },{ AS∈ξ и содер- жащие символ ω (маркировки )1,,,0,0( ωω и ))2,,,0,0( ωω , откуда следует a b aSabS → AS → ε→A c A cA → 2 S Рис. 2. Сеть Петри для грамматики с продукциями ε\|,\| cAcAaSabS →→ (1,0,0,0,0) (0,1,0,0,1) cAS → (0,0,0,0,2) (0,0,0,0,1) cA → ε→A Рис. 3. Дерево nr ST для граммати- ки с продукциями ,\| cAaSabS → ε\|cA→ И.Я. Спекторский ISSN 1681–6048 System Research & Information Technologies, 2011, № 4 132 бесконечность языка, порождаемого данной грамматикой. Более того, поскольку символ ω находится на позициях, соответствующих символам a и b , можем сделать вывод, что порождаемый язык содержит слова со сколь угодно большим числом вхождений a и b (но не c ). АНАЛИЗ С ПОМОЩЬЮ УРАВНЕНИЯ СОСТОЯНИЯ Для анализа порождаемости грамматикой G слова Σ∈w можно использо- вать уравнение состояний сети GN [1, 2]. Обозначим через wµ )( Σ∈w маркировку такую, что ξξµ \|\|)( ww = . Очевидно, что для порождаемости слова w необходимо (но недостаточно), чтобы уравнение состояния имело хотя бы одно решение для правой части Sw µµµ −=∆ . Пример 3. Рассмотрим грамматику >→=< }\|\|{},,{},{ εbSaaSbSbaSG . Соответст- вующая сеть Петри GN изображена на рис. 5. Выпишем матрицу инцидентности для GN , предполагая упорядочен- ность позиций (нетерминальных и терминальных символов) и переходов (продукций) в соответствии с перечислением в определении грамматики: ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ − = 001 110 110 A . Уравнение состояния µ∆=uAT имеет решение относительно вектора запусков )( 321 ,u,uuu = лишь для правых частей вида ),,( yyx=∆µ . Таким образом, из начальной маркировки )0,0,1(=Sµ могут достигаться только маркировки с одинаковыми второй и третьей координатами. Это означает, что грамматика G может генерировать лишь слова с одинаковым числом вхождений a и b . Однако разрешимость уравнения состояния — лишь не- (1,0,0,0,0) (0,1,0,0,1) aSabS → (0,0,0,0,2) (0,0,0,0,1) cA → ε→A (1,0,ω,ω,0) cAS → (0,1,ω,ω,1) (1,0,ω,ω,0) Дубль cAS → aSabS → (0,0,ω,ω,2) (0,0,ω,ω,1) cA → ε→A Рис. 4. Дерево ST для грамматики с продукциями ε\|,\| cAcAaSabS →→ Применение сетей Петри для анализа КС-грамматик Системні дослідження та інформаційні технології, 2011, № 4 133 обходимое условие для порождаемости слова грамматикой; в данном при- мере G порождает лишь слова вида rww , т.е. палиндромы четной длины. ВЫВОДЫ Предложенный метод анализа КС-грамматик с помощью сетей Петри по- зволяет исследовать свойства, связанные с количеством вхождений того или иного символа терминального алфавита в слова, порождаемые данной грамматикой. В частности, с помощью сетей Петри удобно анализировать порождаемый язык на пустоту и конечность. Используя дерево покрываемости, можно не только выявить факт бес- конечности порождаемого языка, но и определить, какие именно символы могут встречаться в порождаемых словах в сколь угодно большом количестве. Анализируя уравнение состояния сети на разрешимость, можно полу- чить необходимые условия порождаемости слов, т.е. «оценить сверху» множество слов, которые могут порождаться данной грамматикой. К достоинствам рассмотренного метода можно отнести простоту и на- глядность. Недостаток метода, ограничивающий его применение, связан с невозможностью отслеживать порядок букв в порождаемом слове. Направлением для дальнейших исследований предполагается обобще- ние рассмотренного метода на более широкий класс формальных грамма- тик. Кроме того, используя различные расширения сетей Петри, можно по- пытаться модифицировать метод с тем, чтобы получить контроль над расположением символов в словах, порождаемых данной грамматикой. ЛИТЕРАТУРА 1. Питерсон Дж. Теория сетей Петри и моделирование систем. — М.: Мир, 1984. — 264 с. 2. Котов В.Е. Сети Петри. — М.: Наука, 1984. — 160 с. 3. Алгоритмічні алгебри: навч. посіб. — Київ: ІЗМН, 1997. — 480 с. 4. Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс. — М.: Радио и связь, 1988. — 128 с. 5. Гросс М., Лантен А. Теория формальных грамматик. — М.: Мир, 1971. — 296 с. 6. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. У 2 т. Т. 1. — М.: Мир, 1978. — 614 с. Поступила 24.06.2010 b ε→S SaSbS → bSaS → a Рис. 5. Сеть Петри для грамматики с продукциями ε\|\| bSaaSbS →

Применение сетей Петри для анализа КС-грамматик

Репозитарії

Схожі ресурси