6.5. Свойства замкнутости

Перейдем к изучению свойств замкнутости языков сетей Петри по отношению к некоторым видам композиции (объединению, пересечению, конкатенации, параллельной композиции, и подстановке) и по отношению к некоторым операциям (обращению, дополнению и бесконечной конкатенации). Изучение этих свойств интересно по двум причинам. Во-первых, оно увеличивает наши знания о свойствах и ограничениях языков сетей Петри как языков. Во-вторых, многие из перечисленных типов композиции отражают процесс композиционного проектирования и конструирования больших систем из малых, поэтому данное исследование может оказаться полезным для разработки методов синтеза.

Большинство из свойств замкнутости касаются композиций языков сетей Петри. Рассмотрим два языка сетей Петри, Мы знаем, что каждый из них порождается некоторой сетью Петри стандартного вида. Поэтому можно рассматривать две помеченные сети Петри стандартного вида, Поскольку сети стандартного вида, имеет начальную позицию Кроме того, или

Покажем, как из этих двух помеченных сетей строится новая помеченная сеть Петри с языком который является композицией требуемого типа. Описываемые конструкции будем иллюстрировать примерами сетей Петри.

Начнем рассмотрение свойств композиции языков сетей Петри с конкатенации, объединения, пересечения и параллельной композиции. Затем исследуем обращение и дополнение языка сети Петри и, наконец, подстановку.

6.5.1. Конкатенация

Многие системы представляют собой последовательную композицию двух подсистем. Каждую из подсистем можно представить сетью Петри со своим языком. При последовательной комбинации двух систем соответствующее выполнение является конкатенацией выполнения из первого языка сети Петри и выполнения из второго. Конкатенация двух языков формально определяется как

Теорема 6.2. Если и языки сетей Петри, то язык сети Петри.

Доказательство. Определим у таким образом, чтобы заключительная позиция совместилась с начальной позицией Тогда переход, помещающий фишку в будет свидетельствовать о конце выполнения а также о начале выполнения Любая строка конкатенации является тогда путем из и затем в следовательно, элементом Аналогично, если строка порождена сетью С, она является конкатенацией строки, порожденной и строки, порожденной

Формальное определение учитывает пустую строку и поэтому более сложно, у можно определить как объединение со следующими дополнительными переходами. Для всякого вводим новый переход Если то вводим также и

Помечение определяем, как Новое заключительное множество если в противном случае

Рис. 6.8. (см. скан) Конкатенация двух языков сетей Петри. (Каждый переход в фактически является парой параллельных конфликтующих переходов, помеченных соответственно. — Прим. ред.)

Из этой теоремы следует, что класс языков сетей Петри замкнут по отношению к конкатенации. На рис. 6.8 показывается описанная конструкция для

6.5.2. Объединение

Другой общепринятый метод композиции систем — объединение. В композиции такого вида будет выполняться любая, но только одна из подсистем. Эта обычная композиция языков аналогична

объединению множеств и определяется следующим образом:

Теорема 6.3. Если языки сетей Петри, то язык сети Петри.

Доказательство. Доказательство аналогично доказательству предыдущей теоремы.

