Теория вычислительных процессов Сети Петри для моделирования конечных автоматов и блок-схем Преподаватель: Веретельникова Евгения Леонидовна 1. - презентация

1 Теория вычислительных процессов Сети Петри для моделирования конечных автоматов и блок-схем Преподаватель: Веретельникова Евгения Леонидовна 1

2 Конечные автоматы Аппаратное обеспечение ЭВМ можно рассматривать на нескольких уровнях, и сети Петри могут моделировать каждый из них. На низком уровне вычислительные системы могут быть описаны автоматами. Автомат – это пятерка (Q, Σ, Δ, δ, Г), где Q – конечное множество состояний {q l, q 2,.., q k }; Σ – конечный входной алфавит; Δ – конечный выходной алфавит; δ : Q Σ Q – функция следующего состояния, отображаю- щая текущее состояние и текущий вход в следующее состояние; Г : Q Σ Δ – функция выхода, отображающая текущее состояние и текущий вход в выходной символ. 2

3 Конечные автоматы Автоматы часто представляют в виде графов переходов, как, например, на рис. 1. В графе переходов состояния представляются кружками, являющимися вершинами. Дуга из состояния q i в q j, помеченная a/b, означает, что, находясь в состоянии q i автомат при входе а перейдет в состояние q j, выдавая при этом символ b. Формально следовало бы записать δ(q i, а) = q j и Г (q i, а) = b. Входной алфавит определяет входы автомата из внешнего мира, а выходной алфавит – выходы автомата во внешний мир. В качестве примера рассмотрим автомат, который преобразует двоичное число, представленное последовате- льностью бит, начиная с младшего, в дополнение до двух (рис. 1). 3

4 Конечные автоматы В данном случае входной и выходной алфавит состоит из трех символов: 0, 1 и R. Автомат начинает работать в состоянии q 1. Символ сброса (R) означает конец (или начало) числа и возвращает автомат в исходное состояние. Выход автомата для символа сброса является просто его повторением. 4 Рис. 1.

5 Конечные автоматы Этот автомат (рис.2) при тех же самых входах вычисляет четность входного числа. Он начинает работу в состоянии q 1. Выход копирует вход до тех пор, пока входным символом не окажется символ сброса. Выходом для символа сброса будет 0 в случае нечетного числа и 1 – в случае четного числа. 5 Рис. 2.

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

7 Конечные автоматы Общий подход к моделированию связи между СП и внешним миром. 7 Представление сетью Петри конечного автомата

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

9 Альтернативный подход представления связи между СП и внешним миром. 9 Представление сетью Петри конечного автомата

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

11 Конечные автоматы Для конечного автомата (Q, Σ, Δ, δ, Г) мы определили сеть Петри (Р, Т, I, О) таким образом: P = Q U Σ U Δ, Т = {t q, σ | q Q, и σ Σ }, I(t q, σ ) = { q, σ }, О(t q, σ ) = { δ(q, σ), Г(q, σ)}. Эта сеть Петри является моделью конечного автомата. На рис. 3 изображена сеть Петри, соответствующая автомату с рис. 1, на рис. 4 – сеть Петри, соответствующая автомату с рис

12 Конечные автоматы Рис. 3. Сеть Петри, соответствующая автомату с рис

13 Конечные автоматы Рис. 4. Сеть Петри, соответствующая автомату с рис

14 Конечные автоматы Алгоритм: для построения сети Петри по конечному автомату необходимо выполнить следующие действия: а) построить конечный автомат ; б) расписать пятерку (Q, Σ, Δ, δ, Г), определяющую конечный автомат ; в) по пятерке (Q, Σ, Δ, δ, Г) получить теоретико- формальное описание сети Петри в виде четверки (Р, Т, I, О); г) нарисовать граф сети Петри. 14

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

16 Конечные автоматы Другое преимущество представления сети Петри связано с иными формами композиции. Например, параллельная композиция позволяет 16

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

