Операція різниці для регулярних мов мереж Петрі в задачі про постачальника та споживача з обмеженим буфером
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. The objective of this paper is to obtain a regular expression for the set difference of languages Ln...
Збережено в:
| Дата: | 2021 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2021
|
| Теми: | |
| Онлайн доступ: | https://journal.iasa.kpi.ua/article/view/240011 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Репозитарії
System research and information technologies| _version_ | 1866302761695444992 |
|---|---|
| author | Statkevych, Vitalii |
| author_facet | Statkevych, Vitalii |
| author_sort | Statkevych, Vitalii |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2021-09-16T11:48:22Z |
| 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. The objective of this paper is to obtain a regular expression for the set difference of languages Ln \ Lm, n > m. For this purpose, we give the finite automaton which accepts the set difference of mentioned languages, and then we use the state elimination method to obtain the regular expression in the recursive form. The main result is illustrated by the examples. In an appendix, we consider the problem with two producers and two consumers with the bounded buffer of size 1. We give a reachability graph and propose the method for obtaining the regular expression. The explicit formulas are given for the problem with two producers and one consumer and also for the problem with one producer and two consumers. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2021.2.08 |
| first_indexed | 2025-07-17T10:27:28Z |
| format | Article |
| fulltext |
В.М. Статкевич, 2021
94 ISSN 1681–6048 System Research & Information Technologies, 2021, № 2
УДК 519.711.7+519.713
DOI: 10.20535/SRIT.2308-8893.2021.2.08
ОПЕРАЦИЯ РАЗНОСТИ ДЛЯ РЕГУЛЯРНЫХ ЯЗЫКОВ
СЕТЕЙ ПЕТРИ В ЗАДАЧЕ О ПРОИЗВОДИТЕЛЕ И
ПОТРЕБИТЕЛЕ С ОГРАНИЧЕННЫМ БУФЕРОМ
В.М. СТАТКЕВИЧ
Аннотация. Рассмотрены сеть Петри в задаче о производителе и потребителе
(одной из классических задач синхронизации) с ограниченным буфером раз-
мера n и регулярные формальные языки nL , которые она порождает. Согласно
цели работы — получение регулярного выражения для разности языков
mn LL \ , mn — построен конечный автомат, допускающий разницу ука-
занных языков, далее методом исключения вершин получено регулярное вы-
ражение в рекурсивном виде. Основной результат проиллюстрирован на при-
мерах. В качестве дополнения рассмотрено задачу с двумя производителями и
двумя потребителями с ограниченным буфером размера 1. Построен граф дос-
тижимости и предложено конструкцию для получения регулярного выраже-
ния. В случае задачи с двумя производителями и одним потребителем, а также
задачи с одним производителем и двумя потребителями указаны явные формулы.
Ключевые слова: сеть Петри, задача о производителе и потребителе, язык се-
ти Петри, формальный язык, регулярный язык, конечный автомат, регулярное
выражение.
o%“" ?=е2“ C=м 2,
ƒ=меч=2ель…%г% чел%"е*= , м=2ем=2,*=,
д%*2%!= -,ƒ,*%-м=2ем=2,че“*,. …=3*
m,*%л= b=!-%л%мее",ч= `…д!ее"=
(20.03.1941–07.06.2021)
ВВЕДЕНИЕ
Сети Петри являются удобным инструментом для моделирования процес-
сов, систем и сетей [1–3]. Сеть Петри может порождать язык; в работе [1]
определены 12 классов языков и указана их взаимосвязь с формальными
языками, определяемыми иерархией Хомского (теория формальных языков
изложена, например, в работах [4–6]).
Задача о производителе и потребителе была предложена Э. Дейкстрой [1]
как одна из задач синхронизации. Существуют несколько различных вари-
антов этой задачи: с неограниченным буфером, с ограниченным буфером, с
несколькими производителями и несколькими потребителями и др.
В работе [7] рассматривалась сеть Петри в задаче о производителе и
потребителе с ограниченным буфером размера n и регулярные формальные
языки nL ( L -типа), которые она порождает. Для рассмотренных языков
были, в частности, найдены регулярные выражения в рекурсивном виде, для
разности языков 1\ LLn построен допускающий конечный автомат и найдены
Операция разности для регулярных языков сетей Петри в задаче о производителе
Системні дослідження та інформаційні технології, 2021, № 2 95
регулярные выражения в рекурсивном виде, а для разности языков
12 \ LL — в виде явной формулы.
Цель работы, продолжающей работу [7], — получение регулярного вы-
ражения для разности языков mn LL \ , mn . В качестве дополнения рас-
смотрена задача с двумя производителями и двумя потребителями с ограни-
ченным буфером размера 1; предложена конструкция для получения
регулярного выражения.
ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ
В задаче о производителе и потребителе процесс-производитель A произ-
водит объекты (фишки) и помещает их
в буфер (позицию 5p ), а процесс-
потребитель B удаляет объект из буфе-
ра и использует его. Буфер имеет огра-
ниченный размер n , следовательно
введена дополнительная позиция 5p ,
имеющая n фишек (рис. 1).
Пусть },,,{ 4321 aaaaA — алфа-
вит, *A — множество слов, т.е. конеч-
ных цепочек из *A . Каждому переходу
сети 1t , 2t , 3t и 4t сопоставим символ
алфавита 1a , 2a , 3a и 4a соответственно; последовательности запусков пе-
реходов — слово в алфавите A . Языком сети Петри L -типа называют мно-
жество всех таких слов, что после выполнения соответствующей последова-
тельности запусков переходов маркировка сети является заключительной [1];
в данной задаче полагаем, что заключительная маркировка совпадает
с начальной маркировкой 0 . Порождаемый сетью язык L -типа обозна-
чим через nL .
Множество регулярных выражений над алфавитом A определяется
стандартным образом [4–6]: 1) 0, 1 и произвольный символ Aa являются
регулярными выражениями; 2) если r и s являются регулярными выраже-
ниями, то )( sr , )( sr и *r также являются регулярными выражениями;
3) иных регулярных выражений нет. Каждое регулярное выражение r зада-
ет язык *][ ArL , определяемый рекурсивно:
1) ]0[L , }{]1[ L , }{][ aaL для произвольного символа Aa ;
2) ][][][ sLrLsrL , ][][][ sLrLsrL , ** ])[(][ rLrL .
Оператор параллельной композиции « || » определяется следующим
образом:
aaa |||| , )||()||()||( 212121 xaxbbxxabxax
для произвольных Aba , , *
21, Axx [1, с. 165].
Рис. 1. Задача о производителе и
потребителе
A B
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 96
Для всех достижимых маркировок ),,,,,( 554321 выполнены
равенства 14321 , n 55 ; одна фишка в позициях 1p либо
2p может размещаться двумя
способами, одна фишка в пози-
циях 3p либо 4p — также дву-
мя способами; n фишек в по-
зициях 5p и 5p — 1n
способами. Потому граф дости-
жимости, построенный в работе
[7], имеет )1(4)1(22 nn
маркировок и допускает пред-
ставление в виде блочной струк-
туры (рис. 2). По графу дости-
жимости построен конечный
автомат, допускающий язык nL :
маркировке ,,,,( 4321
), 55 сопоставлено состояние
542 42 q , переходу сети it —
переход автомата по символу ia ,
начальной и заключительной
маркировке ),0,0,1,0,1(0 n —
начальное и допускающее со-
стояние 0q ( Iq 0 , Fq 0 ).
Автомат имеет вид [7]
,}{},{),(},,,,{},,,{)( 004321340 qqLaaaaqqLM nnn (1)
}141,2:),,{(}240,2:),,{()( 3211 niiqaqniiqaqL iiiin
}144},1,0{4mod:),,{( 23 niiqaq ii
}342},3,2{4mod:),,{( 24 niiqaq ii (2)
(здесь и далее 4mod означает остаток от деления на 4). Следовательно,
nL — автоматный язык, потому регулярный. Регулярное выражение, задаю-
щее язык nL , представлено, в частности, в следующем виде при помощи
метода исключения вершин [7, теорема 1]:
])(1[ 43
*
1
*
111214321 aaltrsaaaaaaLL nnnnn , (3)
где регулярные выражения 1ns , 1nl , 1nt и 1nr определены рекурсивно:
310341204200 ||,,||,0 aaraaaataals , (4)
43
****
2143
*
211 )( aaslrsltrsaaaasaas kkkkkkkkkk , (5)
34
**
121 )( aarsltaat kkkkk , (6)
Рис. 2. Граф достижимости сети Петри
Операция разности для регулярных языков сетей Петри в задаче о производителе
Системні дослідження та інформаційні технології, 2021, № 2 97
43
***
12421 )()||( aaslrsltaaaal kkkkkkk , (7)
34
***
21311 )()||( aarsltrsaaaar kkkkkkk (8)
( 2,,0 nk ). Здесь 133131 || aaaaaa , 244242 || aaaaaa — регуляр-
ные выражения, каждое выражение в формулах (4)–(8) также является регу-
лярным.
РАЗНОСТЬ ФОРМАЛЬНЫХ ЯЗЫКОВ nL И mL
Рассмотрим разность языков nL и mL , mn . Регулярность mn LL \ следует
из свойств замкнутости регулярных языков (свойства замкнутости регуляр-
ных языков, см., например, [4–6]). Построим конечный автомат mnM \ , до-
пускающий язык mn LL \ , согласно следующему принципу. Буфер (позиция
5p ) имеет ограниченный размер n и буфер хотя бы в один момент времени
содержит 1m фишек. Пусть 0t — момент времени, когда впервые выпол-
нилось условие 1)( 5 mp . До такта, соответствующего моменту 0t ,
mnM \ функционирует согласно формулам (1), (2) как автомат )( mLM , до-
пускающий язык mL ; начиная с указанного такта — как автомат )( nLM ,
допускающий язык nL :
},,,,{},,,{},,{ 4321
2
34
2
0
1
34
1
0\ aaaaqqqqM nmmn
,}{},{,)},,(),,,{( 2
0
1
0
2
\
2
642
1
34
2
442
1
14
1
\ qqqaqqaq mnmmmmmn
}240,2:),,{( 1
11
11
\ miiqaq iimn
}141,2:),,{( 1
32
1 miiqaq ii
}144},1,0{4mod:),,{( 1
23
1 miiqaq ii
},342},3,2{4mod:),,{( 1
24
1 miiqaq ii
}240,2:),,{( 2
11
22
\ niiqaq iimn
}141,2:),,{( 2
32
2 niiqaq ii
}144},1,0{4mod:),,{( 2
23
2 niiqaq ii
}.342},3,2{4mod:),,{( 2
24
2 niiqaq ii
Автомат mnM \ имеет вид, показанный на рис. 3. В построенном авто-
мате состояния 1
34
1
0 ,, mqq и переходы множества 1
\mn соответствуют ав-
томату )( mLM , состояния 2
34
2
0 ,, nqq и переходы множества 2
\mn — ав-
томату )( nLM , переходы ),,( 2
442
1
14 mm qaq и ),,( 2
642
1
34 mm qaq «связывают»
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 98
две различные части. Построенный автомат является детерминированным.
Отметим, что конструкция и принцип построения конечного автомата, доу-
скающего язык 1\ LLn , была предложена в работе [7].
Построенный автомат mnM \ используем для получения регулярного
выражения для разности языков mn LL \ при помощи метода удаления вер-
шин.
Регулярное выражение для mn LL \ имеет следующий рекурсивный вид.
Теорема 1. Язык mn LL \ , mn имеет вид ][\ \mnmn rLLL , где
1
*
111
*
1
*
111214321\ [][ mmmmmmmmmn HtrIltrsaaaaaar
,]][)( 43
*
1
*
111214311
*
1
*
111 aaltrsaaaaltGtrR nnnnnnmmmm
а регулярные выражения 1mR , 1mI , 1mG и 1mH определены рекурсивно:
34
*
1
*
1111
*
1210 )( aarsltrsaaR mnmnmnmnmnmn , (9)
mnsI 0 , (10)
341
*
111120 )( aarsltaaG mnmnmnmn
, (11)
43
*
11
*
1
*
111120 )( aaslrsltaaH mnmnmnmnmnmn , (12)
Рис. 3. Автомат, допускающий язык mn LL \
Операция разности для регулярных языков сетей Петри в задаче о производителе
Системні дослідження та інформаційні технології, 2021, № 2 99
kmnkmnkkkkkkkkmnkmnkkkk rsHGrsltrrsIRsaaR *****
211 ()((
,))))(( 34
**** aarsltrsIRsl kmnkmnkmnkmnkmnkmnkkkk (13)
kkkkkkkkkkkk IIslHrsltrsaaI )()(( ****
211
))(()(( *****
kmnkmnkkkkkmnkmnkkkkkkk rsIRslrsHGrsltr
,)))( 43
**** aaslrsltrsIR kmnkmnkmnkmnkmnkmnkmnkmnkk (14)
kmnkmnkkkkkkk rsHGrsltaaG ***
121 ()(
,)())( 34
**** aarsltrsIRsl kmnkmnkmnkmnkmnkmnkkkk (15)
kkkkmnkmnkkkkkkkkkkk RslrsHGIslHrsltaaH ((()( *****
121
43
**** ))))( aaslrsltrsI kmnkmnkmnkmnkmnkmnkmnkmnk (16)
(здесь 2,,0 mk , а в формуле (11) использована запись eee * ,
см. например, [4, 5]).
Доказательство теоремы проведем в несколько шагов.
Шаг 1. Рассмотрим автомат mnM \ . Удаляя в каждом из 2 nm бло-
ков ( 1m блоков в левом столбце рис. 3 и 1n блоков в правом) левое
нижнее и правое верхнее состояния, т.е. состояния 1
iq , }2,1{4mod i ,
241 mi и 2
jq , }2,1{4mod j , 241 nj , и используя оператор па-
раллельной композиции « || », получаем обобщенный автомат
},,,,,,,{},,,,,,{ 2
34
2
4
2
7
2
4
2
3
2
0
1
34
1
4
1
7
1
4
1
3
1
01 nnmm qqqqqqqqqqqqM
),,,{(},,,,{ 2
4421
1
4
1
4321 mmm qaaqaaaa
,}{},{,)},||,(),,,( 2
0
1
0
22
4442
1
34
2
7412
1
34 qqqaaqqaaq nmmmm
}44,,4,0:),,{( 421 Niqaaq p
i
p
i
p
N
}44,,4,0:),,{( 434 Niqaaq p
i
p
i
}14,,7,3:),,{(}14,,7,3:),,{( 344412 NiqaaqNiqaaq p
i
p
i
p
i
p
i
}4,,8,4:),||,{( 131 Niqaaq p
i
p
i
},4,,8,4:),||,{( 421 Niqaaq p
i
p
i 2,1p .
Введенное обозначение p
N ( 2,1p ) для различных 0N будет ис-
пользовано далее при доказательстве теоремы (в случае 0N полагаем
p
0 ). Подробно метод исключения состояний изложен, например, в ра-
ботах [4–6].
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 100
Шаг 2. Сначала рассмотрим случай 3 mn .
2а. Удаляем состояние 2
34 nq , тем самым добавляя петлю
),,( 2
143412
2
14 nn qaaaaq , добавляем петлю ),0,( 2
4
2
4 nn qq и вводим обозначе-
ния (4).
2б. Множеству переходов полученного автомата принадлежат, в том
числе, переходы
),,,(),,,(),,,( 2
40
2
4
2
4443
2
4
2
421
2
44 nnnnnn qsqqaaqqaaq
),,(),,,( 2
40
2
14
2
140
2
4 nnnn qlqqrq , (17)
),,(),,,(),,,( 2
140
2
14
2
5434
2
14
2
1412
2
54 nnnnnn qtqqaaqqaaq . (18)
Удаляем состояние 2
4nq . Тогда из множества переходов удаляются пе-
реходы (17), а добавляются переходы
),,,(),,,( 2
140
*
021
2
44
2
4443
*
021
2
44 nnnn qrsaaqqaasaaq
),,(),,,( 2
140
*
00
2
14
2
4443
*
00
2
14 nnnn qrslqqaaslq ; (19)
объединение двух параллельных петель — третьего перехода из формулы (18)
и четвертого перехода из формулы (19) — дает петлю 0
2
14 ,( tq n
), 2
140
*
00 nqrsl . Аналогичными рассуждениями удаление состояния 2
14 nq ,
объединение параллельных переходов и введение регулярных выражений
1s , 1t , 1l и 1r согласно формулам (5)–(8) приводит к добавлению переходов
),,(),,,(),,,(),,,( 2
441
2
54
2
541
2
44
2
541
2
54
2
441
2
44 nnnnnnnn qlqqrqqtqqsq .
Предложенную процедуру удаления состояний 2
4nq и 2
14 nq обозначим
через ),(DEL 2
14
2
4 nn qq .
2в. Выполняя аналогичную пункту 2б процедуру 2mn раз, т.е. уда-
ляя состояния в порядке 2
4nq , 2
14 nq , …, 2
114 mq и используя рекурсивные
формулы (5)–(8), получаем автомат
},,,,,,,{},,,,,,{ 2
84
2
74
2
7
2
4
2
3
2
0
1
34
1
4
1
7
1
4
1
3
1
02 mmmm qqqqqqqqqqqqM
,}{},{,},,,,{ 2
0
1
024321 qqaaaa
)},||,(),,,(),,,{( 2
4442
1
34
2
7412
1
34
2
4421
1
4
1
2 mmmmmmm qaaqqaaqqaaq
),,,(),,,(),,,{( 2
7412
2
34
2
4443
2
84
2
8421
2
44
2
1 mmmmmmm qaaqqaaqqaaq
),,,(),,,(),,,( 2
742
2
74
2
842
2
84
2
3434
2
74 mmnmmmnmmm qtqqsqqaaq
)}.,,(),,,( 2
842
2
74
2
742
2
84 mmnmmmnm qlqqrq
Теперь рассмотрим случай 2 mn и автомат 1M , полученный на ша-
ге 1. Выполняя предложенные в пункте 2а действия и не выполняя анало-
Операция разности для регулярных языков сетей Петри в задаче о производителе
Системні дослідження та інформаційні технології, 2021, № 2 101
гичную пункту 2б процедуру ни одного раза, получаем автомат, совпадаю-
щий с автоматом 2M .
Заметим, что рассуждения пунктов 2а, 2б и 2в были предложены в ра-
боте [7] при доказательстве теоремы 1 [7].
Шаг 3. Сначала рассмотрим случай 2 mn и автомат 2M , получен-
ный на шаге 2. Последовательно удаляем состояния 2
84 mq и 2
74 mq . Укажем
дополнения к аналогичной пункту 2б процедуре ),(DEL 2
74
2
84 mm qq :
при удалении состояния 2
74 mq дополнительно удаляется переход
),,( 2
7412
1
34 mm qaaq , а также дополнительно добавляются два перехода
),,)(,( 2
4443
*
22
*
2
*
22212
1
34 mmnmnmnmnmnmnm qaaslrsltaaq
),,)(,( 2
34134
*
2
*
22212
1
34 mmnmnmnmnmnm qtaarsltaaq
первый из которых объединяем с существующим параллельным
),||,( 2
4442
1
34 mm qaaq и используем формулу (7). Таким образом, получаем
автомат
},,,,,,,{},,,,,,{ 2
44
2
34
2
7
2
4
2
3
2
0
1
34
1
4
1
7
1
4
1
3
1
03 mmmm qqqqqqqqqqqqM
,}{},{,},,,,{ 2
0
1
034321 qqaaaa
)},,(),,,(),,,{( 2
441
1
34
2
341
1
34
2
4421
1
4
1
3 mmnmmmnmmmm qlqqtqqaaq
),,,(),,,(),,,{( 2
441
2
44
2
443
2
44
2
4421
2
4
2
mmnmmmmmm qsqqaaqqaaq
)}.,,(),,,(),,,( 2
441
2
34
2
341
2
44
2
341
2
34 mmnmmmnmmmnm qlqqrqqtq
Теперь рассмотрим случай 1 mn и автомат 1M , полученный на шаге 1.
Удаляем состояние 2
74 mq , тем самым добавляя переход 3412
1
34 ,( aaaaq m
), 2
3410 mmn qtt и петлю ),,( 2
34103412
2
34 mmnm qttaaaaq , добавляем
петлю ),0,( 2
4410
2
44 nmnn qssq и получаем автомат, совпадающий с ав-
томатом 3M .
Шаг 4. Рассмотрим автомат 3M , полученный на шаге 3. Последова-
тельно удаляем состояния 2
44 mq и 2
34 mq . Укажем дополнения к аналогич-
ной пункту 2б процедуре ),(DEL 2
34
2
44 mm qq . При удалении состояния
2
44 mq дополнительно удаляются два перехода ),,( 2
4421
1
4 mm qaaq и
),,( 2
441
1
34 mmnm qlq , а также дополнительно добавляются переходы
),,,(),,,( 2
341
*
121
1
4
2
443
*
121
1
4 mmnmnmmmnm qrsaaqqaasaaq
),,,(),,,( 2
341
*
11
1
34
2
443
*
11
1
34 mmnmnmnmmmnmnm qrslqqaaslq
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 102
последний из которых объединяем с существующим параллельным
),,( 2
341
1
34 mmnm qtq . Аналогичными рассуждениями удаление состояния
2
34 mq , объединение параллельных переходов и учет формул (5), (7), (8)
приводит к автомату
},,,,,,,{},,,,,,{ 2
4
2
14
2
7
2
4
2
3
2
0
1
34
1
4
1
7
1
4
1
3
1
04 mmmm qqqqqqqqqqqqM
,}{},{,},,,,{ 2
0
1
044321 qqaaaa
34
*
1
*
1111
*
121
1
4
1
4 )(,{( aarsltrsaaq mnmnmnmnmnmnmm
),, 2
14 mmn qr
43
*
11
*
1
*
111
1
34
2
4
1
4 )(,(),,,( aaslrsltqqsq mnmnmnmnmnmnmmmnm
),, 2
4mmn ql
),,,{()},)(,( 2
421
2
44
2
1
2
14341
*
111
1
34 mmmmmnmnmnmnm qaaqqaarsltq
),,,(),,,(),,,( 2
14
2
14
2
4
2
4
2
4443
2
4 mmnmmmnmmm qtqqsqqaaq
)}.,,(),,,( 2
4
2
14
2
14
2
4 mmnmmmnm qlqqrq
Заметим, что в переходе
)(,( 1
*
111
1
34 mnmnmnmnm rsltq
), 2
1434 mqaa использована запись eee * , см. например, [4, 5]; в случае
1m множество
2
1m согласно шагу 1.
Теперь удаляем состояние 1
34 mq , тем самым добавляя три перехода,
среди которых петля ),,( 1
143412
1
14 mm qaaaaq , добавляем петлю ),0,( 1
4
1
4 mm qq
и вводим обозначения (4). Также вводим обозначения 0R , 0I , 0G и 0H со-
гласно формулам (9)–(12), получая автомат
},,,,,,,{},,,,,,{ 2
4
2
14
2
7
2
4
2
3
2
0
1
4
1
14
1
7
1
4
1
3
1
05 mmmm qqqqqqqqqqqqM
,}{},{,},,,,{ 2
0
1
054321 qqaaaa
),,,(),,,(),,,{( 1
40
1
4
1
4443
1
4
1
421
1
44
1
15 mmmmmmm qsqqaaqqaaq
)},,(),,,(),,,( 1
40
1
14
1
140
1
4
1
140
1
14 mmmmmm qlqqrqqtq
)},,(),,,(),,,(),,,{( 2
40
1
14
2
140
1
14
2
40
1
4
2
140
1
4 mmmmmmmm qHqqGqqIqqRq
),,,(),,,(),,,{( 2
4
2
4
2
4443
2
4
2
421
2
44
2
1 mmnmmmmmm qsqqaaqqaaq
)}.,,(),,,(),,,( 2
4
2
14
2
14
2
4
2
14
2
14 mmnmmmnmmmnm qlqqrqqtq
Операция разности для регулярных языков сетей Петри в задаче о производителе
Системні дослідження та інформаційні технології, 2021, № 2 103
Заметим, что в случае 1m множества
2
1
1
1 mm согласно ша-
гу 1. Укажем связь построенного автомата с рис. 3: левый и правый столбцы
выровнены по высоте, а четыре перехода, «связывающие» левый и правый
столбцы, названы по первым четырем буквам слова «right», так как ведут
слева направо.
Шаг 5. Рассмотрим автомат 5M , полученный на шаге 4.
5а. Сначала рассмотрим случай 1m . Последовательно удаляем со-
стояния 2
4mq и 2
14 mq . Укажем дополнения к аналогичной пункту 2б проце-
дуре ),(DEL 2
14
2
4 mm qq : дополнительно удаляются четыре перехода
),,( 2
140
1
4 mm qRq , ),,( 2
40
1
4 mm qIq , ),,( 2
140
1
14 mm qGq и ),,( 2
40
1
14 mm qHq , а также
дополнительно добавляются четыре перехода
),))((,( 2
5434
***
00
1
4 mmnmnmnmnmnmnm qaarsltrsIRq , (20)
),)))(((,( 2
4443
****
000
1
4 mmnmnmnmnmnmnmnmnm qaaslrsltrsIRIq , (21)
),))((,( 2
5434
***
00
1
14 mmnmnmnmnmnmnm qaarsltrsHGq , (22)
mnmnmnm trsHGHq )(((,( *
000
1
14
),)) 2
4443
***
mmnmnmnmnmn qaaslrsl . (23)
Теперь последовательно удаляем состояния 1
4mq и 1
14 mq . Укажем до-
полнения к аналогичной пункту 2б процедуре ),(DEL 1
14
1
4 mm qq : дополни-
тельно удаляются переходы (20)–(23), объединение параллельных перехо-
дов и введение регулярных выражений 1R , 1I , 1G и 1H согласно формулам
(13)–(16) приводит к добавлению переходов ),,( 2
541
1
44 mm qRq ,
),,( 2
441
1
44 mm qIq , ),,( 2
541
1
54 mm qGq и ),,( 2
441
1
54 mm qHq .
5б. Выполняя аналогичную пункту 5а процедуру 1m раз, т.е. удаляя
состояния в порядке 2
4mq , 2
14 mq , 1
4mq , 1
14 mq , …, 2
8q , 2
7q , 1
8q , 1
7q и используя
рекурсивные формулы (20)–(23), получаем автомат
}{},{,},,,,{},,,,,,{ 2
0
1
064321
2
4
2
3
2
0
1
4
1
3
1
06 qqaaaaqqqqqqM ,
),,,(),,,(),,,(),,,(),,,{( 1
31
1
4
1
31
1
3
1
41
1
4
1
043
1
4
1
421
1
06 qrqqtqqsqqaaqqaaq mmm
)},,(),,,(),,,(),,,{()},,( 2
41
1
3
2
31
1
3
2
41
1
4
2
31
1
4
1
31
1
3 qHqqGqqIqqRqqlq mmmmm
),,,(),,,(),,,(),,,{( 2
31
2
3
2
41
2
4
2
043
2
4
2
421
2
0 qtqqsqqaaqqaaq nn
)}.,,(),,,( 2
31
2
3
2
31
2
4 qlqqrq nn
Теперь заметим, что в случае 1m автомат 5M , полученный на ша-
ге 4, совпадает с автоматом 6M и выполнение аналогичной пункту 5а про-
цедуры не требуется.
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 104
Шаг 6. Заменяем автомат 6M на эквивалентный, удаляя переходы
),,( 1
043
1
4 qaaq , ),,( 2
421
2
0 qaaq и добавляя петли ),,( 1
42143
1
4 qaaaaq ,
),,( 2
42143
2
4 qaaaaq . Последовательно удаляем состояния 1
3q , 2
3q и получаем
автомат
}{},{,},,,,{},,,,{ 2
0
1
074321
2
4
2
0
1
4
1
07 qqaaaaqqqqM ,
),,,(),,,{( 1
41
*
1112143
1
4
1
421
1
07 qltrsaaaaqqaaq mmmm
),,)(,( 2
41
*
11
*
1111
*
111
1
4 qltGtrRHtrIq nnmmmmmmmm
)}.,,(),,,( 2
043
2
4
2
41
*
1112143
2
4 qaaqqltrsaaaaq nnnn
Последовательным удалением состояний 1
4q и 2
4q получаем искомое ре-
гулярное выражение mnr \ , что завершает доказательство теоремы.
Замечание 1. Сравнение полученного регулярного выражения mnr \ с
формулой (3) в контексте рис. 3 выявляет общее регулярное выражение
*
1
*
1112143 )( nnnnn ltrsaaaar , порожденное «сворачиванием одного
столбца высоты 22 n ». Формула (3) использует nr один раз, а mnr \ — два
экземпляра mr и nr для сворачивания левого столбца высоты 22 m и пра-
вого столбца высоты 22 n соответственно. Два экземпляра mr и nr разде-
лены регулярным выражением, отвечающим за «связывание» левого и пра-
вого столбцов.
Для языка 12 \ LL регулярное выражение найдено в работе [7] (пример 4).
Пример 1. Рассмотрим 1m и язык 1\ LLn . Из теоремы 1 и форму-
лы (4) следует
34
*
2
*
2222
*
2210 )( aarsltrsaaR nnnnnn , 10 nsI ,
342
*
222120 )( aarsltaaG nnnn
,
43
*
22
*
2
*
222120 )( aaslrsltaaH nnnnnn ,
*
42
*
3412312143211\ )]||())(||([ aaaaaaaaaaaaaarn
43
*
22
*
2
*
22212
*
3412311 )())(||([ aaslrsltaaaaaaaas nnnnnnn
34
*
2
*
2222
*
221 )(( aarsltrsaa nnnnnn
]))())(||( 1
*
1342
*
22212
*
341231 nnnnnn ltaarsltaaaaaaaa
43
*
1
*
1112143 ][ aaltrsaaaa nnnn
*
42
*
341231214321 )]||())(||([ aaaaaaaaaaaaaa
43
*
22
*
2
*
222
*
123412311 )()()||([ aaslrsltaaaaaaaas nnnnnnn
Операция разности для регулярных языков сетей Петри в задаче о производителе
Системні дослідження та інформаційні технології, 2021, № 2 105
))()()||(( 2
*
222
*
123412312
*
221 nnnnnn rsltaaaaaaaarsaa
.]][)( 43
*
1
*
11121431
*
134
*
2
*
222 aaltrsaaaaltaarslt nnnnnnnnnn
Данное регулярное выражение совпадает с регулярным выражением
1\nr , полученным в работе [7] (следствие 3).
Пример 2. Рассмотрим случай 3n , 2m и язык 23 \ LL . Искомое ре-
гулярное выражение имеет вид
1
*
111
*
1
*
1112143212\3 [][ HtrIltrsaaaaaar
43
*
2
*
222214322
*
1
*
111 ]][)( aaltrsaaaaltGtrR .
Проиллюстрируем нахождение регулярных выражений 1R , 1I , 1G и
1H согласно рекурсивным формулам (9)–(16). Из формул (4)–(8) следует
4342
*
31423412312143211 )||())||)(||()(||( aaaaaaaaaaaaaaaaaaaas ,
34
*
31423412121 ))||)(||(( aaaaaaaaaaaat ,
4342
*
3142341212421 )||())||)(||(()||( aaaaaaaaaaaaaaaal ,
34
*
314234123121311 ))||)(||()(||()||( aaaaaaaaaaaaaaaar .
Из теоремы 1 получаем
134
*
3142341231210 ))||)(||()(||( raaaaaaaaaaaaaaR ,
4342
*
314234123121432110 )||())||)(||()(||( aaaaaaaaaaaaaaaaaaaasI ,
3431423412120 ))||)(||(( aaaaaaaaaaaaG ,
14342
*
31423412120 )||())||)(||(( laaaaaaaaaaaaaaH ,
*
3142341231110211 ))||)(||()(||(( aaaaaaaaaarsRaaR
,))))()(||(( 34
*
1
*
111110421
*
100 aarsltrsRaarsHG
11420
*
3142341231211 ))||(())||)(||()(||(( ssaaHaaaaaaaaaaaaI
)))(||(())||)(||()(||(( 110421
*
100
*
3142341231 rsRaarsHGaaaaaaaaaa
,)))( 43
*
11
*
1
*
111110 aaslrsltrsR
1
*
100
*
31423412121 ())||)(||(( rsHGaaaaaaaaaaG
,)))()(||( 34
*
1
*
11111042 aarsltrsRaa
1420
*
31423412121 )||(())||)(||(( saaHaaaaaaaaaaH
.))))()(||(( 43
*
11
*
1
*
111110421
*
100 aaslrsltrsRaarsHG
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 106
Замечание 2. Напомним, что высотой итерации или звездной высотой
rsh регулярного выражения r называется наибольшая глубина вложения
операции замыкания Клини, а высотой итерации регулярного языка Lsh —
наименьшая из высот итераций регулярных выражений, задающих язык L
[5, 8]. В работе [7] получены равенства 2shsh 21 LL и оценка
32sh nLn ( 3n ), а также равенство nmn LLL sh)\sh( . Потому получа-
ем оценку 32)\sh( nLL mn ( 3n ).
Замечание 3. Граф автомата )( nLM имеет 44 n вершин и 48 n ре-
бер, что следует из формул (1), (2), граф автомата mnM \ — 844 nm вер-
шин и 1088 nm ребер. Потому данные графы являются разреженными
(каждая вершина имеет не более двух смежных ей вершин с учетом ориен-
тации ребер) и для хранения их в памяти компьютера удобно использовать
списки смежности [9]. Для представления ориентированного графа
EVG , с ||V вершинами и || E ребрами в виде списков смежности тре-
буемый объем памяти |)||(| EVO [9], потому с учетом mn получаем,
что для представления автоматов )( nLM и mnM \ в виде списков смежности
требуемый объем памяти компьютера )(nO , т.е. линейно зависит от размера
буфера сети Петри. Временна́я сложность построения автомата также )(nO .
ДОПОЛНЕНИЕ: ЗАДАЧА С ДВУМЯ ПРОИЗВОДИТЕЛЯМИ И ДВУМЯ
ПОТРЕБИТЕЛЯМИ С ОГРАНИЧЕННЫМ БУФЕРОМ РАЗМЕРА 1
Рассмотрим задачу с двумя производителями и двумя потребителямии с ог-
раниченным буфером размера 1, когда в позициях 1p и 3p (см. рис. 1) в на-
чальной маркировке 0 имеются по две фишки. Для всех достижимых мар-
кировок ),,,,,( 554321 выполняются равенства 321
24 , 155 ; две фишки в позициях 1p и 2p могут размещаться
тремя способами, две фишки в позициях 3p и 4p — также тремя способа-
ми, одна фишка в позициях 5p либо 5p — двумя способами. Потому граф
достижимости имеет 18233 маркировок и допускает представление в
виде блочной структуры. Поставим вопрос нахождения регулярного выра-
жения для языка L -типа, который порождает данная сеть (заключительная
маркировка, как и ранее, совпадает с 0 ). По графу достижимости стро-
им конечный автомат, изображенный на рис. 4: маркировке
),,,,,( 554321 сопоставляем состояние 5
42
q , переходу сети it —
переход автомата по символу ia , начальной маркировке )1,0,0,2,0,2(0 —
начальное состояние 0
00q автомата. Автомат имеет вид
}{},{,},,,,{},1,0;2,1,0;2,1,0:{ 0
00
0
00143211 qqaaaakjiqM k
ij ,
}1,0;2,1,0;1,0:),,{( ,111 kjiqaq k
ji
k
ij
}1,0;2,1,0:),,{(}2,1,0;2,1:),,{( 0
1,3
11
,12
0 jiqaqjiqaq jiijjiij
Операция разности для регулярных языков сетей Петри в задаче о производителе
Системні дослідження та інформаційні технології, 2021, № 2 107
}.1,0;2,1;2,1,0:),,{( 1,4 kjiqaq k
ji
k
ij
Здесь состоянию автомата k
ijq отвечает маркировка сети
)1,,,2,,2( kkjjii , множество переходов 1 содержит 36 переходов.
Заметим, что состояния k
ijq в случае }1,0{,, kji отвечают задаче с одним
производителем и одним потребителем, в случае }2,1,0{i , }1,0{, kj —
задаче с двумя производителями и одним потребителем, в случае }1,0{, ki ,
}2,1,0{j — задаче с одним производителем и двумя потребителями, а со-
стояния 0
22q и 1
22q образованы «интерференцией» двух производителей и
двух потребителей. Рис. 4 имеет форму куба, где верхняя плоскость отвеча-
ет блоку 0 ( 0k ), а нижняя — блоку 1 ( 1k ).
Удаляем состояния k
ijq , 2 ji , т.е. состояния 0
01q , 0
10q , 0
21q , 0
12q , 1
01q ,
1
10q , 1
21q и 1
12q , объединяем параллельные переходы и используем записи
133131 || aaaaaa , 144141 || aaaaaa ,
244242 || aaaaaa , 344343 || aaaaaa :
}{},{,},,,,{},1,0:,,,,{ 0
00
0
0022432122201102002 qqaaaakqqqqqM kkkkk ,
),,,(),,,(),,,(),,,{( 1
22
2
1
1
02
1
20
2
1
1
00
0
22
2
1
0
02
0
20
2
1
0
002 qaqqaqqaqqaq
),,,(),,,(),,,(),,,( 1
20
2
4
1
22
1
00
2
4
1
02
0
20
2
4
0
22
0
00
2
4
0
02 qaqqaqqaqqaq
),,,(),,,(),,,(),,,( 1
0223
1
11
1
1123
1
20
0
0232
0
11
0
1132
0
20 qaaqqaaqqaaqqaaq
)},,||,(),,||,(),,||,(),,||,( 1
2041
1
11
1
1141
1
02
0
2041
0
11
0
1141
0
02 qaaqqaaqqaaqqaaq
),,,(),,,(),,,(),,,{( 1
2212
0
22
1
2012
0
20
1
0221
0
02
1
0021
0
002 qaaqqaaqqaaqqaaq
),,,(),,,(),,,(),,,( 0
2234
1
22
0
0234
1
02
0
2043
1
20
0
0043
1
00 qaaqqaaqqaaqqaaq
Рис. 4. Задача с двумя производителями и двумя потребителями
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 108
),,||,(),,||,(),,||,(),,||,( 0
2231
1
11
0
1131
1
00
1
1142
0
22
1
0042
0
11 qaaqqaaqqaaqqaaq
)}.,||,(),,||,( 0
1143
1
11
1
1121
0
11 qaaqqaaq
Множество 2 содержит 16 переходов внутри одного блока 0 и внутри
одного блока 1, а множество 2 — 14 переходов между двумя блоками.
Для дальнейших рассуждений используем следующую лемму.
Лемма 1. Пусть Atzyx ,,, . Тогда выполняются равенства:
а) yzxyxzxyzyzx || ;
б) zyxtzxytxzytyztxyzxtyxztxyztztyx )||(||
ztyxztxyzxtyxztyzytx ;
в) yzxxzxyzyxzxyxxzyxyzxyxzxxyzxzxyx 222)||(|| ;
г) 222)||(|| yzxyxzxzyxxyzxxyxzyzxyzxx ;
д) xzyxxzxyzyxxyzxyzxyxzxzyxxyxzxzyx 222)||(|| ;
е) 222222)||(||)||( xyxxyyxyxyyxyxxyxyyxyx .
Доказательство каждого пункта леммы основано на определении опе-
ратора параллельной композиции «||» и не вызывает затруднений. Заметим,
что приоритет оператора параллельной композиции ниже, чем оператора
конкатенации. Также заметим, что правая часть каждого равенства является
регулярным выражением, задающим конечный язык, потому и регулярный
язык.
В автомате 2M удаляем состояния 0
20q , 0
02q , 1
00q , 1
11q , 1
22q и объединя-
ем параллельные переходы с использованием леммы 1, получая автомат
}{},{,},,,,{},,,,,{ 0
00
0
0034321
1
02
1
20
0
22
0
11
0
003 qqaaaaqqqqqM ,
),,)||(,(),,,{( 0
1123211
0
00
0
0014321
0
003 qeaaaaqqeaaaaq
),,)||(,(),,)||(,( 0
0044324
0
11
1
2031211
0
00 qeaaaaqqeaaaaq
),,)||)(||(,(),,)||(||,( 0
2263121
2
132
0
11
0
1153241
0
11 qeaaaaaaaqqeaaaaq
),,)||(,(),,)||(||,( 1
0282321
0
11
1
2071241
0
11 qeaaaaqqeaaaaq
),,)||)(||(,( 0
119434232
2
4
0
22 qeaaaaaaaq
),,)||)(||(,( 0
221031423412
0
22 qeaaaaaaaaq
),,)||(,(),,)||(||,( 1
02122342
0
22
1
20111244
0
22 qeaaaaqqeaaaaq
),,)||(,(),,)||(,( 0
22143123
1
20
0
11133243
1
20 qeaaaaqqeaaaaq
),,)(,(),,)||(,( 1
0216
2
23
1
20
1
20151243
1
20 qeaaqqeaaaaq
),,)||(||,(),,)||(,( 0
11183414
1
02
0
00174434
1
02 qeaaaaqqeaaaaq
Операция разности для регулярных языков сетей Петри в задаче о производителе
Системні дослідження та інформаційні технології, 2021, № 2 109
),,)||(||)||(,(),,)||(||,( 1
20204141
1
02
0
22193411
1
02 qeaaaaqqeaaaaq
).,)||(,( 1
02212341
1
02 qeaaaaq
Множество переходов 3 содержит 21 переход. Отметим, что пункт а)
леммы был использован для получения регулярных выражений 2e , 4e , 8e ,
13e , 15e и 21e , например,
)||()()||( 32111323123211312132
2
12 aaaaaaaaaaaaaaaaaaaaae ;
пункты б), в), д) и е) — для получения выражений
)||)(||()||()||( 3142324141325 aaaaaaaaaaaae
),||(||)||)(||( 32414321 aaaaaaaa
)||(||)||)(||()||()||( 12414121
2
14212417 aaaaaaaaaaaaaaae ,
)||(||)||()||)(||()||( 34144134434131
2
418 aaaaaaaaaaaaaaae ,
)||(||)||()||( 4141
2
41
2
1
2
4
2
4
2
120 aaaaaaaaaae
соответственно; пункт г) — для получения выражений 11e и 19e , например,
)||(||)||)(||( 12444142
2
41212
2
411 aaaaaaaaaaaaaae .
Дальнейшим последовательным удалением состояний в порядке 1
20q ,
1
02q , 0
22q и 0
11q можно получить регулярное выражение. Предложенный по-
рядок удаления обусловлен такими рассуждениями: автомат 3M не содер-
жит состояний k
ijq c пустыми петлями ),0,( k
ij
k
ij qq ; выражения 15e , 21e , 10e и
5e , отвечающие петлям ),,( 1
2015
1
20 qeq , ),,( 1
0221
1
02 qeq , ),,( 0
2210
0
22 qeq и
),,( 0
115
0
11 qeq , имеют 3, 3, 5 и 12 слагаемых соответственно. Также отметим,
что автомат 3M имеет лишь 4 пустых перехода ),0,( 0
22
0
00 qq , ),0,( 1
02
0
00 qq ,
),0,( 0
00
0
22 qq и ),0,( 0
00
1
20 qq , а после удаления состояний 1
20q и 1
02q получае-
мый автомат на трех состояниях },,{ 0
22
0
11
0
00 qqq является полным.
Рассмотрим предложенную конструкцию на двух примерах.
Пример 3 (задача с двумя производителями и одним потребителем с
ограниченным буфером размера 1). Граф достижимости имеет 12223
маркировок, а автомат 1M , как отмечалось выше, модифицируется с учетом
условия }1,0{j . Удалением состояний k
ijq , 2 ji , т.е. состояний 0
01q , 0
10q ,
0
21q , 1
01q , 1
10q и 1
21q получаем автомат
}{},{,},,,,{},1,0:,,{ 0
00
0
002243212011002 qqaaaakqqqM kkk ,
),,,(),,,(),,,{( 0
1132
0
20
1
20
2
1
1
00
0
20
2
1
0
002 qaaqqaqqaq
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 110
)},,||,(),,||,(),,,( 1
2041
1
11
0
2041
0
11
1
1123
1
20 qaaqqaaqqaaq
),,,(),,,(),,,(),,,{( 0
2043
1
20
0
0043
1
00
1
2012
0
20
1
0021
0
002 qaaqqaaqqaaqqaaq
)}.,,(),,||,(),,||,(),,||,( 0
1134
1
11
1
1121
0
11
0
1131
1
00
1
0042
0
11 qaaqqaaqqaaqqaaq
Удалением состояний 0
20q , 1
00q , 1
11q и объединением параллельных пе-
реходов с использованием леммы 1 получаем автомат
}{},{,},,,,{},,,{ 0
00
0
0034321
1
20
0
11
0
003 qqaaaaqqqM ,
),,)||(,(),,,{( 0
1123211
0
00
0
0014321
0
003 qeaaaaqqeaaaaq
),,)||(,(),,)||(,( 0
0044342
0
11
1
2031211
0
00 qeaaaaqqeaaaaq
),,)||(||,(),,)||())||(||(,( 1
2061241
0
11
0
11513423421
0
11 qeaaaaqqeaaaaaaaaq
).,)||(,(),,)||(,( 1
2081243
1
20
0
1173423
1
20 qeaaaaqqeaaaaq
Отметим, что пункт а) леммы был использован для получения регуляр-
ных выражений 2e и 8e , пункт в) — для получения выражения 6e , а выра-
жение 5e получено следующим образом:
3421314232415 )||()||)(||()||( aaaaaaaaaaaae
3412421124142214241 )( aaaaaaaaaaaaaaaaaaa
.)||())||(||()||( 134234211342 aaaaaaaaaaaa
Последовательно удаляя состояния 1
20q и 0
11q , получаем искомое регу-
лярное выражение
))||()]||([)||()||(([ 3423
*
1243121132114321 aaaaaaaaaaaaaaaaaaaa
))||(||()||())||(||[( 124113423421 aaaaaaaaaaaa
*
4342
*
3423
*
1243 ])||(])||()]||([ aaaaaaaaaaaa
высотой итерации 3, откуда следует, что высота итерации соответствующе-
го языка не превышает 3.
Пример 4 (задача с одним производителем и двумя потребителями с
ограниченным буфером размера 1). Граф достижимости также имеет
12232 маркировок, автомат 1M модифицируется с учетом условия
}1,0{i . Удаляем состояния k
ijq , 2 ji , т.е. состояния 0
01q , 0
10q , 0
12q , 1
01q ,
1
10q и 1
21q , затем последовательно — состояния 0
02q , 1
00q , 1
11q , 1
02q и 0
11q
(рассуждения аналогичны примеру 3). Искомое регулярное выражение
имеет вид
)||())||(||()[||([ 3124431231214321 aaaaaaaaaaaaaaaa
*
3414
*
23412312 ))]||(||(])||[()||( aaaaaaaaaaaa
Операция разности для регулярных языков сетей Петри в задаче о производителе
Системні дослідження та інформаційні технології, 2021, № 2 111
,)])||(])||[()||()||(( *
4434
*
234123124324 aaaaaaaaaaaaaaaa
его высота итерации также равна 3, потому высота итерации соответствую-
щего языка не превышает 3.
ВЫВОДЫ
Получено регулярное выражение для разности формальных языков mn LL \ ,
mn , где nL — регулярный формальный язык, порождаемый сетью Петри
в задаче о производителе и потребителе с ограниченным буфером разме-
ра n . В качестве дополнения предложена конструкция для получения регу-
лярного выражения для формального языка, порождаемого сетью Петри в
задаче с двумя производителями и двумя потребителями с ограниченным
буфером размера 1.
ЛИТЕРАТУРА
1. Дж. Питерсон, Теория сетей Петри и моделирование систем. М.: Мир, 1984,
264 c.
2. В.Е. Котов, Сети Петри. М.: Наука, Гл. ред. физ.-мат. лит-ры, 1984, 160 с.
3. Т. Мурата, “Сети Петри: Свойства, анализ, приложения”, ТИИЭР, т. 77, № 4,
c. 41–85, 1989.
4. А.Е. Пентус и М.Р. Пентус, Теория формальных языков. М.: Изд-во ЦПИ при
механико-математическом ф-те МГУ, 2004, 80 с.
5. А.Е. Пентус и М.Р. Пентус, Математическая теория формальных языков. М.:
“Бином”, 2006, 247 с.
6. Дж.Э. Хопкрофт, Р. Мотвани, и Дж.Д. Ульман, Введение в теорию автоматов,
языков и вычислений. М.: “Вильямс”, 2002, 528 с.
7. В.М. Статкевич, “Регулярные выражения для некоторых языков сетей Петри в
задаче о производителе и потребителе”, Системні дослідження та інфор-
маційні технології, № 3, с. 105–123, 2020. doi: 10.20535/SRIT.2308-
8893.2020.3.08
8. А. Саломаа, Жемчужины теории формальных языков. М.: Мир, 1986, 159 с.
9. Ф.А. Новиков, Дискретная математика для программистов. СПб: Питер,
2000, 304 с.
Поступила 25.02.2021
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
ОПЕРАЦІЯ РІЗНИЦІ ДЛЯ РЕГУЛЯРНИХ МОВ МЕРЕЖ ПЕТРІ В ЗАДАЧІ
ПРО ПОСТАЧАЛЬНИКА ТА СПОЖИВАЧА З ОБМЕЖЕНИМ БУФЕРОМ /
В.М. Статкевич
Анотація. Розглянуто мережу Петрі в задачі про постачальника та споживача
(одній з класичних задач синхронізації) з обмеженим буфером розміру n і ре-
гулярні формальні мови nL , які вона породжує. Згідно з метою роботи —
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 112
отримання регулярного виразу для різниці мов mn LL \ , mn — побудовано
скінченний автомат, який допускає різницю вказаних мов, методом вилучення
вершин отримано регулярний вираз в рекурсивній формі. Основний результат
проілюстровано на прикладах. Як доповнення розглянуто задачу з двома по-
стачальниками та двома споживачами з обмеженим буфером розміру 1. Побу-
довано граф досяжності та запропоновано конструкцію для отримання регуля-
рного виразу. У випадку задачі з двома постачальниками та одним
споживачем, а також задачі з одним постачальником та двома споживачами
вказано явні формули.
Ключові слова: мережа Петрі, задача про постачальника та споживача, мова
мережі Петрі, формальна мова, регулярна мова, скінченний автомат, регуляр-
ний вираз.
SET DIFFERENCE OPERATION FOR REGULAR PETRI NET LANGUAGES
FOR THE PRODUCER/CONSUMER PROBLEM WITH THE BOUNDED
BUFFER / 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. The objective of this paper is to ob-
tain a regular expression for the set difference of languages mn LL \ , mn . For
this purpose, we give the finite automaton which accepts the set difference of men-
tioned languages, and then we use the state elimination method to obtain the regular
expression in the recursive form. The main result is illustrated by the examples. In
an appendix, we consider the problem with two producers and two consumers with
the bounded buffer of size 1. We give a reachability graph and propose the method
for obtaining the regular expression. The explicit formulas are given for the problem
with two producers and one consumer and also for the problem with one producer
and two consumers.
Keywords: Petri net, producer/consumer problem, Petri net language, formal lan-
guage, regular language, finite automaton, regular expression.
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 inzhen-
erov 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. J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to automata theory, lan-
guages, and computation. Moscow: Williams Publishing House, 2002.
7. V.M. Statkevych, “Regular expressions for some Petri net languages for the pro-
ducer/consumer problem”, System Research & Information Technologies, no. 3,
pp. 105–123, 2020. doi: 10.20535/SRIT.2308-8893.2020.3.08
8. A. Salomaa, Jewels of formal language theory. Moscow: Mir, 1986.
9. F.A. Novikov, Discrete mathematics for programmers. St. Petersburg: Piter, 2000.
|
| id | journaliasakpiua-article-240011 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:27:28Z |
| publishDate | 2021 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/ea/d5e96c0e0a3ffc08d8bc0d5536ebcaea.pdf |
| spelling | journaliasakpiua-article-2400112021-09-16T11:48:22Z Set difference operation for regular Petri net languages for the producer/consumer problem with the bounded buffer Операция разности для регулярных языков сетей Петри в задаче о производителе и потребителе с ограниченным буфером Операція різниці для регулярних мов мереж Петрі в задачі про постачальника та споживача з обмеженим буфером Statkevych, Vitalii мережа Петрі задача про постачальника та споживача мова мережі Петрі формальна мова регулярна мова скінченний автомат регулярний вираз сеть Петри задача о производителе и потребителе язык сети Петри формальный язык регулярный язык конечный автомат регулярное выражение Petri net producer/consumer problem Petri net language formal language regular language finite automaton regular expression 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. The objective of this paper is to obtain a regular expression for the set difference of languages Ln \ Lm, n > m. For this purpose, we give the finite automaton which accepts the set difference of mentioned languages, and then we use the state elimination method to obtain the regular expression in the recursive form. The main result is illustrated by the examples. In an appendix, we consider the problem with two producers and two consumers with the bounded buffer of size 1. We give a reachability graph and propose the method for obtaining the regular expression. The explicit formulas are given for the problem with two producers and one consumer and also for the problem with one producer and two consumers. Рассмотрены сеть Петри в задаче о производителе и потребителе (одной из классических задач синхронизации) с ограниченным буфером размера n и регулярные формальные языки Ln, которые она порождает. Согласно цели работы — получение регулярного выражения для разности языков Ln \ Lm, n > m — построен конечный автомат, допускающий разницу указанных языков, далее методом исключения вершин получено регулярное выражение в рекурсивном виде. Основной результат проиллюстрирован на примерах. В качестве дополнения рассмотрено задачу с двумя производителями и двумя потребителями с ограниченным буфером размера 1. Построен граф достижимости и предложено конструкцию для получения регулярного выражения. В случае задачи с двумя производителями и одним потребителем, а также задачи с одним производителем и двумя потребителями указаны явные формулы. Розглянуто мережу Петрі в задачі про постачальника та споживача (одній з класичних задач синхронізації) з обмеженим буфером розміру n і регулярні формальні мови Ln, які вона породжує. Згідно з метою роботи — отримання регулярного виразу для різниці мов Ln \ Lm, n > m — побудовано скінченний автомат, який допускає різницю вказаних мов, методом вилучення вер¬шин отримано регулярний вираз в рекурсивній формі. Основний результат проілюстровано на прик¬ладах. Як доповнення розглянуто задачу з двома постачальниками та двома споживачами з об¬меженим буфером розміру 1. Побудовано граф досяжності та запропоновано конструкцію для отримання регулярного виразу. У випадку задачі з двома постачальниками та одним споживачем, а також задачі з одним постачальником та двома споживачами вказано явні формули. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2021-09-14 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/240011 10.20535/SRIT.2308-8893.2021.2.08 System research and information technologies; No. 2 (2021); 94-112 Системные исследования и информационные технологии; № 2 (2021); 94-112 Системні дослідження та інформаційні технології; № 2 (2021); 94-112 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/240011/238395 |
| spellingShingle | мережа Петрі задача про постачальника та споживача мова мережі Петрі формальна мова регулярна мова скінченний автомат регулярний вираз Statkevych, Vitalii Операція різниці для регулярних мов мереж Петрі в задачі про постачальника та споживача з обмеженим буфером |
| title | Операція різниці для регулярних мов мереж Петрі в задачі про постачальника та споживача з обмеженим буфером |
| title_alt | Set difference operation for regular Petri net languages for the producer/consumer problem with the bounded buffer Операция разности для регулярных языков сетей Петри в задаче о производителе и потребителе с ограниченным буфером |
| 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 |
| url | https://journal.iasa.kpi.ua/article/view/240011 |
| work_keys_str_mv | AT statkevychvitalii setdifferenceoperationforregularpetrinetlanguagesfortheproducerconsumerproblemwiththeboundedbuffer AT statkevychvitalii operaciâraznostidlâregulârnyhâzykovsetejpetrivzadačeoproizvoditeleipotrebitelesograničennymbuferom AT statkevychvitalii operacíâríznicídlâregulârnihmovmerežpetrívzadačípropostačalʹnikataspoživačazobmeženimbuferom |