Определим новую сеть Петри такую, что В новой сети Петри две начальные позиции объединены в одну новую начальную позицию. Первый запускаемый переход удаляет фишку из начальной позиции, после чего либо сеть Петри (если переход был из либо сеть Петри (если переход был из будет действовать в точности так же, как до объединения.

Формально мы определяем новую начальную позицию и новый переход для каждого для каждого Функция помечения: Новая начальная маркировка содержит одну фишку в новое множество заключительных маркировок Если или кроме того,

На рис. 6.9 показана описанная конструкция для

6.5.3. Параллельная композиция

Еще один способ композиции двух сетей Петри заключается в разрешении одновременного выполнения двух систем. Он допускает все возможные «перемешивания» выполнений одной сети Петри с выполнениями другой. Для представления такой параллельной композиции Риддл [258] ввел оператор 11, который определяется для и следующим образом:

Параллельной композицией двух языков является

В качестве простого примера рассмотрим языки язык это

Легко показать, что регулярные, контекстно-связанные языки и языки типа замкнуты по отношению к параллельной композиции, поскольку параллельная композиция двух конечных автоматов, линейно-ограниченных автоматов или машин Тьюринга

(кликните для просмотра скана)

являются конечным автоматом, линейно-ограниченным автоматом и машиной Тьюринга соответственно. Вследствие того что параллельную композицию двух автоматов с магазинной памятью нельзя преобразовать в другой автомат с магазинной памятью, контекстно-свободные языки не замкнуты по отношению к параллельной композиции. Для языков сетей Петри докажем следующую теорему.

Теорема 6.4. Если языки сетей Петри, то язык сети Петри.

Доказательство. Сеть Петри, порождающая параллельную композицию строится из сетей Петри, порождающих эти языки; в ней в качестве начальной маркировки фишки помещаются в начальные позиции новое множество заключительных маркировок определяется всеми маркировками, принадлежащими (в позициях ) и (в позициях ).

Эта конструкция показана на рис. 6.10 для

6.5.4. Пересечение

Как и в случае объединения, операция пересечения подобна теоретико-множественному определению пересечения и определяется для языков сетей Петри следующим образом:

Теорема 6.5. Если языки сетей Петри, то язык сети Петри.

Конструкция сети Петри, порождающей пересечение двух языков сетей Петри, несколько сложнее рассмотренных ранее. Всякий раз при порождении строки, когда запускается переход в одной сети Петри, должен запуститься также переход в другой сети Петри с идентичной меткой. Если в каждой сети Петри существует более одного перехода с одной меткой, необходимо рассмотреть все возможные пары переходов двух сетей Петри. Для каждой такой пары мы вводим новый переход, который запускается тогда и только тогда, когда запускаются оба перехода в старых сетях Петри. Это достигается взятием в качестве входного (выходного) комплекта нового перехода суммы комплектов (см. приложение) входных (выходных) комплектов пар переходов старых сетей Петри. Следовательно, если такие, что то вводится переход Некоторые из таких переходов будут иметь в качестве входов начальную позицию. Если для перехода определенного описанным способом, то заменяем этот переход на другой Эта конструкция, по существу, включает две первоначальные сети Петри

(кликните для просмотра скана)

Рис. 6.11. (см. скан) Пересечение двух языков сетей Петри.

в синхронный режим выполнения. Такая составная сеть порождает пересечение Описанная конструкция иллюстрируется на рис. 6.11.

6.5.5. Обращение

В отличие от рассмотренных до сих пор операций обращение, по-видимому, представляет только теоретический интерес. Обращение предложения это предложение х, символы которого расположены в противоположном порядке. Мы определяем эту операцию рекурсивно:

для Обращение языка определяется следующим образом:

Теорема 6.6. Если язык сети Петри, то и язык сети Петри.

Конструкция в этом случае тривиальна. Начальная и заключительная маркировки меняются местом, меняются местом также входные и выходные комплекты каждого перехода. Следовательно, Построенная сеть просто выполняет первоначальную сеть Петри в обратном порядке и обращает все порождаемые ею строки.

6.5.6. Дополнение

Дополнение языка над алфавитом это множество всех строк отсутствующих в Его можно представить как

Эта операция над языком сети Петри может быть полезной при анализе сетей Петри, так как проверка существования запрещенных состояний или запрещенных последовательностей в дополнении может оказаться легче, чем проверка их несуществования в языке сети Петри.

Замкнутость языков сетей Петри -типа по отношению к дополнению — задача, которая ждет своего решения. Однако в [64] показано, что некоторые языки сетей Петри не замкнуты по отношению к дополнению, т. е. существуют языки сетей Петри, дополнения которых не являются языками сетей Петри.

6.5.7. Повторная композиция

Мы рассмотрели операции объединения, пересечения, конкатенации, параллельной композиции, обращения и дополнения. Для всех операций, кроме последней, мы описали конструкции, показывающие, что языки сетей Петри замкнуты по отношению к ним. Результаты позволяют сделать следующий вывод.

Следствие 6.1. Языки сетей Петри замкнуты по отношению к любому конечному числу выполнений операций объединения, пересечения, обращения, параллельной композиции и конкатенации, осуществляемых в любом порядке.

Доказательство следует из приведенных выше теорем.

Устраняя ограничение на конечность числа разрешенных операций, можно определить новую операцию. Бесконечная конкатенация (звезда Клини) языка — это множество всех конкатенаций

(произвольной длины) элементов языка. Она обозначается через и определяется как

Эта операция может оказаться полезной на практике. Бесконечная конкатенация подобна моделированию цикла. Кроме того, известно, что регулярные, контекстно-свободные, контекстно-связанные языки и языки типа замкнуты по отношению к бесконечной конкатенации [130]. К сожалению, и весьма неожиданно оказалось, что языки сетей Петри не замкнуты по отношению к бесконечной конкатенации.

Это объясняется конечностью сетей Петри (конечное число позиций и переходов) и разрешающей природой изменения состояний (переходы запускать разрешается, но потребовать их запуска нельзя). Для построения сети Петри, порождающей бесконечную конкатенацию языка сети Петри, потребовалось бы в общем случае повторно использовать некоторую часть сети Петри, что позволяет фишкам появляться и оставаться в некоторых из повторно используемых позиций сети Петри. При последующем повторе эти фишки могут разрешить переходы, которые не должны запускаться.

Доказательство того, что сети Петри не замкнуты по отношению к бесконечной конкатенации, оказалось очень сложным. Идею, положенную в основу доказательства, можно продемонстрировать, рассмотрев пример. Ранее показано, что язык сети Петри. Мы утверждаем, что не является языком сети Петри. Любая сеть Петри, порождающая должна иметь некоторую позицию или множество позиций, кодирующих число для каждой части строки. Эти фишки управляют порождением символов Сеть Петри, порождающая должна использовать эти фишки более одного раза. Но, поскольку природа сети разрешающая, нельзя гарантировать, что эти позиции станут пустыми перед повторным использованием. Следовательно, для любой сети Петри, пытающейся породить существуют такие что сеть Петри порождает также некоторую строку следующего вида:

где Основу формального доказательства того, что языки сетей Петри не замкнуты по отношению к бесконечной конкатенации, дал Косараю [159].

Читатель, знакомый с лингвистической теорией абстрактных семейств языков [100], легко докажет, что языки сетей Петри не замкнуты по отношению к бесконечной конкатенации. Хорошо известно, что наименьшие полные абстрактные семейства языков замкнуты по отношению к пересечению, а содержащие содержат и всякое рекурсивно перечислимое множество. Таким

образом, поскольку языки сетей Петри замкнуты по отношению к пересечению и язык сети Петри, то, если бы они были замкнуты по отношению к бесконечной конкатенации, они образовали бы абстрактное семейство языков. Однако нам известно, что не является языком сети Петри (см. разд. 6.6.2), поэтому языки сетей Петри не замкнуты по отношению к бесконечной конкатенации. Эта аргументация принадлежит Мандриоли.

Тем не менее существует подкласс языков сетей Петри, замкнутый по отношению к бесконечной -это класс языков вполне оканчивающихся сетей Петри. Это понятие введено в [104] для моделей вычисления, основанных на сложных билогических графах. Мы заимствуем его определение и переводим в термины сетей Петри.

Определение 6.6. Сеть Петри является вполне оканчивающейся, если всякий раз, когда ее выполнение заканчивается, 1) в сети остается только одна фишка, находящаяся в заключительной позиции; 2) число фишек, находившихся в сети Петри, конечно.