18 Представление блок-схемы сетями Петри Вырожденным случаем параллельной системы обработки является система с одним процессом. Сначала рассмотрим, как сетью Петри может быть представлен отдельный процесс, а затем путем комбинации сетей Петри, представляющих нес- колько процессов, получим систему параллельных процессов. Отдельный процесс описывается программой. Эта программа может быть написана на многих языках, но для удобства примем общецелевой язык, такой, как Си, Паскаль, Бейсик, Фортран или даже язык ассемблера. Программа представляет два различных аспекта процесса: вычисление и управление. Вычисление связано с текущими арифметиче- скими и логическими операциями, вводом и выводом, обыч- ными манипуляциями над участками памяти и их содержи- мым. Управление же связано не со значениями или выполня- емыми вычислениями, а только с порядком их выполнения. 18

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

20 Представление блок-схемы сетями Петри Стандартный способ представления структуры управления программ – это блок-схемы. Блок-схема представляет поток управления в программе. Например, программа на слайде 21 (рис. 1) представляется блок-схемой на рис. 2. Заметим, что блок-схема не указывает конкретные вычисления, которые надо произвести, а только определяет структуру программы. Такая блок-схема является абстрактной. Рисунок на слайде 22 показывает, как можно проинтерпретировать блок-схему (слайд 21) программы, представленной рядом. Каждая последова- тельная программа может быть представлена в виде блок- схемы. Таким образом, показывая, как блок-схема может быть представлена сетью Петри, мы дадим представление сетью Петри программы. 20

21 Представление блок-схемы сетями Петри { cin>>y 1 ; cin>>y 2 ; y 3 = 1; while (y 1 > 0 ) { if (y 1 % 2 = =0) { y 3 = y 3 * y 2 ; y 1 = y 1 – 1; } y 2 = y 2 * y 2 ; y 1 = y 1 – 2; } cout

22 Представление блок-схемы сетями Петри ДействиеИнтерпретация acin>>y 1 ; cin>>y 2 ; y 3 = 1; by 1 > 0 ? cy 1 % 2 = =0 ? dy 3 = y 3 * y 2 ; y 1 = y 1 – 1; ey 2 = y 2 * y 2 ; y 1 = y 1 – 2; fcout

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

24 Представление блок-схемы сетями Петри Однако заметим, что в сети Петри действия моделируют- ся переходами, тогда как в блок-схеме действия моделиру- ются узлами. Kроме того, если движение нашей фишки текущей инструкции в блок-схеме нужно приостановить, это делается между узлами, на дугах, а не внутри блока. Таким образом, правильный перевод блок-схемы в сеть Петри заменяет узлы блок-схемы на переходы сети Петри, а дуги блок-схемы – на позиции сети Петри. Каждая дуга блок-схемы соответствует точно одной позиции в сети Петри. Узлы блок-схемы представляются по-разному в зависимости от типа узла: вычисления или принятия решения. На следующем слайде иллюстрируются оба способа перевода. На рис. 3 показан перевод блок-схемы в эквивалентную сеть Петри. 24

25 Представление блок-схемы сетями Петри Перевод узлов блок-схемы в переходы сети Петри 25

26 Представление блок-схемы сетями Петри Блок-схема программы Сеть Петри 26

27 Представление блок-схемы сетями Петри Необходимо сделать замечания относительно того, что обозначают компоненты сети Петри на предыдущем слайде. Для ответа на вопрос «что означают позиции» рассмотрим интерпретацию фишек блок-схемы счетчиком команд. Фишка, находящаяся в позиции, означает, что счетчик команд установлен на готовность выполнения следующей инструкции. Каждая позиция имеет единствен- ный выходной переход, за исключением позиции, которая предшествует принятию решения; такие позиции имеют по два выходных перехода, соответствующих истинному и ложному значению предиката. 27

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

29 Представление блок-схемы сетями Петри Алгоритм: для построения сети Петри по блок-схеме необходимо выполнить следующие действия: а) по условию задачи написать программу ; б) по (а) построить абстрактную блок-схему; в) по (а) и (б) написать интерпретацию каждого блока; г) по (б) нарисовать граф сети Петри 29