Sistemnì Doslìdženâ ta Informacìjnì Tehnologìï (Dec 2020)

Регулярные выражения для некоторых языков сетей Петри в задаче о производителе и потребителе

  • Vitalii M. Statkevych

DOI
https://doi.org/10.20535/SRIT.2308-8893.2020.3.08
Journal volume & issue
no. 3

Abstract

Read online

Рассмотрены сеть Петри в задаче о производителе и потребителе (одной из классических задач синхронизации) с ограниченным буфером размера n и регулярные формальные языки Ln, которые она порождает. Для этих языков найдены регулярные выражения в рекурсивном виде, а в случаях ограниченного буфера размера от 1 до 3 — в виде явных формул. По графу достижимости построен конечный автомат, применен метод последовательного удаления вершин. Для высоты итерации (звездной высоты) указанных языков дана оценка сверху, а в случаях ограниченного буфера размера 1 и 2 найдены точные значения. Для указанных языков рассмотрены операции объединения, пересечения, замыкания Клини, конкатенации и разности. Для разности языков Ln \ L1 построен конечный автомат и найдены регулярные выражения в рекурсивном виде, а для разности L2 \ L1 — в виде явной формулы.

Keywords