Sistemnì Doslìdženâ ta Informacìjnì Tehnologìï (Sep 2021)

Операция разности для регулярных языков сетей Петри в задаче о производителе и потребителе с ограниченным буфером

  • Vitalii Statkevych

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

Abstract

Read online

Рассмотрены сеть Петри в задаче о производителе и потребителе (одной из классических задач синхронизации) с ограниченным буфером размера n и регулярные формальные языки Ln, которые она порождает. Согласно цели работы — получение регулярного выражения для разности языков Ln \ Lm, n > m — построен конечный автомат, допускающий разницу указанных языков, далее методом исключения вершин получено регулярное выражение в рекурсивном виде. Основной результат проиллюстрирован на примерах. В качестве дополнения рассмотрено задачу с двумя производителями и двумя потребителями с ограниченным буфером размера 1. Построен граф достижимости и предложено конструкцию для получения регулярного выражения. В случае задачи с двумя производителями и одним потребителем, а также задачи с одним производителем и двумя потребителями указаны явные формулы.

Keywords