Зв’язок мереж Петрі з бездужковим польським записом
We propose Petri nets that produce languages of Polish notation and reverse Polish notation for propositional formulas and mathematical expressions. Propositional formulas can contain a given number of variables and mathematical expressions. Arithmetic expressions can contain a given number of varia...
Збережено в:
| Дата: | 2016 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2016
|
| Теми: | |
| Онлайн доступ: | https://journal.iasa.kpi.ua/article/view/59334 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Репозитарії
System research and information technologies| _version_ | 1867334257840488448 |
|---|---|
| author | Statkevich, Vitaly M. |
| author_facet | Statkevich, Vitaly M. |
| author_institution_txt_mv | [
{
"author": "Vitaly M. Statkevich",
"institution": "Відділ прикладного нелінійного аналізу ННК \"Інститут прикладного системного аналізу\" НТУУ \"КПІ\", Київ"
}
] |
| author_sort | Statkevich, Vitaly M. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2018-03-30T15:27:05Z |
| description | We propose Petri nets that produce languages of Polish notation and reverse Polish notation for propositional formulas and mathematical expressions. Propositional formulas can contain a given number of variables and mathematical expressions. Arithmetic expressions can contain a given number of variables and constants. We also propose inhibitor nets that produce the fixed-point binary numbers in mathematical expressions for above-mentioned languages. The technique of the nets construction allows to use arbitrary functions with a given arity. We also propose a coloured Petri net for calculating values of propositional formulas in reverse Polish notation. The technique of the net construction allows to use arbitrary functions with a given arity using a truth table of a corresponding function. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2016.2.01 |
| first_indexed | 2025-07-17T10:19:50Z |
| format | Article |
| fulltext |
© В.М. Статкевич, 2016
Системні дослідження та інформаційні технології, 2016, № 2 7
TIДC
ПРОГРЕСИВНІ ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ,
ВИСОКОПРОДУКТИВНІ КОМП’ЮТЕРНІ
СИСТЕМИ
УДК 519.711.7+519.6
DOI: 10.20535/SRIT.2308-8893.2016.2.01
СВЯЗЬ СЕТЕЙ ПЕТРИ
С БЕССКОБОЧНОЙ ПОЛЬСКОЙ ЗАПИСЬЮ
В.М. СТАТКЕВИЧ
Рассмотрены сети Петри, которые порождают языки бесскобочной польской
записи и обратной польской записи для пропозициональных формул и ариф-
метических выражений. Пропозициональные формулы могут содержать за-
данное количество переменных, а арифметические выражения — переменных
и констант. Предложены также ингибиторные сети Петри для указанных язы-
ков, позволяющие формировать вещественные числа в двоичной записи
с фиксированной точкой в арифметических выражениях. Метод построения
сетей позволяет использовать произвольные функции заданной арности. Пред-
ложена цветная сеть Петри для вычисления значений пропозициональных
формул в обратной польской записи. Метод построения сети позволяет ис-
пользовать произвольные функции заданной арности с применением таблицы
истинности соответствующей функции.
ВВЕДЕНИЕ
Сети Петри были предложены К. Петри в 1962 г. и являются удобным сред-
ством для моделирования различных процессов, систем и сетей (см., напри-
мер, [1, 2]). Следует отметить такие их важные свойства, как недетермини-
рованность, асинхронность, параллелизм и конфликтность.
Каждая сеть Петри может порождать язык. В работе [1] определены
12 классов языков и исследована их связь с формальными языками, опреде-
ляемыми иерархией Хомского (см., например, [3]).
Сети Петри имеют определённую связь с вычислениями. В работе [1,
с. 147] предлагалось в качестве упражнения исследовать связь с арифмети-
кой Пресбюргера. Однако моделировать машину Тьюринга сети Петри не
могут, так как невозможно проконтролировать отсутствие фишки в позиции.
Доказано (см. [2, §5.2]), что ингибиторные сети (сети, имеющие ингибитор-
ные дуги, позволяющие проверять отсутствие фишек в позиции) и сети
с приоритетами (обобщение сетей Петри) равномощны классу машин Тью-
ринга, а в [4] построена ингибиторная сеть, исполняющая произвольно за-
данную машину Тьюринга. В работе [5] детально исследована связь сетей
Петри с исчислением процессов (алгеброй процессов).
Цветные сети Петри [2, 6] — обобщение сетей Петри, когда фишкам
могут быть сопоставлены признаки (например, цвета) из заданного множе-
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2016, № 2 8
ства признаков, а правила запуска переходов модифицируются с учётом
признаков фишек, — в случае бесконечного множества признаков равно-
мощны классу машин Тьюринга. В случае конечного множества признаков
цветной сети соответствует сеть Петри, возможно большего размера
(см. [2, §5.3]).
В статье [7] сети Петри применяются для анализа контекстно-
свободных грамматик.
Отметим также подход к определению класса языков, предложенный
в работе [8].
В этой работе предлагаются сети Петри, которые порождают языки
бесскобочной польской записи, а также обратной польской записи для про-
позициональных формул и арифметических выражений. Эта запись, пред-
ложенная Я. Лукасевичем (см., например, [3, c. 244–245]), имеет широкое
применение в синтаксическом анализе и программировании, в частности,
с 1960-х годов разрабатывались компьютеры и калькуляторы, поддержи-
вающие обратную польскую запись. Также в данной работе предлагается
цветная сеть Петри, позволяющая вычислять значения пропозициональных
формул.
ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ
Сетью Петри называют набор 0,,, μWTP , где P — множество позиций
(конечное и непустое); T — множество переходов (конечное и непустое),
}0{)()(: ∪→×∪× NPTTPW — весовая функция; }0{:0 ∪→μ NP — на-
чальная маркировка. Сеть Петри представляется в виде двудольного ориен-
тированного мультиграфа, множество вершин которого разбивается на два
непересекающихся подмножества P и T (доли), а дуги направлены от по-
зиций к переходам или от переходов к позициям [1, 2].
Пусть A — конечное множество символов (алфавит), *A — множество
слов, т.е. конечных цепочек символов из A . Пустой символ обозначают
какλ и полагают, что A∉λ . Формальным языком L над алфавитом A на-
зывают некоторое подмножество множества ** : ALA ⊂ [3].
Сопоставим каждому переходу некоторый символ алфавита A или
пустой символ λ , }{: λ∪→δ AT — функция помечения. Свободно поме-
ченной сетью Петри называют сеть, в которой все переходы помечены раз-
личными символами алфавита A . Различают свободные языки сети Петри,
без λ -переходов и с λ -переходами. Последовательности KK ,,,1 ntt=σ за-
пусков переходов сети отвечает слово *),(,),()( 1 Attw n ∈δδ=σ KK (перехо-
ды, помеченные символом λ , не учитываются). Пусть задано множество
заключительных маркировок F . Языком сети Петри L -типа называют
множество слов w таких, что после запуска соответствующей последова-
тельности переходов σ текущая маркировка является заключительной.
Языком сети Петри T -типа называют множество слов w таких, что после
запуска последовательности переходов σ ни один переход невозможно за-
пустить [1, 2].
Связь сетей Петри с бесскобочной польской записью
Системні дослідження та інформаційні технології, 2016, № 2 9
Ингибиторной сетью Петри называют сеть Петри, содержащую, кроме
обычных дуг, ещё и ингибиторные дуги. Последние направлены лишь от
позиций к переходам, всегда имеют кратность 1 и на рисунке обозначаются
заканчивающимися не стрелками, а окружностями. Соответствующий пере-
ход можно запустить тогда, когда выполнены обычные условия запуска пе-
рехода, а также во всех входных позициях, соединённых с ним ингибитор-
ными дугами, отсутствуют фишки [2].
Пропозициональные формулы определяются следующим образом:
1) пропозициональная буква является формулой; 2) если A и B — форму-
лы, то )( BA∨ , )( BA∧ , A¬ — также формулы; 3) других формул нет.
Бесскобочной польской записью выражения (согласно иной термино-
логии – префиксной формой записи) называют запись, в которой символ
операции предшествует операндам, обратной польской записью (или пост-
фиксной формой записи) – запись, в которой операнды предшествуют сим-
волу операции ([3, с. 244–245]). Например, обычной инфиксной форме запи-
си выражения )14()3*2( −+ соответствует польская запись 1432* −+
и обратная польская запись +−14*32 .
СЕТИ ПЕТРИ ДЛЯ БЕССКОБОЧНОЙ ПОЛЬСКОЙ ЗАПИСИ
Рассмотрим свободно помеченные сети Петри на рис. 1. Данные сети поро-
ждают языки L -типа с заключительной маркировкой )0(=μ f , соответст-
вующие польской записи пропозициональных формул и арифметических
выражений. Здесь nxx ,,1 K — переменные, mcc ,,1 K — константы, «+», «–»,
«*», «/» — бинарные операции, « u− » — унарный минус. При добавлении
в выражение дополнительной k-арной функции (например, стрелки Пирса,
штриха Шеффера, тригонометрической, степенной, логарифмической и т.д.)
следует дополнить сеть ещё одним переходом t̂ , помеченным соответст-
вующим символом, и дугами tp ˆ1 − , 1ˆ pt − с весами 1)ˆ,( 1 =tpW ,
kptW =),ˆ( 1 . Графы достижимости для данных сетей бесконечны.
После формирования сетями слова w переменные и константы можно
в дальнейшем (уже не с помощью данных сетей) интерпретировать, задавая
конкретные логические или числовые значения. Также на этапе интерпрета-
Рис. 1. Сети Петри для бесскобочной польской записи: а — пропозициональных
формул; б — арифметических выражений
а б
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2016, № 2 10
ции для сети на рис. 1, б можно проверить корректность полученного ариф-
метического выражения: отсутствие деления на ноль, принадлежность аргу-
ментов функций типа tg , ctg , ln их областям определения и т.д.
Сеть на рис. 1, б можно усовершенствовать, позволив формировать
константы. Ингибиторная сеть на рис. 2 (в предположении, что
)0,0,0,0,0,0,0(=μ f ) позволяет формировать вещественные числа в двоич-
ной записи с фиксированной точкой. В момент начала формирования конс-
танты в позиции 2p появляется фишка-флаг, запрещая запуск переходов,
отвечающих за переменные и операции. После формирования константы
фишка из позиции 2p исчезает, разрешая запуск указанных переходов.
Здесь « n− » указывает на то, что константа отрицательна.
Для сетей на рис. 1–2 указанные языки L -типа совпадают с языками
T -типа.
СЕТИ ПЕТРИ ДЛЯ ОБРАТНОЙ
ПОЛЬСКОЙ ЗАПИСИ
Рассмотрим сети Петри с λ -переходом на
рис. 3. Данные сети порождают языки L -
типа с заключительной маркировкой
)1,0,0,0(=μ f , соответствующие обратной
польской записи пропозициональных
формул и арифметических выражений.
При добавлении в выражение дополни-
тельной k -арной ( 2≥k ) функции следует
дополнить сеть ещё одним переходом t̂ ,
помеченным соответствующим символом,
и дугами tp ˆ3 − , tp ˆ2 − , 2ˆ pt − с весами
1)ˆ,( 3 −= ktpW , 1),ˆ()ˆ,( 22 == ptWtpW ,
а при добавлении унарной функции – ду-
гами tp ˆ2 − , 2ˆ pt − с весами =)ˆ,( 2 tpW
1),ˆ( 2 == ptW .
Сеть на рис. 3, б также можно усо-
вершенствовать (рис. 4), добавив блоки
формирования вещественных чисел
с фиксированной точкой подобно тому,
как изображено на рис. 2, и положив
)1,0,0,0,0,0,0,0,0,0,0,0,0,0,0(=μ f .
Отметим, что для сетей на рис. 3 в от-
личие от сетей на рис. 1 и 2 языки T -типа
не совпадают с указанными языками L -
типа из-за наличия тупиков )1,,0,0( l ,
N∈l . Однако от этих тупиков можно из-
бавиться, проведя ингибиторную дугу от
Рис. 2. Ингибиторная сеть Петри
для бесскобочной польской запи-
си арифметических выражений
Связь сетей Петри с бесскобочной польской записью
Системні дослідження та інформаційні технології, 2016, № 2 11
позиции 3p к λ -переходу, что сделает языки T -типа равными языкам
L -типа (для сети на рис. 4 подобная ингибиторная дуга присутствует).
При отсутствии переменных или при выборе конкретной интерпрета-
ции сеть на рис. 3, а можно усовершенствовать, позволив вычислять зна-
Рис. 3. Сети Петри для обратной польской записи: а — пропозициональных фор-
мул; б — арифметических выражений
а б
Рис. 4. Ингибиторная сеть Петри для обратной польской записи арифметических
выражений
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2016, № 2 12
чения пропозициональных формул. Цветная сеть на рис. 5 и рис. 6 воспро-
изводит известный алгоритм вычисления значения выражения, записанного
обратной польской записью. Множество признаков — }1{\N , порядок сра-
батывания переходов соответствует обратной польской записи пропозицио-
нальной формулы.
Позиции 531, ppp − могут содержать только простые фишки, обозна-
чаемые α . Значение выражения равно 0, если фишка содержится в пози-
ции 4p , и равно 1, если фишка содержится в позиции 5p . Позиция 2p
может содержать только цветные фишки, обозначаемые nα , где n вычис-
ляется следующим образом. Старший бит числа n всегда равен единице, а
остальные биты формируют стек значений, вершина которого находится в
младшем бите; фактически единица в старшем бите является аналогом
начального символа 0Z (маркера дна стека) в МП-автомате (см., на-
пример, [3, с. 193–194]).
Рис. 5. Цветная сеть Петри для вычисления значений пропозициональных формул
1p 2p
1t α 10α
2t α 11α
2p 2p
0xα 1xα
3t
1xα 0xα
2p 2p 3p
4t xα 0xα α
5t xα 1xα α
2p 3p 2p
00xα α 0xα
01xα α 0xα
10xα α 0xα6t
11xα α 1xα
00xα α 0xα
01xα α 1xα
10xα α 1xα7t
11xα α 1xα
2p 4p
8t 10α α
2p 5p
9t 11α α
Рис. 6. Условия запуска переходов для цветной сети на рис. 5
Связь сетей Петри с бесскобочной польской записью
Системні дослідження та інформаційні технології, 2016, № 2 13
Переходы 1t , 2t , 4t и 5t отвечают за запись констант 0 и 1 в стек, пере-
ходы 3t , 6t и 7t — за выполнение операций логического отрицания, конъ-
юнкции и дизъюнкции соответственно, переходы 8t и 9t — за получение
результата. Условия запуска переходов указаны на рис. 6 (под x подразуме-
ваются старшие биты двоичной записи числа n ).
При добавлении в пропозициональную формулу дополнительной k -
арной ( 2≥k ) функции следует дополнить сеть ещё одним переходом t̂ , по-
меченным соответствующим символом, и дугами tp ˆ3 − , tp ˆ2 − , 2ˆ pt − .
Также необходимо указать условия запуска перехода t̂ , которые строятся на
основании таблицы истинности соответствующей функции.
Таким образом, предложенная цветная сеть позволяет вычислять зна-
чение пропозициональной формулы при условии, что порядок срабатывания
переходов соответствует обратной польской записи данной формулы.
ЛИТЕРАТУРА
1. Питерсон Дж. Теория сетей Петри и моделирование систем / Дж. Питерсон;
пер. с англ. — М.: Мир, 1984. — 264 с.
2. Котов В.Е. Сети Петри / В.Е. Котов. — М.: Наука. Гл. ред. физико-мат. лит-ры,
1984. — 160 с.
3. Ахо А. Теория синтаксического анализа, перевода и компиляции. Т. 1.
Синтаксический анализ / А. Ахо, Дж. Ульман: пер. с англ. — М.: Мир,
1978. — 613 с.
4. Зайцев Д.А. Ингибиторная сеть Петри, исполняющая произвольно заданную
машину Тьюринга / Д.А. Зайцев // Системні дослідження та інформаційні
технології. — 2012. — № 2. — С. 26–41.
5. Best E. Petri net algebra / E. Best, R. Devillers, M. Koutny. — Berlin: Springer-
Verlag, 2001. — 380 p.
6. Jensen K. Coloured Petri Nets: Modelling and Validation of Concurrent Systems,
Springer-Verlag / K. Jensen, L. Kristensen. — Berlin, 2009. — 384 p.
7. Спекторский И.Я. Применение сетей Петри для анализа КС-грамматик /
И.Я. Спекторский // Системні дослідження та інформаційні технології. —
2011. — № 4. — С. 129–133.
8. Jantzen M. Labeled Step Sequences in Petri Nets, Applications and Theory of Petri
Nets / M. Jantzen, G., Zetzsche // 29th International Conference, Xi'an, China
(June 23–27, 2008). — Proceedings. — P. 270–287.
Поступила 01.02.2016
|
| id | journaliasakpiua-article-59334 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:19:50Z |
| publishDate | 2016 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/41/c7a1078432c7d0919db743cccaea0d41.pdf |
| spelling | journaliasakpiua-article-593342018-03-30T15:27:05Z Connection between Petri nets and Polish notation Связь сетей Петри с бесскособочной польской записью Зв’язок мереж Петрі з бездужковим польським записом Statkevich, Vitaly M. Petri net inhibitor Petri net coloured Petri net Petri net language Polish notation reverse Polish notation сеть Петри ингибиторная сеть Петри цветная сеть Петри язык сети Петри бесскобочная польская запись обратная польская запись мережа Петрі інгібіторна мережа Петрі кольорова мережа Петрі мова мережі Петрі бездужковий польський запис обернений польський запис We propose Petri nets that produce languages of Polish notation and reverse Polish notation for propositional formulas and mathematical expressions. Propositional formulas can contain a given number of variables and mathematical expressions. Arithmetic expressions can contain a given number of variables and constants. We also propose inhibitor nets that produce the fixed-point binary numbers in mathematical expressions for above-mentioned languages. The technique of the nets construction allows to use arbitrary functions with a given arity. We also propose a coloured Petri net for calculating values of propositional formulas in reverse Polish notation. The technique of the net construction allows to use arbitrary functions with a given arity using a truth table of a corresponding function. Рассмотрены сети Петри, которые порождают языки бесскобочной польской записи и обратной польской записи для пропозициональных формул и арифметических выражений. Пропозициональные формулы могут содержать заданное количество переменных, а арифметические выражения — переменных и констант. Предложены также ингибиторные сети Петри для указанных языков, позволяющие формировать вещественные числа в двоичной записи с фиксированной точкой в арифметических выражениях. Метод построения сетей позволяет использовать произвольные функции заданной арности. Предложена цветная сеть Петри для вычисления значений пропозициональных формул в обратной польской записи. Метод построения сети позволяет использовать произвольные функции заданной арности с применением таблицы истинности соответствующей функции. Розглянуто мережі Петрі, які породжують мови бездужкового польського запису та оберненого польського запису для пропозиційних формул та арифметичних виразів. Пропозиційні формули можуть містити задану кількість змінних, а арифметичні вирази — змінних та констант. Запропоновано також інгібіторні мережі Петрі для вказаних мов, які дозволяють формувати дійсні числа у двійковому записі з фіксованою точкою у арифметичних виразах. Метод побудови мереж дозволяє використовувати довільні функції заданої арності. Запропоновано кольорову мережу Петрі для обчислення пропозиційних формул в оберненому польському записі. Метод побудови мережі дозволяє застосовувати довільні функції заданої арності з використанням таблиці правдивості відповідної функції. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2016-08-11 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/59334 10.20535/SRIT.2308-8893.2016.2.01 System research and information technologies; No. 2 (2016); 7-13 Системные исследования и информационные технологии; № 2 (2016); 7-13 Системні дослідження та інформаційні технології; № 2 (2016); 7-13 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/59334/71108 Copyright (c) 2021 System research and information technologies |
| spellingShingle | мережа Петрі інгібіторна мережа Петрі кольорова мережа Петрі мова мережі Петрі бездужковий польський запис обернений польський запис Statkevich, Vitaly M. Зв’язок мереж Петрі з бездужковим польським записом |
| title | Зв’язок мереж Петрі з бездужковим польським записом |
| title_alt | Connection between Petri nets and Polish notation Связь сетей Петри с бесскособочной польской записью |
| title_full | Зв’язок мереж Петрі з бездужковим польським записом |
| title_fullStr | Зв’язок мереж Петрі з бездужковим польським записом |
| title_full_unstemmed | Зв’язок мереж Петрі з бездужковим польським записом |
| title_short | Зв’язок мереж Петрі з бездужковим польським записом |
| title_sort | зв’язок мереж петрі з бездужковим польським записом |
| topic | мережа Петрі інгібіторна мережа Петрі кольорова мережа Петрі мова мережі Петрі бездужковий польський запис обернений польський запис |
| topic_facet | Petri net inhibitor Petri net coloured Petri net Petri net language Polish notation reverse Polish notation сеть Петри ингибиторная сеть Петри цветная сеть Петри язык сети Петри бесскобочная польская запись обратная польская запись мережа Петрі інгібіторна мережа Петрі кольорова мережа Петрі мова мережі Петрі бездужковий польський запис обернений польський запис |
| url | https://journal.iasa.kpi.ua/article/view/59334 |
| work_keys_str_mv | AT statkevichvitalym connectionbetweenpetrinetsandpolishnotation AT statkevichvitalym svâzʹsetejpetrisbesskosobočnojpolʹskojzapisʹû AT statkevichvitalym zvâzokmerežpetrízbezdužkovimpolʹsʹkimzapisom |