Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 69
Текст из файла (страница 69)
Теорию формальных грамматик и аатоматоа Если маркировка уз' достижима из начальной маркировки уз сети Петри, то должно существовать целое неотрицательное решение уравнения,и' = уз+ х.(л, решением которого будет х = у(сг). Исследуем аадзчу достнинмостн для сети Петри, изобраненной на рис. 4.87, б, с начальной марвировкой (1,0, О, 0) для маркировки»з' = (О, 2, 1, 2).
Уравиыше»з' = »з+ хР принимает внд 0 1 0 0 (О, 2, 1~ 2) = (1~ О, О, 0) + х. 0 0 -1 0 и имеет решение х = (4, 2, 1, 0), соответствующее последователывзстя запусков переходов Гзсзсз1згзсзсз Матричный подход к анализу сетей Петри, как и подход, основанный на дереве достижимости, ие позволяет в общем случае решить задачу активности и достижимости. Проблемы матричного анализа заключаются в том, что, во-первых, вектор запуска, получаемый при решении уравнения, не дает информации о порядке запуска переходов и, во-вторых, может соответствовать неразрешенной последовательности запусков.
В настоящее время установлена, что задачи достижимости и активности эквивалентны, но не известно, разрешимы ли они вообще, т. е. нет ни алгоритма, позволяющего решить эти задачи, ни доказательства его отсутствия. Рассмотрим применение методов анализа сетей Петри, моделирующих практические системы. Специалиэнрованизя параллельная система для реалиаепии интеграционных вычислительных процессов состоят иа совокупности процессорных элементов (ПЭ) и молулей памяти (памяти данных (МПД) и памяти команд (МПК)), свяаанных в копыт (рис.
4.89). ПЭ работает в двух реиимах. В первом случае он захватывает оба смевипюх МПД, используя левый лля извлечения исход- ных данных новой итерации, вравый — для выборки результатов предыдущей итерации. По завершении итерации он помещает результат в правый МЙД и освобоидает оба МПД. В другом реннме ПЭ работаег с внутренними данными. Реиим упааываегся комшздой, считываемой их МПК. Рассмотрим два варианта реализации устройств увравления ПЭ. В первом варианте захват МПД при осуществлении итерааии производится последовательно. ПЭ монет находиться в следующих состояниях: "обработке внутренних данных" (Яз ), "захвачен левый 94.11.
Модслкроаамис оазноматнмх сиспзсм сетями Петри 383 МПД (Яз), ааахвачен правый МПД" (Яз), аэахвачены оба МПД, обработка данных очередной итерааии" (Яз). МПД монет быть либо свобоаным, либо захваченным. Собьггиями будем ссчитать захват и освобоидение МПД, Этот вариант работы представляется сетью Петри, в которой вандому ПЭ соответствуют четыре позиции, реаляаующие описанные условия, а кандому МПД вЂ” поанция ($ишва в которой означает, что МПД своболен; (рис. 4.90).
Мокко убедиться, что дерево достиннмости этой сети Петри содериит две терминальные маркировки: 384 Гл. 4. Теория формальных грамматик и оетоматое 14.12. Эадачи и унралскеиия 385 )»! = (Яз, Яз, Фг) и )»2 = (Яз, Яз, Язз), кредстевляющне ситузвюо, когда ка. адый ПЭ ззхвзтывзет левый и крзвый МПД соответственно. Это означает, что сеть Петри не актязна, т.
е. в системе вазмоаны тувнковые ситуации. При другам веризкте работы системы ПЭ осушествлтат только одновременный за!свет сменных МПД (если он вавмоаен). В тгом случае кзадому ПЭ соответствуют только условия Я! и Я» (рис. 4.91). Дерево достианмастн (рис. 4.92) не садераит термннальных маркировок, сеть Петри активна. Кроме тога, на рзс- (1 1 ! 1 0 1 0 1 0) (О ! 0 0 1 1 0 1 0) (О 0 1 ! 0 0 1 1 0) (1 0 0 ! 0 1 О 0 1) 9(2 (! ! ! ! 0 1 0 ! О) (1 1 1 1 0 ! 0 1 0) (1 ! ! 1 0 1 0 1 0) Рнс. 4.92 смотрения дереве достнанмостн очевидно, чта сеть Петри безокзснея (цоасция нитеркретируется вак простые условия).
В системе осуществляется рескределение ресурсов, которые ие воявлюотся и ие исчезают, т. е. выполняется закон сохранения. Определим, является лн сеть Петри сохраняющей. Для етого решим уравнение 12И' = О, которое крнннмзет внд »О1 М2 »ОО »О» 1ОЬ кч Юг юа 1ОЕ -1 0 — 1 -1 1 1 0 1 1 -1 — 1 — 1 0 0 0 1 1 0 0 0 0 -1 — 1 О 0 0 1 1 0 0 О 0 0 0 О 0 0 0 — 1 1 0 0 1 -1 0 0 0 0 -1 1 0 0 1 -1 Решением его является И' = (1, 1, 1, 1, 3, 1, 3, 1, 3).
Действительно, казицнн рз, рт, рз представляют условия, связанные с тремя устройствами, остальные позиции — условия, которые сатаны с одним устройством. Таким образом, сеть Петри обладаю основными необхадимымн свойствами, что обеспечивает работоспособность второго варианте. Попытки моделирования реальных систем привели к различным доопределениям и модификациям сетей Петри. В основном эти модификации связаны с изменением правила запуска переходов. Мои(ность моделирования обычных сетей Петри ограничена невозможностью проверки позиции на нуль (т.
е. того, что маркировка позиции нулевая). Одним из способов преодоления зтого недостатка является введение сдерлеивяюи(их дуг. По новым правилам запуска переход разрешен, если фишки есть в его обычных входных позициях (из которых ведут обычные дуги) и отсутствуют в сдерживаюших входных позициях (из которых ведут обычные дуги). Сдерживаюшая дуга изображается как обычная, только на конце имеет вместо стрелки маленький кружок (это обозначение заимствованс из теории нереключательных схем, где кружок означает онео) (рис.
4.93). Если в обычных сетях Петри переход запускается по логике И, то в сетях Петри со сдерживаюшими дугами логика расширена до включения отрицаний. Поскольку событие может представляться несколькими переходами, можно смоделировать событие, предусловие которого записывается как объединение нескольких конъюнкций 31 условий и отрицаний условий, соответствующих позициям сети Петри со сдер)киваюшнми дугами. Таким образом, (,' сети Петри позволяют моделировать мпд! ° ° 3! предусловня в виде ДНФ, т.
е. условия 1 самого обшего вида. Рассмотренная зздечз оргвююацни работы скедизлнзировзниай вычислительной сисхемы монет быть решена и кервым вариантом, в к~ хором разрешен коследовзтельный ззхззт МПД 32 (см. рис. 4.90), иа с предотвращением туонко- »2 2 вых ситуаций. Очевидно, что возмоаны две ту- рне. 4.93 аиковые ситуации, охнсывземые маркировками с фишками в казнцнях Яз, Я2, Я22 и Яз, Язз, Язз. Для кредатврзшення первой туликовой ситуации необходимо в маркировках (Яз, Яз), (Яз, Яз), (Яз, Ятз) предотвратить воявленне фишки в козициях Яз, о~з, Яз соответственно. Следавзтельно переход 21 долаеи иметь в качестве кредусловия ваньюнкцюо МПД, 32 4ОЯ! 42(Я! 3О Яз ), т.
е. его иуаио заменить из кереходы !', и 2," с вредусловнями МПД, 3О Я, 42 Я2 и МПД, !с Я! 31Я2 (см. рнс. 4.93). Аналогично следует аостуннть с цереходзмн 22, 2» (см. рис. 4.90). Подобные действия вредхриннмзются и для цредатврзшения второй туликовой ситуации. Другие предложения по изменению правил запуска либо зквивалентны введению сдерживающих дуг, либо носят даже более частный характер. Например, в сетях Петри с областями ограничения имеются множества позиций (называемые областями ограничения), в которых фишки одновременно находиться не могут.
Правила запуска модифицированы так, чтобы не нарушать это условие. Если в сеть Петри, изображенную на рис. 4.90, включить дВЕ Обпаетн ОГраНИЧЕНИя, (22~1 52~, Ятзу И (.231,23~! .23), та МОЖНО предотвратить возникновение тупиковых ситуаций. 34.12. Задачи и упражнения 4.1. Состзвять функциональную теблнду мешины Тьюринга дри суммировании 1 к числу, звкисвнному в троичной системе счисления. 4.2.
Нз ленте зенисека число в системе счисления с основанием (). Составить фуикцнонзлыше таблицы, с помощью которых монна зекисзхь число: в) непосредственно следующее зз дзюшм; б) иекосредственно цредшествующее данному. 4.3. Нз ленте ззкнсзна число х в троичной системе. Составить функциональную таблицу, с помощью которой из леитУ ззцисывветск 2х, если х делится иа 3 без остатке, и х — 1 в кротивнам случае. 4.4. Синтезировать криотрониую схему, резлазующую функцию У(Х1, Хз, Хз, Х»))! ю Ч(1, 3, 7, 3, 9, 10, 12, 15). !2 В.
К Г»Оса|а» 386 Гл. 4. Теория формальных грамматик и аетоматое 14.13. Комментарии 387 4.6. Как учнтяюаетая каэф(пишеит разветвления, определяемый иагрузоч- ными способностями ааданиого бааисного элемента, при использовании ковлгеб- ры графов К? 4.6. Сравнить слояности счетчиков четности от трех переменных в базисе Веббе и Шеффера.
4.7. Сравнить слоияости счетчика четности от трех веременпых в баэисе Шеффера, по строеняого методом моделирования свяаов алгебры Буля и методом, который основан ив применении коалгебры графов К. 4.6. Минимнвировать коли'тстав нетермннальных символов автоматной грамматини, определяемый секвеициямн вида: Ова -+ ва1, 1ва -+ ваО, Овз -+ вз1, 1ва -+ вто, Овз -+ ва1, 1вз "+ вао, Ова -+ вао, 1ва "+ вз1, Овв -а ва1, 1ва -а ваО, Ова -а вао, 1ва -Ф ваО, Овт -+ ваО, 1вг -+ ва1, Ова -+ ваО, 1ва -+ взо, где в; (а = 1, ..., 6) — ' иетерминельный символ; О, 1 — терминальные символы (левый относительно стрелкя входной, правый выходной).
4.6. Произвести соседнее кодирование нетерминвльных символов автомат- ной грамматики, заданной в предыдушей задаче. 4.10. Построить функцию воабуядення первого триггере с рвадельными вхо- дами для автомате, рассмотренного в предыдушей задаче. 4.Н. Построить фуикшио воабуидения второго триггера со счетяьгм входом для автомата, рассмотренного в задаче 4.9.
4,12. Синтеаировать триггер со счетным входом в имлликативном базисе. 4,16. Сшпеаировать триатер с раздельными входами в коимпликативном 6ависе. 4.14. Снитеаироввть генератор лоследовательности чисел 1, 7, О, 2, 5, 1, ... в бааисе Жегалкина. 4.15. Синтезировать логическую схему, реалнаующую булеву функцию У(хн ха, хз, ха))а = и(О, 1, 2, 7, 11), в первом топологическом бааисе.
4,16. Синтеэировать логическую схему, реализуюшую булеву функцию у(хи хг, хз, хл)Ь = и(0 1~ 2 4 15)~ ва втором топологнческом базисе. 4.17. Синтезировать логическую схему, реелиауюшую булеву функцию У(ха, ха, хз, ха))а = и(0, 3, 5, 10, 12, 15), в третьем топологнческом базисе. 4.16. Синтеаировать логическую схему, реелиауюшую булеву функцию 1(х! хв хз ха))1 и(0,3,баб,9, 10) в четвертом топологи меном базисе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
