О языках вложенных рекурсивных сетей Петри

В работе исследуются языковые свойства вложенных рекурсивных сетей Петри. Показано, что класс контекстно-свободных языков строго вкладывается в класс тупиковых языков вложенных рекурсивных сетей Петри. Приводится алгоритм построения сети, порождающей данный КС-язык. сеть петри язык рекурсивный Формализмы, основанные на сетях Петри ([Котов, 86]), являются удобным инструментом для моделирования и анализа различных параллельных и распределенных систем управления. В данной работе исследуются языковые свойства так называемых вложенных рекурсивных сетей Петри ([Lomazova, 99]), которые позволяют моделировать системы с модульной и динамической структурой. Эта модель представляет собой дальнейшее развитие концепции вложенных сетей Петри [Ломазова, 99]. Во вложенных сетях в качестве фишек выступают обычные сети Петри, которые имеют автономное поведение и могут взаимодействовать с системной сетью. Это позволяет интуитивно ясно моделировать иерархические системы с динамической структурой. Рекурсивные вложенные сети Петри — обобщение вложенных сетей, в котором сеть может порождать в качестве элемента (фишки) свою собственную копию, что снимает ограничения на глубину вложенности. Рекурсивные сети оказались более удобными для моделирования систем, имеющих рекурсивную природу. В частности, известно [Jantzen, 1987], что такой фундаментальный класс формальных систем, как класс контекстно-свободных языков не сравним с классом языков, порождаемых обыкновенными сетями Петри. В то же время существует довольно простой способ моделирования рекурсивными сетями произвольного КС-языка. В данной работе приводится алгоритм построения рекурсивной вложенной сети Петри, порождающей произвольный КС-язык в качестве тупикового.