Применение сетей Петри для анализа КС-грамматик
Предложена схема использования сетей Петри для исследования некоторых свойств КС-грамматик. Метод позволяет, в частности, исследовать заданную КС-грамматику на пустоту и конечность порождаемого языка, используя дерево покрываемости соответствующей сети Петри. Кроме того, предложенный метод позволяет...
Збережено в:
| Опубліковано в: : | Системні дослідження та інформаційні технології |
|---|---|
| Дата: | 2011 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.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| _version_ | 1859668140269502464 |
|---|---|
| author | Спекторский, И.Я. |
| author_facet | Спекторский, И.Я. |
| citation_txt | Применение сетей Петри для анализа КС-грамматик / И.Я. Спекторский // Систем. дослідж. та інформ. технології. — 2011. — № 4. — С. 129-133. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| container_title | Системні дослідження та інформаційні технології |
| description | Предложена схема использования сетей Петри для исследования некоторых свойств КС-грамматик. Метод позволяет, в частности, исследовать заданную КС-грамматику на пустоту и конечность порождаемого языка, используя дерево покрываемости соответствующей сети Петри. Кроме того, предложенный метод позволяет сформулировать необходимые условия порождения заданного слова КС-грамматикой в терминах матричного анализа соответствующей сети.
Запропоновано схему використання мереж Петрі для дослідження деяких властивостей КВ-граматик. Метод дозволяє, зокрема, досліджувати задану КВ-граматику на порожність та скінченність породжуваної мови, використовуючи дерево покриття відповідної мережі Петрі. Крім того, запропонований метод дозволяє сформулювати необхідні умови породження заданого слова КВ-граматикою в термінах матричного аналізу відповідної мережі.
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.
|
| first_indexed | 2025-11-30T11:58:12Z |
| format | Article |
| 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 →
|
| id | nasplib_isofts_kiev_ua-123456789-50134 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1681–6048 |
| language | Russian |
| last_indexed | 2025-11-30T11:58:12Z |
| publishDate | 2011 |
| publisher | Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| record_format | dspace |
| spelling | Спекторский, И.Я. 2013-10-05T20:22:45Z 2013-10-05T20:22:45Z 2011 Применение сетей Петри для анализа КС-грамматик / И.Я. Спекторский // Систем. дослідж. та інформ. технології. — 2011. — № 4. — С. 129-133. — Бібліогр.: 6 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/50134 519.71 Предложена схема использования сетей Петри для исследования некоторых свойств КС-грамматик. Метод позволяет, в частности, исследовать заданную КС-грамматику на пустоту и конечность порождаемого языка, используя дерево покрываемости соответствующей сети Петри. Кроме того, предложенный метод позволяет сформулировать необходимые условия порождения заданного слова КС-грамматикой в терминах матричного анализа соответствующей сети. Запропоновано схему використання мереж Петрі для дослідження деяких властивостей КВ-граматик. Метод дозволяє, зокрема, досліджувати задану КВ-граматику на порожність та скінченність породжуваної мови, використовуючи дерево покриття відповідної мережі Петрі. Крім того, запропонований метод дозволяє сформулювати необхідні умови породження заданого слова КВ-граматикою в термінах матричного аналізу відповідної мережі. 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. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Математичні методи, моделі, проблеми і технології дослідження складних систем Применение сетей Петри для анализа КС-грамматик Застосування мереж Петрі для аналізу КВ-граматик Application of Petri nets for the analysis of CF-grammars Article published earlier |
| spellingShingle | Применение сетей Петри для анализа КС-грамматик Спекторский, И.Я. Математичні методи, моделі, проблеми і технології дослідження складних систем |
| title | Применение сетей Петри для анализа КС-грамматик |
| title_alt | Застосування мереж Петрі для аналізу КВ-граматик Application of Petri nets for the analysis of CF-grammars |
| title_full | Применение сетей Петри для анализа КС-грамматик |
| title_fullStr | Применение сетей Петри для анализа КС-грамматик |
| title_full_unstemmed | Применение сетей Петри для анализа КС-грамматик |
| title_short | Применение сетей Петри для анализа КС-грамматик |
| title_sort | применение сетей петри для анализа кс-грамматик |
| topic | Математичні методи, моделі, проблеми і технології дослідження складних систем |
| topic_facet | Математичні методи, моделі, проблеми і технології дослідження складних систем |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/50134 |
| work_keys_str_mv | AT spektorskiiiâ primenenieseteipetridlâanalizaksgrammatik AT spektorskiiiâ zastosuvannâmerežpetrídlâanalízukvgramatik AT spektorskiiiâ applicationofpetrinetsfortheanalysisofcfgrammars |