- •Часть 1.
- •Оглавление
- •1. Модели дискретных структур. Комбинационные схемы
- •1.1. Введение
- •1.2. Функции алгебры логики
- •Коммутативность
- •Ассоциативность
- •Дистрибутивность
- •1.3. Булева алгебра. Функциональная полнота
- •Свойства алгебры Жегалкина
- •1.4. Минимизация функции алгебры логики
- •1.5. Функции k-значной логики
- •1.6. Основные понятия трехзначной логики
- •1.7. Представление k-значных функций в виде нормальных форм
- •1.8. Двоичное кодирование переменных и функций трехзначной логики
- •1.9. Программная реализация логических функций и автоматов
- •2. Формальные языки и грамматики
- •2.1. Введение в теорию формальных языков и грамматик
- •2.2. Выводы цепочек формального языка. Деревья ксг
- •2.3. Основные понятия теории формальных языков и грамматик
- •2.4. Приведение грамматик
- •2.4. Операции над языками
- •2.5. Право-линейная и автоматная грамматики
- •3. Теория автоматов
- •3.1. Введение
- •3.2. Способы представления конечных автоматов
- •3.3. Минимизация числа состояний автомата
- •3.4. Использование сети Петри при переходе от грамматики к автомату
- •3.5. Сети Петри. Маркировка
- •3.6. Классификация сетей Петри
- •Статические ограничения
- •3.7. Синхронные и асинхронные автоматы
- •3.8. Модели автоматов Мили и Мура
- •3.9. Кодирование автомата
- •3.10. Элементная база синтеза комбинационных схем
- •3.11. Структурный синтез автомата
- •4. Отдельные вопросы теории вычислительных процессов
- •4.1. Автоматы с магазинной памятью
- •4.2. Комбинационные схемы обнаружения ошибок
- •4.3. Пространство сообщений. Коды обнаружения и исправления ошибок
- •Контрольные вопросы
3.5. Сети Петри. Маркировка
Множество входных и выходных позиций перехода ti T обозначим через I(ti) и O(ti) соответственно. Аналогично, записи I(pi) и O(pi) есть обозначения входного и выходного множеств переходов для позиции pi. Тогда сеть Петри может быть задана как формальная система следующим образом:
S = < P, T, I, O, 0 > , где I = I ( ti ) , O = O ( ti ), P = I O.
Представление сети Петри в виде двудольного графа позволяет задать структуру сети Петри статически. Динамика в модель вносится механизмом смены маркировки (разметки) позиций и соглашением о правиле срабатывания ( реализации ) переходов.
Начальная маркировка присваивает позициям сети Петри целые числа ( в том числе нуль ).
На графе маркировка задается следующим образом: в позициях проставляют определенное число точек, носящих название маркеров или фишек. Передвижение маркеров по сети осуществляется посредством срабатывания ее переходов. Сработать может только возбужденный переход, то есть такой переход ti T, во всех входных позициях которого содержится хотя бы по одному маркеру. Срабатывание перехода может произойти через любой конечный промежуток времени после возбуждения перехода. Результатом срабатывания является изъятие по одному маркеру из каждой входной позиции срабатывающего перехода и добавление маркера во все его выходные позиции. Изъятие маркеров и их перемещение считается мгновенным, с нулевой задержкой. Срабатывание какого-либо возбужденного перехода вызывает смену маркировки сети. Текущая маркировка сети понимается как состояние сети в данный момент времени. Можно считать, что динамика поведения сети Петри (ее функционирование во времени) адекватно может быть описана моделью вида: S = < 0, , >, где 0 - начальная маркировка; - отношение следования маркировок; - множество допустимых маркировок данной сети достижимых из 0.
Маркировка может задаваться вектором = (1, ... n ), число компонент которого соответствует числу позиций сети. Значение i - й компоненты i n есть натуральное число равное числу маркеров в позиции.
Пример. Для сети Петри, заданной в виде графа:
P1 P2
t1
P3 P4
t 2 t3 t4
t5
P5 P6 P7
рассмотреть следование маркировок из 0.
Решение. Начальная маркировка имеет следующий вид:
0 = ( 2, 1, 0, 0, 0, 1, 0), где цифра есть число маркеров в соответствующей позиции. По определению возбужденным переходом сети при маркировке 0 является переход t1. Его срабатывание приводит сеть в новое состояние
0 1, 1 =(1, 0, 1, 1, 0, 1, 0). Далее возбуждаются переходы t4, t2, t3. Из переходов t2 и t3 может сработать только один, так как срабатывание одного перехода снимает возбуждение другого. Рассмотрим все возможные варианты:
Отметим, что в сети возможно одновременное срабатывание нескольких переходов , например, ( t2, t4 ) или ( t3, t4 ) после срабатывания перехода t1. Рассмотрим соответствующие этим вариантам состояния сети:
0 1 4, 4 = ( 1, 0, 0, 0, 1, 1, 1) - при срабатывании ( t2, t4 ),
0 1 4, 4 = (1, 0, 0, 0, 1, 1, 1) - при срабатывании ( t3, t4 ).
Для задания динамики сети Петри используют диаграмму достижимых состояний (маркировок). Диаграмма представляет собой ориентированный граф, вершины которого есть достижимые маркировки из множества M, а дуги направлены из a в b . Дуги, если необходимо, помечают обозначением тех переходов, срабатывание которых является причиной смены маркировки.
Пример. Построить диаграмму достижимых состояний для сети предыдущего примера.
Решение.
(2, 1, 0, 0, 0, 1, 0)
t1
(1, 0, 1, 1, 0, 1, 0)
t2t3 (t2t3)t4 t4
( 1, 0, 0, 1, 1, 1, 0) t2t3 ( 1, 0, 1, 0, 0, 1, 1)
t4
( 1, 0, 0, 0, 1, 1, 1) t5
t5 t2t3 ( 1, 1, 1, 0, 0, 1, 0)
( 1, 1, 0, 0, 1, 1, 0)
t1 t2t3 t1
( 0, 0, 1, 1, 1, 1, 0) ( 0, 0, 2, 1, 0, 1 ,0)
t2t3 t4 (t2t3)t4 t4
(t2t3)t4 t2t3 ( 0, 0, 2, 0, 0, 1 ,1)
( 0, 0, 0, 1, 2, 1, 0) (0, 0, 1, 0, 1, 1, 1) t5
t4 t5 ( 0, 1, 2, 0, 0, 1 ,0)
(0, 0, 0, 0, 2, 1, 1) t2t3 t2t3
t5 t2t3 ( 0, 1, 1, 0, 1, 1 ,0)
( 0, 1, 0, 0, 2, 1, 0)
(t2t3)t4 - означает, что одновременно может сработать одна из пар
переходов: (t2t4) или (t3t4). Диаграмма отражает возможность параллельности вычислительных процессов. В рассматриваемом примере множество допустимых маркировок (состояний) равно 16. Причем из выделенной в качестве начальной маркировки 0 достижима лишь одна заключительная (тупиковая) маркировка T = ( 0, 1, 0, 0, 2, 1, 0), из которой уже не может идти продвижение маркеров по сети. Это гарантирует однозначное завершение процесса, моделируемого сетью. По диаграмме можно проследить множество последовательностей срабатывания переходов (траекторий процесса). Одна из возможных траекторий: t1 t3 t4 t5 t1 t4 t5 t2.
В общем случае, начальной маркировке может соответствовать несколько результирующих маркировок. Достижение каждой из них возможно при определенном распределении скоростей срабатывания переходов. В общем случае в некоторых позициях сети Петри возможно накопление бесконечного числа маркеров. Следовательно, множество допустимых состояний может не быть конечным. В сети Петри может не существовать тупиковых маркировок. Такого рода сетями моделируются циклические или автономные процессы.