Регулярні вирази для деяких мов мереж Петрі в задачі про постачальника та споживача
We consider a Petri net for the producer/consumer problem (one of the classical synchronization problems) with the bounded buffer of size n and the regular formal languages Ln, generated by the net. We propose regular expressions denoting these languages in the recursive form, in case of the bounded...
Saved in:
| Date: | 2020 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2020
|
| Subjects: | |
| Online Access: | https://journal.iasa.kpi.ua/article/view/221359 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1867334409566289920 |
|---|---|
| author | Statkevych, Vitalii M. |
| author_facet | Statkevych, Vitalii M. |
| author_institution_txt_mv | [
{
"author": "Vitalii M. Statkevych",
"institution": "Учебно-научный комплекс \"Институт прикладного системного анализа\" Национального технического университета Украины \"Киевский политехнический институт имени Игоря Сикорского\", Киев"
}
] |
| author_sort | Statkevych, Vitalii M. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2021-01-19T12:18:25Z |
| description | We consider a Petri net for the producer/consumer problem (one of the classical synchronization problems) with the bounded buffer of size n and the regular formal languages Ln, generated by the net. We propose regular expressions denoting these languages in the recursive form, in case of the bounded buffer of size from 1 to 3 the explicit formulas are proposed. We transform a reachability graph into a finite automaton and use the state elimination method. We give an upper estimate for the star-height of the mentioned languages, in case of the bounded buffer of size 1 and 2 the exact values are calculated. We also consider union, intersection, Kleene closure, concatenation and set difference operations on mentioned languages. We give the finite automaton and propose regular expressions denoting the set difference of languages Ln \ L1 in the recursive form, for L2 \ L1 the explicit formula is proposed. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2020.3.08 |
| first_indexed | 2025-07-17T10:27:00Z |
| format | Article |
| fulltext |
В.М. Статкевич, 2020
Системні дослідження та інформаційні технології, 2020, № 3 105
УДК 519.711.7+519.713
DOI: 10.20535/SRIT.2308-8893.2020.3.08
РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ ДЛЯ НЕКОТОРЫХ ЯЗЫКОВ
СЕТЕЙ ПЕТРИ В ЗАДАЧЕ О ПРОИЗВОДИТЕЛЕ
И ПОТРЕБИТЕЛЕ
В.М. СТАТКЕВИЧ
Аннотация. Рассмотрены сеть Петри в задаче о производителе и потребителе
(одной из классических задач синхронизации) с ограниченным буфером раз-
мера n и регулярные формальные языки nL , которые она порождает. Для
этих языков найдены регулярные выражения в рекурсивном виде, а в случаях
ограниченного буфера размера от 1 до 3 — в виде явных формул. По графу до-
стижимости построен конечный автомат, применен метод последовательного
удаления вершин. Для высоты итерации (звездной высоты) указанных языков
дана оценка сверху, а в случаях ограниченного буфера размера 1 и 2 найдены
точные значения. Для указанных языков рассмотрены операции объединения,
пересечения, замыкания Клини, конкатенации и разности. Для разности язы-
ков 1\ LLn построен конечный автомат и найдены регулярные выражения в
рекурсивном виде, а для разности 12 \ LL — в виде явной формулы.
Ключевые слова: сеть Петри, задача о производителе и потребителе, язык се-
ти Петри, формальный язык, регулярный язык, конечный автомат, регулярное
выражение, высота итерации (звездная высота).
ВВЕДЕНИЕ
Сети Петри являются удобным средством для моделирования различных
процессов, систем и сетей [1–3]. Одной из классических задач синхрониза-
ции является задача о производителе и потребителе, предложенная
Э. Дейкстрой [1]; существует несколько различных вариантов этой задачи.
Каждая сеть Петри может порождать язык. В работе [1] определены
12 классов языков и исследована их связь с формальными языками, опреде-
ляемыми иерархией Хомского (теорию формальных языков см., например,
в работах [4–7]).
В данной работе рассмотрены некоторые регулярные языки L -типа се-
тей Петри в задаче о производителе и потребителе с ограниченным буфе-
ром, соответствующие регулярные выражения найдены в рекурсивном виде,
а в простейших случаях — в виде явных формул. В простейших случаях
найдены высоты итерации рассмотренных языков, а в более сложных дана
оценка сверху. Некоторые результаты были анонсированы в тезисах [8–9].
Для варианта задачи с неограниченным буфером и соответственно контек-
стно-свободного языка L -типа автомат с магазинной памятью приведен
в тезизах [8], а более полные результаты подробно изложены в тезисах [10].
В работе [11] рассмотрены задачи управления и проектирования слож-
ных систем и предложена теория дискретно-непрерывных сетей, примени-
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2020, № 3 106
мая в случаях, когда объект описывается дифференциальными уравнениями
в непрерывном времени, а управление дискретно.
ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ
В задаче о производителе и потребителе процесс-производитель A произ-
водит объекты (фишки) и помещает их в буфер (позицию 5p ), а процесс-
потребитель B удаляет объект из буфера и использует его (рис. 1). Задача
имеет следующие варианты [1, 3]: 1) с неограниченным буфером;
2) с ограниченным буфером размера
n , тогда вводится дополнительная
позиция 5p , имеющая n фишек;
3) с несколькими производителями и
несколькими потребителями, тогда
в позициях 1p и 3p в начальной мар-
кировке 0 имеются s и t фишек
соответственно; 4) в системе с двумя
производителями и двумя потребите-
лями один из потребителей имеет
приоритет перед другим; такая систе-
ма реализуется при помощи ингибиторной дуги.
Пусть A — алфавит, *A — множество слов, т.е. конечных цепочек сим-
волов из A . Формальным языком L над алфавитом A называют некоторое
подмножество *AL [4–7]. Каждому переходу из множества переходов T
сопоставим символ алфавита A , AT : — функция помечения. По-
добным образом конечной последовательности переходов *Tw сопостав-
ляется слово *)( Aw . Пусть задано множество заключительных маркиро-
вок F . Языком сети Петри L -типа называют множество таких слов )(w ,
что маркировка сети Петри после запуска последовательности переходов w
является заключительной [1]. В рассматриваемой задаче полагаем
},,,{ 4321 ttttT , },,,{ 4321 aaaaA , ii at )( , 4,,1i (таким образом, сеть
является свободно помеченной [1]), }{ 0F .
Множество регулярных выражений над алфавитом A определяется ре-
курсивно [4, 5, 7]: 1) 0, 1 и любой символ Aa являются регулярными вы-
ражениями; 2) если r и s являются регулярными выражениями, то )( sr ,
)( sr и *r также являются регулярными выражениями; 3) иных регулярных
выражений нет. Каждое регулярное выражение r задает язык *][ ArL ,
определяемый рекурсивно: 1) ]0[L , }{]1[ L , }{][ aaL для любого
символа Aa ; 2) ][][][ sLrLsrL , ][][][ sLrLsrL , ** ])[(][ rLrL .
Высота итерации или звездная высота регулярного выражения rsh оп-
ределяется рекурсивно [5, 12]: 1) 0sh0sh a для любого символа Aa ,
11sh ; 2) )sh,max(sh)sh()sh( srsrsr ; rr sh1)sh( * . Высотой ите-
рации регулярного языка L называется минимальная из высот итерации ре-
гулярных выражений, задающих язык L .
Рис. 1. Задача о производителе и потре-
бителе
А В
Регулярные выражения для некоторых языков сетей Петри в задаче
Системні дослідження та інформаційні технології, 2020, № 3 107
ЯЗЫКИ, ПОРОЖДАЕМЫЕ СЕТЬЮ С ОГРАНИЧЕННЫМ БУФЕРОМ
РАЗМЕРА n
Рассмотрим сеть Петри с ограниченным буфером размера n , изображенную
на рис. 1. Граф достижимости сети, изображенный на рис. 2, имеет блочную
структуру.
Порождаемый сетью язык
L -типа обозначим nL . По графу
достижимости строим конечный
автомат, допускающий язык nL :
вершинам графа (т.е. маркиров-
кам сети) сопоставляем состояния
автомата, ребрам графа (т.е. пе-
реходам сети) — переходы авто-
мата, начальной и заключитель-
ной маркировке ),0,0,1,0,1(0 n
— начальное и допускающее
состояние 0q ( Iq 0 , Fq 0 ).
Отметим, что подобный принцип
построения конечного автомата
по графу достижимости исполь-
зовался в работе [13]. Построен-
ный автомат в данном случае яв-
ляется детерминированным:
}{},{,},,,,{},,,{ 004321340 qqaaaaqq n , (1)
}141,2:),,{(}240,2:),,{( 3211 niiqaqniiqaq iiii
}144},1,0{4mod:),,{( 23 niiqaq ii
}342},3,2{4mod:),,{( 24 niiqaq ii (2)
(здесь и далее 4mod означает остаток от деления на 4). Отметим, что в ра-
боте [14] представлен метод нахождения регулярного выражения для языка
безопасной сети без полного построения графа достижимости, а в качестве
примера рассмотрена задача о пяти обедающих мудрецах. Представленный
метод основан на редукции сети Петри.
Пример 1. Пусть 1n . Тогда конечный автомат (1), (2) принимает вид
,}{},{,},,,,{},,,,,,,,{ 0014321765432101 qqaaaaqqqqqqqqM
),,,(),,,(),,,(),,,(),,,(),,,{( 6234217165143121101 qaqqaqqaqqaqqaqqaq
)}.,,(),,,(),,,(),,,(),,,(),,,( 547446143042335234 qaqqaqqaqqaqqaqqaq
Рис. 2. Граф достижимости сети Петри
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2020, № 3 108
Регулярное выражение находим, удаляя по очереди состояния автома-
та 1M ; подробно метод изложен, например, в работах [4, 5, 7]. Удаляя
в каждом из двух блоков (рис. 2) левое нижнее и правое верхнее состояния,
т.е. состояния 1q , 2q , 5q и 6q , получаем обобщенный автомат
31404344210432174302 ,(),,,(),,,{(},,,,{},,,,{ aaqqaaqqaaqaaaaqqqqM
}{},{)},,,(),,,(),,,(),, 0033477123424423313 qqqaaqqaaqqaaaaqqaa .
Запишем 133131 || aaaaaa , 244242 || aaaaaa , используя оператор
параллельной композиции « || » [1, с. 165], а также последовательно удалим
состояния 7q и 3q :
,),,(),,,{(},,,,{},,{ 043442104321403 qaaqqaaqaaaaqqM
}{},{)},),||())(||(,( 00442
*
3412314 qqqaaaaaaaaq .
Следовательно, искомое регулярное выражение имеет вид
*
43
*
42
*
341231211 ])]||())(||[([ aaaaaaaaaaaar ,
его высота итерации 3sh 1 r . Для нахождения высоты итерации языка 1L в
автомате 2M последовательно удаляем состояния 7q и 4q :
),),||(,(),,,{(},,,,{},,{ 3312100432104321303 qaaaaqqaaaaqaaaaqqM
.}{},{)},,)||)(||(,(),,)||(,( 003341231423043423 qqqaaaaaaaaqqaaaaq
Соответствующее регулярное выражение имеет вид
*
4342
*
3412314231214321 ])||(])||)(||)[(||([ aaaaaaaaaaaaaaaaaaaa ,
потому высота итерации языка 2sh 1 L .
Пример 2. Пусть 2n . Тогда конечный автомат (1), (2) принимает вид
,}{},{,},,,,{},,,{ 00143211101 qqaaaaqqM
}7,5,3,1:),,{(}10,8,6,4,2,0:),,{( 32111 iqaqiqaq iiii
}.11,10,7,6,3,2:),,{(}9,8,5,4:),,{( 2423 iqaqiqaq iiii
Как и в примере 1, удалением в каждом из трех блоков левого нижнего
и правого верхнего состояний, т.е. состояний 1q , 2q , 5q , 6q , 9q и 10q , по-
лучаем обобщенный автомат
,}{},{,},,,,{},,,,,,{ 002432111874302 qqaaaaqqqqqqM
),,,(),,,(),,,(),,,{( 44380434821442102 qaaqqaaqqaaqqaaq
),,,(),,,(),,,(),,,( 734113347111277123 qaaqqaaqqaaqqaaq
Регулярные выражения для некоторых языков сетей Петри в задаче
Системні дослідження та інформаційні технології, 2020, № 3 109
)}.,||,(),,||,(),,||,(),,||,( 8427442373183314 qaaqqaaqqaaqqaaq
Последовательно удаляем состояния 11q , 8q и 3q :
}{},{,},,,,{},,,{ 00343217403 qqaaaaqqqM ,
),),||)(||(,(),,,(),,,{( 4423143214043442103 qaaaaaaaaqqaaqqaaq
),,)||()||(,(),,)||()||(,( 44342423477123131214 qaaaaaaaaqqaaaaaaaaq
)}.,)||)(||(,( 71234341231427 qaaaaaaaaaaaaq
Удаляя состояние 7q , а затем 4q , получаем искомое регулярное выра-
жение
))||()||(()||)(||([[ 1231312142314321212 aaaaaaaaaaaaaaaaaar
)||((])||)(||[( 4234
*
123434123142 aaaaaaaaaaaaaaaa
,])])||( *
43
*
4342 aaaaaa
высота итерации которого 3sh 2 r . Однако высота итерации языка
2sh 2 L ; в этом убеждаемся, заменяя автомат 3M на эквивалентный с эп-
силон-переходом
}{},{,},,,,{},,,,{ 003432174003 qqaaaaqqqqM ,
)},,(),,1,(),,,{()}),,{(\( 043400421434043433 qaaqqqqaaaaqqaaq
и последовательным удалением состояний 7q и 4q , получая регулярное вы-
ражение
)||(()||)(||([1 3121423121434321212 aaaaaaaaaaaaaaaaaar
341231421231 )||)(||[())||( aaaaaaaaaaaa
43
*
43424234
*
1234 )])||()||((] aaaaaaaaaaaaaa
высоты итерации 2sh 2 r . Подобное преобразование автомата для умень-
шения высоты итерации регулярного выражения приведено, например, в
работах [5, упр. 5.4.10] и [12, с. 36].
Пример 3. Пусть 3n . Удаляя в автомате (1), (2) в каждом из четырех
блоков (рис. 2) левое нижнее и правое верхнее состояния, получаем обоб-
щенный автомат
,}{},{,},,,,{},,,,,,,,{ 0014321151211874301 qqaaaaqqqqqqqqM
}8,4,0:),,{(}8,4,0:),,{( 4344211 iqaaqiqaaq iiii
}11,7,3:),,{(}11,7,3:),,{( 344412 iqaaqiqaaq iiii
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2020, № 3 110
}.12,8,4:),||,{(}12,8,4:),||,{( 421131 iqaaqiqaaq iiii
Обозначаем 211 aae , 432 aae , 313 || aae , 424 || aae и последова-
тельно удаляем состояния 15q , 12q и 11q :
,}{},{,},,,,{},,,,,{ 0024321874302 qqaaaaqqqqqM
),,,(),,,(),,,(),,,{( 4280248144102 qeqqeqqeqqeq
),,,(),,,(),,,(),,,( 443334327713 qeqqeqqeqqeq RR
),,)(,(),,)(,( 72
*
342117824
*
342131218 qeeeeeeqqeeeeeeeeeeq RRRRRR
)},)(,(),,)(,( 824
*
342114772
*
34213138 qeeeeeeeeqqeeeeeeeeq RRRRRR
(здесь и далее Rw — обращение или зеркальный образ слова w [4, 5, 7]).
Отметим, что удаление состояния 15q добавляет лишь петлю
),,( 112111 qeeq RR , не изменяя другие переходы автомата; удаление состояний
12q и 11q добавляет лишь петли у состояний 7q и 8q и усложняет переходы
из 7q в 8q и обратно, также не изменяя другие переходы автомата. Удаляем
последовательно состояния 8q и 3q :
,}{},{,},,,,{},,,{ 00343217403 qqaaaaqqqM
),,))((,(),,,(),,,{( 42
*
24
*
3421312114340244103 qeeeeeeeeeeeeeeqqeqqeq RR
),),)(())((,( 72
*
3421313
*
24
*
342131211134 qeeeeeeeeeeeeeeeeeeeeeq RRRRRR
),,))()()((,( 42
*
24
*
3421312124
*
342114427 qeeeeeeeeeeeeeeeeeeeeeq RRRRRR
*
24
*
3421312124
*
3421147 ))()()((,( eeeeeeeeeeeeeeeeeeq RRRRR
)}.,)())(( 7122
*
342112
*
3421313 qeeeeeeeeeeeeeeee RRRRRRRRR
Удаляя состояние 7q , а затем 4q , получаем искомое регулярное выра-
жение
2
*
24
*
3421312114313 ))(([[ eeeeeeeeeeeeeeer RR
)])(())(([ 2
*
3421313
*
24
*
34213121113
RRRRRR eeeeeeeeeeeeeeeeeeeee
*
24
*
3421312124
*
342114 ))()()([( eeeeeeeeeeeeeeeeee RRRRR
*
122
*
342112
*
3421313 ])())(( RRRRRRRRR eeeeeeeeeeeeeeee
*
2
*
2
*
24
*
3421312124
*
34211442 ]]]))()()(([ eeeeeeeeeeeeeeeeeeeeee RRRRRR
Регулярные выражения для некоторых языков сетей Петри в задаче
Системні дослідження та інформаційні технології, 2020, № 3 111
высотой итерации 5sh 3 r . Заменой же автомата 3M на эквивалентный с
эпсилон-переходом (см. пример 2)
}{},{,},,,,{},,,,{ 003432174003 qqaaaaqqqqM ,
)},,(),,1,(),,,{()}),,{(\( 02400412402433 qeqqqqeeqqeq
и последовательным удалением состояний 7q и 4q получаем регулярное
выражение
2
*
24
*
342131211431213 ))(([1 eeeeeeeeeeeeeeeeer RR
)])(())(([ 2
*
3421313
*
24
*
34213121113
RRRRRR eeeeeeeeeeeeeeeeeeeee
*
24
*
3421312124
*
342114 ))()()([( eeeeeeeeeeeeeeeeee RRRRR
*
122
*
342112
*
3421313 ])())(( RRRRRRRRR eeeeeeeeeeeeeeee
2
*
2
*
24
*
3421312124
*
34211442 ]]))()()(([ eeeeeeeeeeeeeeeeeeeeee RRRRRR
высотой итерации 4sh 3 r . Следовательно, 4sh 3 L , однако существует
(см. далее замечание 1 и оценку (17)) более точная оценка 3sh 3 L , на ос-
новании которой с учетом очевидного вложения 32 LL и равенства
2sh 2 L (см. пример 2) автор выдвигает следующую гипотезу.
Гипотеза. 3sh 3 L .
В общем случае регулярное выражение для nL имеет следующий ре-
курсивный вид.
Теорема 1. Язык nL имеет вид
]))([( *
43
*
1
*
11121 aaltrsaaLL nnnnn (3)
])(1[ 43
*
1
*
111214321 aaltrsaaaaaaL nnnn , (4)
где регулярные выражения 1ns , 1nl , 1nt и 1nr определены рекурсивно:
310341204200 ||,,||,0 aaraaaataals , (5)
43
****
2143
*
211 )( aaslrsltrsaaaasaas kkkkkkkkkk , (6)
34
**
121 )( aarsltaat kkkkk , (7)
43
***
12421 )()||( aaslrsltaaaal kkkkkkk , (8)
34
***
21311 )()||( aarsltrsaaaar kkkkkkk (9)
(здесь 2,,0 nk ).
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2020, № 3 112
Доказательство. Рассмотрим автомат (1), (2). Аналогично примерам
1–3 удалением в каждом из 1n блоков рис. 2 левого нижнего и правого
верхнего состояний (т.е. состояний iq , }2,1{4mod i , 241 ni ) получа-
ем обобщенный автомат
,}{},{,},,,,{},,,,,,,{ 001432134474301 qqaaaaqqqqqqM nn
}44,,4,0:),,{(}44,,4,0:),,{( 4344211 niqaaqniqaaq iiii
}14,,7,3:),,{(}14,,7,3:),,{( 344412 niqaaqniqaaq iiii
}.4,,8,4:),||,{(}4,,8,4:),||,{( 421131 niqaaqniqaaq iiii
Удаляем состояние 34 nq , тем самым добавляя петлю
),,( 14341214 nn qaaaaq , добавляем петлю ),0,( 44 nn qq и вводим обозначе-
ния (5). Множеству переходов полученного автомата принадлежат, в том
числе, переходы
),,,(),,,(),,,( 4044443442144 nnnnnn qsqqaaqqaaq
),,(),,,( 40141404 nnnn qlqqrq , (10)
),,(),,,(),,,( 14014543414141254 nnnnnn qtqqaaqqaaq . (11)
Удаляем состояние nq4 . Тогда из множества переходов удаляются пе-
реходы (10), а добавляются переходы
),,,(),,,( 140
*
021444443
*
02144 nnnn qrsaaqqaasaaq
),,(),,,( 140
*
00144443
*
0014 nnnn qrslqqaaslq ; (12)
объединение двух параллельных петель — третьего перехода из формулы
(11) и четвертого перехода из формулы (12) — дает петлю 014 ,( tq n
), 140
*
00 nqrsl . Аналогичными рассуждениями удаление состояния 14 nq ,
объединение параллельных переходов и введение регулярных выражений
1s , 1t , 1l и 1r согласно формулам (6)–(9) приводит к добавлению переходов
),,(),,,(),,,(),,,( 44154541445415444144 nnnnnnnn qlqqrqqtqqsq .
Выполняя далее подобную процедуру, т.е. удаляя состояния в порядке
44 nq , 54 nq , …, 7q , получаем рекурсивные формулы (6)–(9) и автомат
),,,(),,,{(},,,,{},,,{ 0434421043214302 qaaqqaaqaaaaqqqM
.}{},{)},,,(),,,(),,,(),,,( 00413314313414 qqqlqqrqqtqqsq nnnn
Удаляя состояние 3q , а затем 4q , получаем регулярное выражение, до-
казывающее формулу (3). Заменой же автомата 2M на эквивалентный с эп-
силон-переходом (см. примеры 2, 3)
),,1,(),,,(),,,{(},,,,{},,,,{ 0004344210432143002 qqqaaqqaaqaaaaqqqqM
Регулярные выражения для некоторых языков сетей Петри в задаче
Системні дослідження та інформаційні технології, 2020, № 3 113
}{},{)},,,(),,,(),,,(),,,( 004133143134121434 qqqlqqrqqtqqsaaaaq nnnn
и последовательным удалением состояний 3q и 4q получаем регулярное
выражение, доказывающее формулу (4). Теорема доказана.
Следствие 1. Удаление состояний автомата 1M теоремы 1 в ином по-
рядке 34 nq , 14 nq , nq4 , 54 nq , 44 nq , …, 8q приводит к эквивалентным ре-
курсивным формулам:
,||ˆ,ˆ,||ˆ,0ˆ 3100341200420000 aarraaaattaallss
43
**
211 )ˆˆˆˆ(ˆ aaltrsaas kkkkk , (13)
34
****
1234
*
121
ˆˆ)ˆˆˆˆ(ˆˆˆˆ aatrltrsltaaaataat kkkkkkkkkk , (14)
43
***
12421 )ˆˆˆˆ(ˆˆ)||(ˆ aaltrsltaaaal kkkkkkk , (15)
34
***
21311
ˆˆ)ˆˆˆˆ()||(ˆ aatrltrsaaaar kkkkkkk (16)
( 2,,0 nk ) при сохранении формул (3)–(5), т.е.
]))ˆˆˆˆ([( *
43
*
1
*
11121 aaltrsaaLL nnnnn
])ˆˆˆˆ(1[ 43
*
1
*
111214321 aaltrsaaaaaaL nnnn .
Следствие 2. Удаление состояний ,,,,, 544414434 nnnnn qqqqq
1112 ,, qq автомата 1M теоремы 1 с последующей заменой автомата на эк-
вивалентный с эпсилон-переходом (см. примеры 2, 3) приводит к автомату
,}{},{,},,,,{},,,,,,{ 00243218743002 qqaaaaqqqqqqM
),,1,(),,,(),,,(),,,(),,,{( 0044380434821442102 qqqaaqqaaqqaaqqaaq
),,,(),,||,(),,||,(),,,(),,,( 4214344423331433477123 qaaaaqqaaqqaaqqaaqqaaq
)};,,(),,,(),,,(),,,( 827728727828 qlqqrqqtqqsq nnnn
дальнейшим удалением состояний 3q и 4q получаем автомат
,}{},{,},,,,{},,,,{ 003432187003 qqaaaaqqqqM
),,))||)(||((1,{( 0143
*
423121432103 qeaaaaaaaaaaaaq
),,)||())||)(||((,( 721231
*
42312143210 qeaaaaaaaaaaaaaaq
),,))||)(||((,( 8321
*
42312143210 qeaaaaaaaaaaaaq
),,))||)(||()(||(,( 0443
*
4231214342347 qeaaaaaaaaaaaaaaq
21434234123427 )(||(,( aaaaaaaaaaaatq n
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2020, № 3 114
),,)||())||)(||( 751231
*
4231 qeaaaaaaaa
),,))||)(||()(||(,( 8621
*
42312143423427 qeaaaaaaaaaaaaaalq n
),,))||)(||((,( 0743
*
42312143438 qeaaaaaaaaaaaaq
),,)||())||)(||((,( 781231
*
423121434328 qeaaaaaaaaaaaaaarq n
)},))||)(||((,( 8921
*
423121434328 qeaaaaaaaaaaaasq n
и соответствующее ему регулярное выражение
)())(( 4
*
587
*
6
*
5896
*
5234
*
521 eeeeeeeeeeeeeeee .
Замечание 1. Оценим высоту итерации языка nL . Поскольку 00 s со-
гласно формуле (5), регулярные выражения (6)–(9) для случая 0k пред-
ставимы в виде
430
*
00002143211 )( aalrltraaaaaas ,
34
*
000121 )( aarltaat ,
430
*
00012421 )()||( aalrltaaaal ,
34
*
000021311 )()||( aarltraaaar .
Следовательно, 1shshshsh 1111 rlts , а из формул (6)–(9) и след-
ствия 2 получаем
12shshshsh krlts kkkk ( 1k ),
1shshshshsh 74321 eeeee ,
52shshshsh 9865 neeee ,
32sh nLn ( 3n ). (17)
Отметим, что ни формула (4) не улучшает полученную оценку (17), по-
скольку 32shshshsh 1111 nrlts nnnn , 12sh nLn , ни формулы
(13)–(16), поскольку
2ˆshˆshˆshˆsh 1111 rlts ,
22ˆshˆshˆshˆsh 1111 nrlts nnnn ,
nLn 2sh . В случаях 1n и 2n высота итерации языка 2shsh 21 LL
(см. примеры 1, 2), в случае 3n 3sh 3 L (см. пример 3). Вопрос улучше-
ния оценки (17), равно как и вопрос нахождения nLsh , для случаев 3n на
данный момент остается для автора открытым.
Регулярные выражения для некоторых языков сетей Петри в задаче
Системні дослідження та інформаційні технології, 2020, № 3 115
НЕКОТОРЫЕ ОПЕРАЦИИ НАД ФОРМАЛЬНЫМИ ЯЗЫКАМИ nL
Для двух языков nL и mL ( mn ) выполняется очевидное вложение
mn LL , потому nmn LLL , mmn LLL . Из формулы (3) следует ра-
венство nn LL *)( .
Для конкатенации выполняется равенство nnmmn LLLLL . Действи-
тельно, для nLw ввиду принадлежности mL для произвольного m
имеем mnLLww , откуда следует вложение mnn LLL . Докажем обрат-
ное вложение. Пусть mnLLwww 21 , где nLw 1 , mLw 2 . Сеть Петри с
ограниченным буфером размера n , порождающая слово 1w , может поро-
дить и слово 2w , поскольку для его порождения требуется меньший буфер
размера nm . Потому она может породить и слово 21www , т.е. nLw ,
nmn LLL . Равенство nnm LLL доказывается аналогично.
Рассмотрим разность языков nL и mL для mn . Язык mn LL \
mn LL регулярен, как пересечение регулярного языка nL с регулярным
языком mL — дополнением к регулярному языку mL (свойства замкнутости
регулярных языков см., например, [4, 5, 7]).
Пример 4. Рассмотрим язык 12 \ LL . Построим конечный автомат 1M ,
допускающий данный язык, согласно следующему принципу. Буфер (пози-
ция 5p ) имеет ограни-
ченный размер 2 и бу-
фер хотя бы в один мо-
мент времени содержит
две фишки. Пусть 0t —
момент времени, когда
впервые выполнилось
условие 2)( 5 p . До
момента 0t (формаль-
нее: до соответствующе-
го такта) 1M функцио-
нирует как автомат 1M
примера 1, допускаю-
щий язык 1L ; с момента
0t — как автомат 1M
примера 2, допускаю-
щий язык 2L . Автомат
1M имеет вид, указан-
ный на рис. 3:
}{},{,},,,,{},,,{},,{ 001114321110701 qqaaaaqqqqM ,
),,,(),,,(),,,(),,,(),,,(),,,{( 6234217165143121101 qaqqaqqaqqaqqaqqaq
Рис. 3. Автомат, допускающий язык 12 \ LL
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2020, № 3 116
)},,,(),,,(),,,(),,,(),,,(),,,( 547446143042335234 qaqqaqqaqqaqqaqqaq (18)
)},,(),,,{( 10278251 qaqqaq , (19)
}7,5,3,1:),,{(}10,8,6,4,2,0:),,{( 32111 iqaqiqaq iiii
}.11,10,7,6,3,2:),,{(}9,8,5,4:),,{( 2423 iqaqiqaq iiii
В построенном автомате состояния 70 ,, qq и переходы из множества
1 соответствуют автомату 1M примера 1, состояния 110 ,, qq и переходы
из множества 1 — автомату 1M примера 2, переходы из множества 1
«связывают» две различные части. Построенный автомат является детерми-
нированным.
Регулярное выражение находим следующим образом. В каждом из пяти
блоков (двух блоков в левой колонке рис. 3 и трех в правой) удаляем левое
нижнее и правое верхнее состояния аналогично примеру 2, т.е. состояния
1q , 2q , 5q , 6q , 1q , 2q , 5q , 6q , 9q и 10q :
24321118743074302 },,,,{},,,,,,,,,,{ aaaaqqqqqqqqqqM
,}{},{, 0022 qq
),,||,(),,,(),,,{( 3314043442102 qaaqqaaqqaaq
)},,,(),,,(),,||,( 334771234423 qaaqqaaqqaaq (20)
)},||,(),,,(),,,({ 84271112782142 qaaqqaaqqaaq , (21)
),,,(),,,(),,,(),,,({ 44380434821442102 qaaqqaaqqaaqqaaq
),,,(),,,(),,,(),,,( 734113347111277123 qaaqqaaqqaaqqaaq
)}.,||,(),,||,(),,||,(),,||,( 8427442373183314 qaaqqaaqqaaqqaaq
Заменяем автомат 2M на эквивалентный, удаляя переходы ),,( 0434 qaaq ,
),,( 4210 qaaq и добавляя петли ),,( 421434 qaaaaq , ),,( 421434 qaaaaq . Последо-
вательно удаляем состояния 11q , 3q и 3q , а также учитываем формулы (5):
}{},{,},,,,{},,,,,,,{ 00333432187407403 qqaaaaqqqqqqqM ,
),),||)(||(,(),,,{( 442312143442103 qaaaaaaaaqqaaq
)},,,(),),||(,(),,)||(,( 712347442347712314 qaaaaqqaaaaqqaaaaq
)},||,(),,,(),,,({ 80427703412782143 qlaaqqtaaaaqqaaq ,
),,)||(,(),),||)(||(,(),,,({ 712314442312143404343 qaaaaqqaaaaaaaaqqaaq
Регулярные выражения для некоторых языков сетей Петри в задаче
Системні дослідження та інформаційні технології, 2020, № 3 117
),,,(),),||(,( 712340123434127442347 qaaaataaaaaaaaqqaaaaq
)}.,||,(),,||,(),,,(),,,( 804277031844388214 qlaaqqraaqqaaqqaaq (22)
Последовательно удаляем состояния 8q , 7q и 7q ; при удалении состоя-
ния 7q объединение двух параллельных петель
)),||)(||(,( 4423121434 qaaaaaaaaq ,
)),||()()||(,( 44234
*
123412314 qaaaaaaaaaaaaq
дает петлю )),||())(||(,( 442
*
34123121434 qaaaaaaaaaaaaq ; с учетом этого
получаем автомат
}{},{,},,,,{},,,,{ 004432140404 qqaaaaqqqqM ,
),,,(),,,{( 043442104 qaaqqaaq
),),||())(||(,( 442
*
34123121434 qaaaaaaaaaaaaq
4342
*
1234123143214 )||()()||(,( aaaaaaaaaaaaaaaaq
)))||)(||(()()||()||(( 31423412
*
123412313121 aaaaaaaaaaaaaaaaaaaa
),),)||()||(())||)(||(( 443424234
*
314212343412 qaaaaaaaaaaaaaaaaaaaa
))||()||(()||)(||(,( 123131214231214343214 aaaaaaaaaaaaaaaaaaaaq
)}.),)||()||(())||)(||(( 443424234
*
314212343412 qaaaaaaaaaaaaaaaaaaaa
Удаляя состояние 4q и 4q , получаем искомое регулярное выражение
*
42
*
3412312143214 )]||())(||([ aaaaaaaaaaaaaar
4342
*
123412314321 )||()()||([ aaaaaaaaaaaaaaaa
)))||)(||(()()||()||(( 31423412
*
123412313121 aaaaaaaaaaaaaaaaaaaa
)])||()||(())||)(||(( 43424234
*
314212343412 aaaaaaaaaaaaaaaaaaaa
))||()||(()||)(||([ 12313121423121434321 aaaaaaaaaaaaaaaaaaaa
43
*
43424234
*
314212343412 )])||()||(())||)(||(( aaaaaaaaaaaaaaaaaaaaaa
высотой итерации 2sh 4 r . Тогда высота итерации языка 2)\sh( 12 LL .
Отметим, что 212 sh)\sh( LLL с учетом примера 2.
Регулярное выражение для 1\ LLn имеет следующий рекурсивный вид.
Теорема 2. Язык 1\ LLn , 2n имеет вид ][\ 1\1 nn rLLL , где
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2020, № 3 118
*
42
*
3412312143211\ )]||())(||([ aaaaaaaaaaaaaarn
43
*
22
*
1234123121 ))()||([( aaslaaaaaaaaaa nn
))()()||(( 2
*
222
*
123412312
*
221 nnnnnn rsltaaaaaaaarsaa
)])||(()( 43
*
224234
*
12342
*
222 aaslaaaaaaaarslt nnnnnn
))||(()||)(||([ 2
*
221123143
*
22142312143 nnn rsaaaaaaaasaaaaaaaaaa
,)])||(()( 43
*
43
*
224234
*
12342
*
222 aaaaslaaaaaaaarslt nnnnnn (23)
а 2ns , 2nt , 2nl и 2nr определены рекурсивно формулами (5)–(9).
Доказательство. Сперва отметим, что для случая 2n непосредст-
венная подстановка формул (5) в формулу (23) доказывает, что 1\nr совпада-
ет с регулярным выражением 4r примера 4. Рассмотрим автомат
}{},{,},,,,{},,,{},,{ 001114321340701 qqaaaaqqqqM n ,
}141,2:),,{(}240,2:),,{( 32111 niiqaqniiqaq iiii
}144},1,0{4mod:),,{( 23 niiqaq ii
}342},3,2{4mod:),,{( 24 niiqaq ii
(здесь 1 и 1 определены формулами (18), (19) соответственно, а 1 ана-
логично формуле (2)). Рассматриваемый автомат является детерминирован-
ным. Аналогично теореме 1 удалением в каждом из 3n блоков левого
нижнего и правого верхнего состояний (т.е. состояний 1q , 2q , 5q , 6q и iq ,
}2,1{4mod i , 241 ni ) получаем обобщенный автомат
24321344743074302 },,,,{},,,,,,,,,,,{ aaaaqqqqqqqqqqM nn
}{},{, 0022 qq ,
}44,,4,0:),,{(}44,,4,0:),,{( 4344212 niqaaqniqaaq iiii
}14,,7,3:),,{(}14,,7,3:),,{( 344412 niqaaqniqaaq iiii
}4,,8,4:),||,{(}4,,8,4:),||,{( 421131 niqaaqniqaaq iiii
(здесь 2 и 2 определены формулами (20), (21) соответственно, а 2 ана-
логично множеству 1 из доказательства теоремы 1). Последовательно уда-
ляем состояния 34 nq , nq4 , 14 nq , 44 nq , 54 nq , …, 15q и вводим рекурсив-
ные формулы (6)–(9) по аналогии с рассуждениями доказательства
теоремы 1. Отметим, что данные действия не изменяют переходы множеств
2 и 2 . Полученный автомат имеет вид
Регулярные выражения для некоторых языков сетей Петри в задаче
Системні дослідження та інформаційні технології, 2020, № 3 119
2432112118743074302 },,,,{},,,,,,,,,,,{
~
aaaaqqqqqqqqqqqM
}{},{,
~
0022 qq ,
}8,4,0:),,{(}8,4,0:),,{(
~
4344212 iqaaqiqaaq iiii
),,,(),,,(),,,(),,,{( 734113347111277123 qaaqqaaqqaaqqaaq
),,||,(),,||,(),,||,(),,||,( 8427442373183314 qaaqqaaqqaaqqaaq
)}.,,(),,,(),,,(),,,( 12311113121131112312 qlqqrqqtqqsq nnnn
Заменяем автомат 2
~
M на эквивалентный, удаляя переходы ),,( 0434 qaaq ,
),,( 4210 qaaq и добавляя петли ),,( 421434 qaaaaq , ),,( 421434 qaaaaq . Последо-
вательно удаляем состояния 12q и 11q , используем рекурсивные форму-
лы (6)–(9), затем удаляем состояния 3q и 3q :
}{},{,},,,,{},,,,,,,{ 00333432187407403 qqaaaaqqqqqqqM ,
),),||)(||(,(),,,{( 442312143442103 qaaaaaaaaqqaaq
)},,,(),),||(,(),,)||(,( 712347442347712314 qaaaaqqaaaaqqaaaaq (24)
)},,(),,,(),,,({ 82772782143 qlqqtqqaaq nn , (25)
),,)||(,(),),||)(||(,(),,,({ 712314442312143404343 qaaaaqqaaaaaaaaqqaaq
),,,(),,,(),),||(,( 82147123427442347 qaaqqaaaatqqaaaaq n
)}.,,(),,,(),,,(),,,( 8288277284438 qsqqlqqrqqaaq nnn (26)
Сравнение данного автомата с автоматом 3M примера 4 показывает:
1) в множествах 3 переходы совпадают;
2) в множествах 3 второй и третий переходы различаются лишь инде-
ксами;
3) в множествах 3 пятый, восьмой и девятый переходы различаются
лишь индексами, а десятый переход множества (26) при 2n с учетом
формул (5) является пустым переходом ),0,( 808 qsq и его можно без поте-
ри общности добавить в множество (22).
Потому, выполняя предложенные в примере 4 дальнейшие действия, а
именно последовательно удаляя состояния 8q , 7q , 7q , 4q и 4q , а также
принимая во внимание оговоренную в п. 3) петлю ),,( 828 qsq n , получаем
искомое регулярное выражение (23).
Теорема доказана.
Следствие 3. Язык 1\ LLn также допускает представление в виде
][\ 1\1 nn rLLL , где
*
42
*
3412312143211\ )]||())(||([ aaaaaaaaaaaaaarn
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2020, № 3 120
43
*
22
*
2
*
222
*
123412311 )()()||([ aaslrsltaaaaaaaas nnnnnnn
))()()||(( 2
*
222
*
123412312
*
221 nnnnnn rsltaaaaaaaarsaa
.][])( 43
*
1
*
11121431
*
134
*
2
*
222 aaltrsaaaaltaarslt nnnnnnnnnn (27)
Доказательство. В доказательстве теоремы 2 при построении автомата
3M по автомату 2
~
M не удаляем (в отличие от доказательства теоремы 2)
состояние 3q , получая следующий автомат:
}{},{,
~
},,,,{},,,,,,,,{
~
003334321874307403 qqaaaaqqqqqqqqM ,
),,||,(),,||,(),,,(),,,({
~
4423331442143404343 qaaqqaaqqaaaaqqaaq
),,,(),,,(),,,(),,,( 821472733477123 qaaqqtqqaaqqaaq n
)},,(),,,(),,,(),,,( 8288277284438 qsqqlqqrqqaaq nnn
(здесь 3 и 3 определены формулами (24), (25) соответственно). Последова-
тельно удаляем состояния 8q и 7q , используем рекурсивные формулы (6)–(9):
}{},{,
~
},,,,{},,,,,,{
~
004343214307404 qqaaaaqqqqqqM ,
),,,(),,)(,({
~
4143134
*
2
*
2222
*
22144 qsqqraarsltrsaaq nnnnnnnn
),,)(,(),,)(,( 443
*
22
*
2
*
22273342
*
2227 qaaslrsltqqaarsltq nnnnnnnnnn
)},,(),,,(),,,(),,,(),,,( 31341331441214340434 qtqqlqqrqqsaaaaqqaaq nnnn
(в третьем переходе множества 4
~
использована запись eee * , см. на-
пример, [4, 5]). Последовательным удалением состояний 7q и 3q получаем
автомат
}{},{,
~
},,,,{},,,,{
~
005432140405 qqaaaaqqqqM ,
),,(),,,{(
~
043442105 qaaqqaaq ,
)),||())(||(,( 442
*
34123121434 qaaaaaaaaaaaaq ,
43
*
22
*
2
*
222
*
1234123114 )()()||(,( aaslrsltaaaaaaaasq nnnnnnn
))()()||(( 2
*
222
*
123412312
*
221 nnnnnn rsltaaaaaaaarsaa
)},,(),,)( 41
*
1112143441
*
134
*
2
*
222 qltrsaaaaqqltaarslt nnnnnnnnnn
и искомое регулярное выражение (27). Следствие доказано.
Регулярные выражения для некоторых языков сетей Петри в задаче
Системні дослідження та інформаційні технології, 2020, № 3 121
Замечание 2. Формула (27), использующая индексы 2n и 1n , выг-
лядит более компактной по сравнению с формулой (23). По сути же регуляр-
ное выражение 1\nr из-за дополнительного шага рекурсии сложнее, чем 1\nr .
Именно потому в примере 4 и в доказательстве теоремы 2 состояние 3q
удаляется до состояний 8q и 7q , хотя шаг рекурсии предполагает обратное.
Замечание 3. Для высоты итерации языка mn LL \ ( mn ) выполняется
равенство nmn LLL sh)\sh( , поскольку высоту итерации языка определяет
именно n (подобно тому, как на рис. 3 высоту итерации языка определяет
именно правая, более высокая колонка).
Отметим, что в работе [15] предложен эвристический алгоритм по-
строения по заданному конечному автомату регулярного выражения, высота
итерации которого близка к высоте итерации соответствующего регулярно-
го языка (такое регулярное выражение в работе [15] называется псевдо-
оптимальным).
Замечание 4. Напомним, что языком сети Петри T -типа называют
множество таких слов )(w , что после запуска последовательности перехо-
дов w ни один переход невозможно запустить [1]. Порождаемый сетью
Петри, изображенной на рис. 1, язык T -типа не содержит ни одного слова
L как для варианта задачи с ограниченным буфером, так и с неограни-
ченным.
ЛИТЕРАТУРА
1. Дж. Питерсон, Теория сетей Петри и моделирование систем. М.: Мир, 1984,
264 с.
2. В.Е. Котов, Сети Петри. М.: Наука. Гл. ред. физ.-мат. лит-ры, 1984, 160 с.
3. Т. Мурата, “Сети Петри: Свойства, анализ, приложения”, ТИИЭР, т. 77, № 4,
c. 41–85, 1989.
4. А.Е. Пентус и М.Р. Пентус, Теория формальных языков. М.: Изд-во ЦПИ при
механико-математическом ф-те МГУ, 2004, 80 с.
5. А.Е. Пентус и М.Р. Пентус, Математическая теория формальных языков. М.:
«Бином», 2006, 247 с.
6. С. Гинзбург, Математическая теория контекстно-свободных языков. М.:
Мир, 1970, 326 с.
7. Дж. Э. Хопкрофт, Р. Мотвани, и Дж. Д. Ульман, Введение в теорию автома-
тов, языков и вычислений. М.: Вильямс, 2002, 528 с.
8. В.М. Статкевич, “Регулярные выражения для языков сети Петри «производи-
тель/потребитель» с ограниченным буфером размера 1 и 2”, на Системный
анализ и информационные технологии, материалы 19-й Международной науч-
но-технической конференции SAIT 2017, Киев, 22–25 мая 2017, с. 123.
9. V. Statkevych, “On regular expressions for producer/consumer Petri net languages
with bounded buffer”, in Nonlinear Analysis and Applications: Materials of 4th In-
ternational scientific conference on memory of corresponding member of National
Academy of Science of Ukraine V.S. Mel’nik, Kyiv, 4–6 April, 2018, p. 68.
10. V. Mukhin and V. Statkevych, “On one context-free language for pro-
ducer/consumer Petri net with the unbounded buffer”, in 15th International con-
ference on Development and Application Systems, Suceava, Romania, 21–23 May, 2020,
pp. 137–140.
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2020, № 3 122
11. М.З. Згуровский и В.А. Денисенко, Дискретно-непрерывные системы с управ-
ляемой структурой. Теория, моделирование, применение. К.: Наукова думка,
1998, 351 с.
12. А. Саломаа, Жемчужины теории формальных языков. М.: Мир, 1986, 159 с.
13. R. Valk and G. Vidal-Naquet, “Petri nets and regular languages”, Journal of Com-
puter and System Sciences, 23, pp. 299–325, 1981.
14. A. Gronewold and H. Fleischhack, “Computing Petri net languages by reductions”,
in Fundamentals of computation theory: 10th International conference; proceedings /
FCT’95, Drezden, Germany, August 22–25, 1995, Springer, pp. 253–262.
15. С.В. Баумгертнер и Б.Ф. Мельников, “Мультиэвристический подход к проблеме
звездно-высотной минимизации недетерминированных конечных автоматов”,
Вестник Воронежского государственного университета. Серия: Cистемный
анализ и информационные технологии, № 1, c. 5–7, 2010.
Поступила 11.08.2020
INFORMATION ON THE ARTICLE
Vitalii M. Statkevych, ORCID: 0000-0001-5210-9890, Educational and Scientific Complex
“Institute for Applied System Analysis” of the National Technical University of Ukraine
“Igor Sikorsky Kyiv Polytechnic Institute”, Ukraine, e-mail: mstatckevich@yahoo.com
REGULAR EXPRESSIONS FOR SOME PETRI NET LANGUAGES FOR THE
PRODUCER/CONSUMER PROBLEM / V.M. Statkevych
Abstract. We consider a Petri net for the producer/consumer problem (one of the
classical synchronization problems) with the bounded buffer of size n and the regu-
lar formal languages nL , generated by the net. We propose regular expressions de-
noting these languages in the recursive form, in case of the bounded buffer of size
from 1 to 3 the explicit formulas are proposed. We transform a reachability graph in-
to a finite automaton and use the state elimination method. We give an upper esti-
mate for the star-height of the mentioned languages, in case of the bounded buffer of
size 1 and 2 the exact values are calculated. We also consider union, intersection,
Kleene closure, concatenation and set difference operations on mentioned lan-
guages. We give the finite automaton and propose regular expressions denoting the
set difference of languages 1\ LLn in the recursive form, for 12 \ LL the explicit
formula is proposed.
Keywords: Petri net, producer/consumer problem, Petri net language, formal lan-
guage, regular language, finite automaton, regular expression, star-height.
РЕГУЛЯРНІ ВИРАЗИ ДЛЯ ДЕЯКИХ МОВ МЕРЕЖ ПЕТРІ В ЗАДАЧІ ПРО
ПОСТАЧАЛЬНИКА ТА СПОЖИВАЧА / В.М. Статкевич
Анотація. Розглянуто мережу Петрі в задачі про постачальника та споживача
(одній з класичних задач синхронізації) з обмеженим буфером розміру n і ре-
гулярні формальні мови nL , які вона породжує. Для цих мов знайдено регу-
лярні вирази в рекурсивному вигляді, а у випадках обмеженого буфера розміру
від 1 до 3 — у вигляді явних формул. За графом досяжності побудовано скін-
ченний автомат, застосовано метод послідовного видалення вершин. Для висо-
ти ітерації (зіркової висоти) вказаних мов надано оцінку зверху, а у випадках
обмеженого буфера розміру 1 та 2 знайдено точні значення. Для вказаних мов
розглянуто операції об’єднання, перетину, замикання Кліні, конкатенації
та різниці. Для різниці мов 1\ LLn побудовано скінченний автомат і знайдено
регулярні вирази в рекурсивному вигляді, а для різниці 12 \ LL — у вигляді
явної формули.
Ключові слова: мережа Петрі, задача про постачальника та споживача, мова
мережі Петрі, формальна мова, регулярна мова, скінченний автомат, регуляр-
ний вираз, висота ітерації (зіркова висота).
Регулярные выражения для некоторых языков сетей Петри в задаче
Системні дослідження та інформаційні технології, 2020, № 3 123
REFERENCES
1. J. Peterson, Petri net theory and modeling of systems. Moscow: Mir, 1984.
2. V.E. Kotov, Petri nets. Moscow: Nauka, 1984.
3. Т. Murata, “Petri nets: Properties, analysis and applications”, Trudy Instituta in-
zhenerov po elektrotekhnike i radioelektronike, vol. 77, no. 4, pp. 41–85, 1989.
4. A.E. Pentus and M.R. Pentus, Formal language theory. Мoscow: Mekhaniko-
matematicheskii fakul’tet Moskovskogo Gosudarstvenogo Universiteta, 2004.
5. A.E. Pentus and M.R. Pentus, The mathematical theory of formal languages. Mos-
cow: Binom, 2006.
6. S. Ginsburg, The mathematical theory of context-free languages. Moscow: Mir,
1970.
7. J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to automata theory, lan-
guages, and computation, 2nd ed. Moscow: Williams Publishing House, 2002.
8. V.M. Statkevych, “Regular expressions for producer/consumer Petri net languages
with bounded buffer of size 1 and 2”, in 19th Int. Conf. on System Analysis and In-
formation Technology (SAIT), Kyiv, Educational and Scientific Complex “Institute
for Applied System Analysis” of National Technical University of Ukraine “Kyiv
Polytechnic Institute”, 22–25 May 2017, pp. 123.
9. V. Statkevych, “On regular expressions for producer/consumer Petri net languages
with bounded buffer”, in 4th Int. Scientific Conf. Nonlinear Analysis and Applica-
tions on memory of corresponding member of National Academy of Science of
Ukraine V.S. Mel’nik, Kyiv, National Technical University of Ukraine “Kyiv Poly-
technic Institute”, 4–6 Apr. 2018, pp. 68.
10. V. Mukhin and V. Statkevych, “On one context-free language for pro-
ducer/consumer Petri net with the unbounded buffer”, in 15th Int. Conf. on Devel-
opment and Application Systems (DAS), Suceava, Romania, 21–23 May 2020,
pp. 137–140. doi: 10.1109/DAS49615.2020.9108948
11. M.Z. Zgurovsky and V.A. Denisenko, Discrete-continuous systems with controlled
structure. Theory, modeling, applications. Kiev: Naukova Dumka, 1998.
12. A. Salomaa, Jewels of formal language theory. Moscow: Mir, 1986.
13. R. Valk and G. Vidal-Naquet, “Petri nets and regular languages”, Journal of Com-
puter and System Sciences, vol. 23, issue 3, pp. 299–325, 1981.
14. A. Gronewold and H. Fleischhack, “Computing Petri net languages by reductions”,
in 10th Int. Conf. Fundamentals of computation theory (FCT), Drezden, Germany,
Springer, 22–25 Aug. 1995, pp. 253–262. doi: 10.1007/3-540-60249-6_57
15. S.V. Baumgertner and B.F. Melnikov, “Multi-heuristic approach for the star-height
minimization of non-deterministic finite automata”, Proceedings of Voronezh State
University. Series: Systems analysis and information technologies, no. 1, pp. 5–7,
2010.
|
| id | journaliasakpiua-article-221359 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:27:00Z |
| publishDate | 2020 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/36/1a8cd950d60e2de6310815e0d452f236.pdf |
| spelling | journaliasakpiua-article-2213592021-01-19T12:18:25Z Regular expressions for some Petri net languages for the producer/consumer problem Регулярные выражения для некоторых языков сетей Петри в задаче о производителе и потребителе Регулярні вирази для деяких мов мереж Петрі в задачі про постачальника та споживача Statkevych, Vitalii M. Petri net producer/consumer problem Petri net language formal language regular language finite automaton regular expression star-height сеть Петри задача о производителе и потребителе язык сети Петри формальный язык регулярный язык конечный автомат регулярное выражение высота итерации (звездная высота) мережа Петрі задача про постачальника та споживача мова мережі Петрі формальна мова регулярна мова скінченний автомат регулярний вираз висота ітерації (зіркова висота) We consider a Petri net for the producer/consumer problem (one of the classical synchronization problems) with the bounded buffer of size n and the regular formal languages Ln, generated by the net. We propose regular expressions denoting these languages in the recursive form, in case of the bounded buffer of size from 1 to 3 the explicit formulas are proposed. We transform a reachability graph into a finite automaton and use the state elimination method. We give an upper estimate for the star-height of the mentioned languages, in case of the bounded buffer of size 1 and 2 the exact values are calculated. We also consider union, intersection, Kleene closure, concatenation and set difference operations on mentioned languages. We give the finite automaton and propose regular expressions denoting the set difference of languages Ln \ L1 in the recursive form, for L2 \ L1 the explicit formula is proposed. Рассмотрены сеть Петри в задаче о производителе и потребителе (одной из классических задач синхронизации) с ограниченным буфером размера n и регулярные формальные языки Ln, которые она порождает. Для этих языков найдены регулярные выражения в рекурсивном виде, а в случаях ограниченного буфера размера от 1 до 3 — в виде явных формул. По графу достижимости построен конечный автомат, применен метод последовательного удаления вершин. Для высоты итерации (звездной высоты) указанных языков дана оценка сверху, а в случаях ограниченного буфера размера 1 и 2 найдены точные значения. Для указанных языков рассмотрены операции объединения, пересечения, замыкания Клини, конкатенации и разности. Для разности языков Ln \ L1 построен конечный автомат и найдены регулярные выражения в рекурсивном виде, а для разности L2 \ L1 — в виде явной формулы. Розглянуто мережу Петрі в задачі про постачальника та споживача (одній з класичних задач синхронізації) з обмеженим буфером розміру n і регулярні формальні мови Ln, які вона породжує. Для цих мов знайдено регулярні вирази в рекурсивному вигляді, а у випадках обмеженого буфера розміру від 1 до 3 — у вигляді явних формул. За графом досяжності побудовано скінченний автомат, застосовано метод послідовного видалення вершин. Для висоти ітерації (зіркової висоти) вказаних мов надано оцінку зверху, а у випадках обмеженого буфера розміру 1 та 2 знайдено точні значення. Для вказаних мов розглянуто операції об’єднання, перетину, замикання Кліні, конкатенації та різниці. Для різниці мов Ln \ L1 побудовано скінченний автомат і знайдено регулярні вирази в рекурсивному вигляді, а для різниці L2 \ L1 — у вигляді явної формули. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2020-12-07 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/221359 10.20535/SRIT.2308-8893.2020.3.08 System research and information technologies; No. 3 (2020); 105-123 Системные исследования и информационные технологии; № 3 (2020); 105-123 Системні дослідження та інформаційні технології; № 3 (2020); 105-123 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/221359/223560 Copyright (c) 2021 System research and information technologies |
| spellingShingle | мережа Петрі задача про постачальника та споживача мова мережі Петрі формальна мова регулярна мова скінченний автомат регулярний вираз висота ітерації (зіркова висота) Statkevych, Vitalii M. Регулярні вирази для деяких мов мереж Петрі в задачі про постачальника та споживача |
| title | Регулярні вирази для деяких мов мереж Петрі в задачі про постачальника та споживача |
| title_alt | Regular expressions for some Petri net languages for the producer/consumer problem Регулярные выражения для некоторых языков сетей Петри в задаче о производителе и потребителе |
| title_full | Регулярні вирази для деяких мов мереж Петрі в задачі про постачальника та споживача |
| title_fullStr | Регулярні вирази для деяких мов мереж Петрі в задачі про постачальника та споживача |
| title_full_unstemmed | Регулярні вирази для деяких мов мереж Петрі в задачі про постачальника та споживача |
| title_short | Регулярні вирази для деяких мов мереж Петрі в задачі про постачальника та споживача |
| title_sort | регулярні вирази для деяких мов мереж петрі в задачі про постачальника та споживача |
| topic | мережа Петрі задача про постачальника та споживача мова мережі Петрі формальна мова регулярна мова скінченний автомат регулярний вираз висота ітерації (зіркова висота) |
| topic_facet | Petri net producer/consumer problem Petri net language formal language regular language finite automaton regular expression star-height сеть Петри задача о производителе и потребителе язык сети Петри формальный язык регулярный язык конечный автомат регулярное выражение высота итерации (звездная высота) мережа Петрі задача про постачальника та споживача мова мережі Петрі формальна мова регулярна мова скінченний автомат регулярний вираз висота ітерації (зіркова висота) |
| url | https://journal.iasa.kpi.ua/article/view/221359 |
| work_keys_str_mv | AT statkevychvitaliim regularexpressionsforsomepetrinetlanguagesfortheproducerconsumerproblem AT statkevychvitaliim regulârnyevyraženiâdlânekotoryhâzykovsetejpetrivzadačeoproizvoditeleipotrebitele AT statkevychvitaliim regulârnívirazidlâdeâkihmovmerežpetrívzadačípropostačalʹnikataspoživača |