Cтраница 1
Помеченная сеть Петри - эта пара ( Л /, 2), где N - сеть Петри, 2: Т - А - помечающая функция над некоторым алфавитом А. [1]
Поскольку для помеченной сети на рис. 3.1, б помечающая функция 2 ] осуществляет взаимно-однозначное отображение множества Т на алфавит А, то ее префиксный язык и терминальный языки получаются из вышеприведенных языков прямой заменой символов-переходов на соответствующие символы из А. [2]
Nu префиксный язык помеченной сети ( Л /, 2) совпадают. [3]
Теорема 3.7. Класс помеченных сетей Петри строго мощнее класса конечных автоматов, не сравним с классом магазинных автоматов и строго менее мощен, чем класс машин Тьюринга. [4]
На рис. 3.5 6 показана помеченная сеть, построенная таким образом по автомату на рис. 3.5 а. Простой анализ способа построения помеченной сети по конечному автомату убеждает в том, что язык, допускаемый автоматом, совпадает с терминальным языком построенной сети. [5]
Петри включает префиксные языки всех помеченных сетей, которые можно образовать из сетей класса. Верхний индекс X указывает, что помечающие функции могут быть частичными, т.е. помеченные сети могут содержать X-переходы. [6]
Петри включает терминальные языки всех помеченных сетей, образованных из сетей класса Jf, в том числе помеченных сетей с Х - переходами. [7]
Существует терминальный язык, порождаемый помеченной сетью Петри и не являющийся контексно-свободным. [8]
Для выяснения принадлежности слова а языку помеченной сети с Х - пере-ходами может быть применена следующая процедура. [9]
Покажем, как из этих двух помеченных сетей строится новая помеченная сеть Петри у ( С, а, ( д /, F) с языком L ( y), который является композицией LJ и L2 требуемого типа. [10]
Если класс помеченных ординарных сетей равномощен классу помеченных сетей с кратными дугами по отношению к префиксным и терминальным языкам, то иная ситуация складывается со свободными языками. [11]
Предположим, что язык L порождается некоторой помеченной сетью Петри ( Л /, 2) в качестве терминального языка. Подъязык а ь с п 0) языка L также порождается этой сетью. Тогда эта сеть должна порождать бесконечные последовательности срабатываний. [12]
Этот язык порождается ( как префиксный) помеченной сетью Петри с Х - перехо-дами, показанной на рис. 3.4. В этой сети поочередные срабатывания переходов Г2 и Г3, помеченных соответственно символами 0 и 1, порождают некоторое двоичное слово о. Если при этом срабатывают также переходы f4 nfs, то в местах РЗ ир4 накапливаются фишки. [13]
Покажем, как из этих двух помеченных сетей строится новая помеченная сеть Петри у ( С, а, ( д /, F) с языком L ( y), который является композицией LJ и L2 требуемого типа. [14]
Теорема 5.3. Любой рекурсивно перечислимый язык может быть порожден помеченной сетью с приоритетами как ее префиксный или терминальный язык. [15]