Заметим сначала, что вторая часть определения не обязательна, поскольку если сеть Петри оканчивает выполнение, то делает это за конечное число шагов и, следовательно, порождает только конечное число фишек. Первая же часть определения обязательна. Сеть Петри можно рассматривать как машину, порождающую строки символов. Мы помещаем фишку на вход машины, и на ленте для нас печатается строка символов. В конце концов обнаружится, что машина остановилась (т. е. не существует разрешенных переходов). В обычном подходе, когда не имеется отпечатанного выхода, необходимо анализировать текущее состояние машины и проверять, достигнута ли заключительная маркировка. Если она еще не достигнута, мы не принимаем выданную строку и снова пускаем машину. Если же сеть Петри вполне оканчивающаяся, то нет необходимости анализировать текущее состояние машины, поскольку гарантируется, что заключительная маркировка будет достигнута.

Теперь легко видеть, как можно использовать вполне оканчивающуюся сеть Петри для построения сети Петри, порождающей бесконечную конкатенацию ее языка. Мы просто соединяем заключительную и начальную позиции. Поскольку всякий раз, когда фишка появляетсяв заключительной позиции, сеть Петри, как мы знаем, бывает пуста, то при повторном использовании сети не будет запущен никакой нежелательный переход.

Этот подкласс сетей Петри не представляет большого интереса, поскольку можно показать, что между вполне оканчивающимися сетями Петри и конечными автоматами существует взаимно однозначное соответствие. Следовательно, языки вполне оканчивающихся сетей Петри являются регулярными, и, как уже известно, этот класс языков замкнут по отношению к бесконечной конкатенации. Таким образом, мы убедились, что изучение свойств систем,

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

6.5.8. Подстановка

Мы уже говорили, что системы можно проектировать и моделировать с помощью сетей Петри иерархическим образом. Это подразумевает сначала спецификацию схемы работы системы на уровне подсистем и затем последовательное уточнение этой схемы путем замены операций на их определения в терминах других операций. В случае применения сетей Петри уточнение может принимать форму подстановки целой сети Петри вместо перехода или позиции. Последнее не вызывает никаких трудностей, в связи с этим мы ограничим наше рассмотрение задачей подстановки подсети вместо перехода (операции) сети Петри.

Подстановку сети Петри вместо операции в другой сети Петри можно рассматривать как композицию языков двух сетей Петри. Поскольку операция представляется символом из подстановка языка сети Петри вместо символа в другом языке сети Петри определяется как замена всех появлений на множество строк Языки сетей Петри замкнуты по отношению к подстановке, если результат подстановки языка сети Петри есть также язык сети Петри. Вариациями подстановки являются конечная подстановка, при которой конечное множество строк, и гомоморфизм, при котором одна строка.

К сожалению, вновь результат отрицателен: языки сетей Петри не замкнуты по отношению к обычной подстановке. Это следует из примера подстановки вместо с в с. Причиной опять является возможность повторного запуска сети Петри. В случае же конечной подстановки или гомоморфизма является регулярным языком, следовательно, можно построить вполне оканчивающуюся сеть Петри, порождающую его, из чего вытекают следующие теорема и следствие.

Теорема 6.7. Если регулярный язык, язык сети Петри, то результат подстановки вместо любого символа язык сети Петри.

Следствие 6.2. Языки сетей Петри замкнуты по отношению к конечной подстановке и гомоморфизму.