Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 26

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 26)

Последовательность переходов — это строка, а множества строк — язык. Таким образом, в этой главе мы займемся языками, определяемыми сетями Петри, и их свойствами. ЬЛ. Мотивы мзученмв языков сетей Петри Развитие теории сетей Петри обусловливают две основные причины: 1) опнсаьие преплагаемых и существующих систем и й) анализ систем, моделируемых сетями Петри. Цель анализа сети Петри — определение свойств сети и моделируемой системы.

Одно из самых важных свойств системы — это множество действий, которые могут произойти. Множество всех возможных последовательностей действий хароктеризрст систему. Действия моделирукпся в сети Петри переходами, осуществление действия — запуском перехода. Последовательности действий моделирукпся последовательностями переходов.

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

Если обе системы моделирунлся сетями Петри, то поведение этих двух систем должно быть идентичным, и, следовательно, языки их равны. Две се;и Петри называются эквив ленглнылги, если равны их языки. Эзо образует формальную основу для установления эквивалентности двух систем.

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

Если преобразование, примененное к сети Петри, порождает новую сеть Петри с тем же языком, "го оно является сохраняющим язык. Оптимальную сеть Петри можно получить путем применения сохраняющих язык преобразований к неоптимальной сети Петри. Для практического использования моделирования и анализа систем на оснтве сетей Петри требуется набор преобразований, сохраняющих язык. Языки сетей Петри могут быль полезны также для анализа се.тей Петри. В гл. 4 были разработаны методы определения частных свойств сетей Петри: безопасности, ограниченнос1и, сохранения, активности, достижимости и покрываемости. Хотя установление этих свойств важно (и трудно), они не единственные, которые анализирукпся в сети Петри.

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

Благодаря атому можно получить общий метод анализа произвольных систем с целью проверки на обладание свойствами, специфичными для ннх. Риддл 125И занимался исследованиями анализа на основе языка моделиРуемой системы. Другое применение языков сетей Петри лежит в области задания и автоматического синтегхт сетей Петри. Если задать языком требуемое поведение, то можно будет автоматически синтезировать сеть Петри, обладающую данным языком.

Полученную сеть Петри можно использовать в качестве контроллера, гарантирующего, что возможны только указанные последовательности и никакие другие. „Вля определения разрешаемых последователыюстей действий были предложены Е-выражения П63). На нх основе разработаны методы . автоматического построения сетей Петри. Еще одна прнинна изучения языков сетей Петри — желание получить информацию о разрешимости ряда задач для сетей Петри.

Например,нам не известно, разрешимы ли задачи об обладании сетями ыо Глава 6 '«)) Петри определенными свойствами. В настоящее впеия ведутся исследования разрешимости таких основных задач, как достижомость. В частности, одна из областей, в которых рассматриваются вопросы разрешимости, — это теория формальных языков. Используя языки сетей Петри, можно перенести понятия и методы теории формальных языков иа задачи для сетей Петри.

Возможно, это позволит получить некоторые результаты в задачах разрешимости для сетей Петри. И обратно, методы сетей Петри могут оказаться весьма полезными для получения новых сведений о формальных языках. 1« « « ЬЛ. Некоторые понятия теории формепьных языиоя Развитая к настоящему моменту теория языков сетей Петри подобна другим частям теории формальных языков. Классическая теория формальных языков представлена в нескольких монографиях ПЗО, 265, 991. Многие из основных понятий теории языков сетей Пери заимствованы из классической теорие формальных языков. Ал«рава«п — это конечное множество символов.

Са«рока — любая последовательность конечной длины из символов алфавита. Пустая с«лавка «. — это стпока, не имеющая символов, т. е. нулевой длины. Если Х вЂ” алфавит, то Х* — множество всех строк из символов Х, включая пустую строку. Х является множеством всех непустых строк над алфавитом Х. Х* = Х+ В Р.«. Языком назыыется множество строк над алфавитом. В общем случае языки могут быть бесконечными, следовательно, одной из проблем является представление языка. Для представления языков было предложено два подхода.

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

Это дает прекрасные средства для установления связи теории сетей Петри с теорией формальных языков: мы определяем класс языков сетей Петри как класс языков, порождаемых сетями Петри. Детали этого определения аналогичны деталям определения любого другого класса языков. Рассмотрим в качестве примера конечные автоматы и регулярные выражения, Конечный автомат С есть пятерка Я б, Х, в, г), где Д вЂ” конечное множество состояний, Х вЂ” алфавит симвсп«ов, б: ~ и Х «-(~ — функция переходов, вр Я вЂ” начальное состоя- ттзики сетей Петри ние, г г- я — конечное множество заключительных сослюлнийп. Функция переходов б естественным образом обобщается на случай отображения нз (~ х Х" в ('). Язык ЦС), порождаемый конечным автоматом, — это множество строк над Х, определяемое следующим образом: ~(О) =( ЕХ*! Из.

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

Задание этого для сети Петри может привести к различным классам языков сетей Петри. Рассмотрим их по порядку. 6.3Л. Начальное состояние Начальное состояние сети Петри можно определить различными способами. Наиболее общепринятое определение — считать начальным состоянием произвольную маркировку )г. Однако зто определение имеет несколько модификаций. Одним из разумных ограничений в определении начального состояния является рассмотрение только маркировок с одной фишкой в начальной позиции и нулем фишек в остальных [2371. Другое, более общее определение '.допускает множество начальных маркировок вместо одной маркировки. Эти три определения, по существу, одинаковы.

Разумеется, опре,.деление начальной позиции является частным случаем определения начальной маркировки, а оно — частным случаем определения множества начальных маркировок. Однако если при определении начальной позиции будет необходимо множество начальных марки- $ ровок М = (р„р, ..., ра), то можно просто ввести в сеть Петри дополнительную позицию р» и множество переходов (сг, ..., ге). ереход г( будет брать фишку из р„и порождать маркировку рр аким образом, поведение расширенной сети будет идентично по- П Как а арнгинале, будем нспользааать терман «конечный а»томат» я обозначения управляющего автомата (разд.

Характеристики

Список файлов книги