русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Конечные автоматы


Дата добавления: 2013-12-23; просмотров: 1730; Нарушение авторских прав


На низком уровне вычислительные системы могут быть описаны автоматами. Автомат — это пятерка (Q, ∑, ∆, δ, Г), где

Q — конечное множество состояний {q1, q2,…, qk};

∑ — конечный входной алфавит;

∆ — конечный выходной алфавит;δ : Q х ∑ → Q — функция следующего состояния, отображающая текущее состояние и текущий вход в следующее состояние; Г : Q х ∑→∆ — функция выхода, отображающая текущее состояние и текущий вход в выходной символ.

Автоматы часто представляют в виде графов переходов, как, на­пример, на рис. 3.9. В графе переходов состояния представляются кружками, являющимися вершинами. Дуга из состояния qi в qj помеченная a|b, означает, что, находясь в состоянии qi автомат при входе а перейдет в состояние qj выдавая при этом символ b. Формально следовало бы записать

δ(qi ,a)=qj и Г (qi ,a)=b

Входной алфавит определяет входы автомата из внешнего мира, а выходной алфавит — выходы автомата во внешний мир.

В качестве примера рассмотрим автомат, изображенный на рис. 3.9. Этот автомат преобразует двоичное число, представленное последовательностью бит, начиная с младшего, в дополнение до двух. В данном случае входной и выходной алфавит состоит из трех символов: 0, 1 и R. Автомат начинает работать в состоянии qt. Сим­вол сброса (R) означает конец (или начало) числа и возвращает автомат в исходное состояние. Выход автомата для символа сброса является просто его повторением.

 

Аналогичный автомат показан на рис. 3.10. При тех же самых входах этот автомат вычисляет четность входного числа. Он начи­нает работу в состоянии q1. Выход копирует вход до тех пор, пока входным символом не окажется символ сброса. Выходом для сим­вола сброса будет 0 в случае нечетного числа и 1 — в случае чет­ного числа.



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

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

ходными позициями переходов. Несмотря на возможную путаницу, эти термины наиболее естественны для обоих понятий.

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

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

 

 

 

Для конечного автомата (Q, ∑, ∆, δ, Г) мы определили сеть Петри (Р, Т, I, О) таким образом:

P = Q∆,

T = {tq,σ|q и σ ∑ },

I(tq,σ) ={q,σ},

O(tq,σ) = {δ(q,σ), Г(q,σ)}

Эта сеть Петри является моделью конечного автомата.

На рис. 3.13 изображена сеть Петри, соответствующая автомату с рис. 3.9. На рис. 3.14 - cеть Петри, соответствующая автомату с рис. 3.10.

При сравнении сетей Петри на рис. 3.13, 3.14 с эквивалентными автоматами на рис. 3.9, 3.10 возникают некоторые вопросы. Преж­де всего: почему модель сети Петри предпочтительнее описания конечным автоматом? Описание автоматом более понятно, чем описание сетью Петри, в которой 6 переходов, 24 дуги и 7 или 8 по­зиций. Это верно. Однако мы показали, что сети Петри могут пред­ставлять любую систему, представимую автоматом, и это свидетель­ствует о больших возможностях сетей Петри.

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

 

заметим, что выходной алфавит автомата с рис. 3.9 идентичен входному алфавиту автомата с рис. 3.10. Передавая выход автома­та с рис. 3.9 на вход автомата с рис. 3.10, можно построить ком­позицию автоматов, вычисляющую дополнение до двух и проверяю

щую четность. Такая композиция является автоматом с составны­ми состояниями, компоненты которых — это состояния обоих под­автоматов. В сетях Петри такая композиция есть просто совмещение выходных позиций первой сети с входными позициями второй. На рис. 3.15 показана композиция автоматов, а на рис. 3.16 — со­ставная сеть Петри.

Другое преимущество представления сети Петри связано с ины­ми формами композиции. Например, параллельная композиция позволяет компонентам композиции автоматов работать одновре­менно. В этом случае вновь получаем автомат с составными состоя­ниями, в то время как для сети Петри — это просто дублирование фишек во входах, соответствующих входным символам, и исполь­зование их во всех компонентах сети Петри. Наконец, на выходе мы просто выбираем соответствующие позиции выхода. Например, если мы хотим соединить параллельно две сети Петри (рис. 3.13 и 3.14), то в результате получим сеть Петри, подобную изобра­женной на рис. 3.17, которая вычисляет дополнение числа до двух и его четность. Если на входе появляется символ сброса, то выходом является четность.

 



<== предыдущая лекция | следующая лекция ==>
Достижимость и покрываемость сетей Петри. Пример. | Сохранение сетей Петри. P- и V- системы. Пример.


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.006 сек.