КС309 МДК01.02 Математический аппарат для построения компьютерных сетей 09.09.2022

«Основы теории конечных автоматов»

Дисциплина: Моделирование процессов и систем

Преподаватель: Максимов Петр Викторович

Определение конечного автомата

• Конечный автомат – это система, имеющая входные, выходные сигналы и имеющая конечное число внутренних состояний, а также функции переходов между состояниями.

Теория автоматов – это раздел дискретной математики, который посвящен автоматным моделям реальных устройств, предназначенных для обработки дискретной информации с помощью заданного алгоритма, без учета их физических и технических характеристик.

Устройство, обрабатывающее информацию, обменивается ею с внешней средой через входные и выходные каналы, по которым поступает информация.

Входные сигналы (S) представляют собой воздействия, генерируемые внешней средой и которые влияют на поведение исследуемой системы.

Результат обработки этой информации выдается – выходными сигналами (R) .

Содержимое памяти в настоящее время называется - состоянием автомата (К). Состояния автомата – это величины, которые не являются ни входными, ни выходными сигналами (еще их называют промежуточными переменными).

Схематично система может быть представлена «черным ящиком» (Рис.1) с конечным числом входных (S) и выходных сигналов, промежуточные переменные сосредоточенны внутри ящика.

Конечный автомат – это система, имеющая конечное число состояний

В любой момент времени автомат находится только в одном состоянии

Переход состояний – это изменение текущего состояния, вызванное внешним событием

В ответ на поступившее событие автомат может перейти в новое состояние или остаться в пережнем

То, в какое состояние перейдет автомат, зависит как от текущего состояния, так и от события

Определение конечного автомата

• Входной алфавит S – это конечное множество возможных входных сигналов.
• Выходной алфавит R – это множество возможных выходных сигналов.
• Алфавит состояний K – это множество возможных внутренних состояний автомата.

В любой момент времени автомат находится только в одном состоянии

Переход состояний – это изменение текущего состояния, вызванное внешним событием (Входным сигналом)

Устройство, как правило, имеет память, содержимое которой во время работы устройства может меняться. Изменения зависят: от содержимого памяти в данный момент времени , а также от входного сигнала , поступившего в этот момент по входному каналу.

Выходной сигнал в каждый момент времени зависит от входного сигнала и от состояния автомата в настоящий момент времени

В ответ на поступившее событие автомат может перейти в новое состояние или остаться в пережнем

То, в какое состояние перейдет автомат, зависит как от текущего состояния, так и от события

Определение конечного автомата

На этих множествах задают два логических оператора:

• Функция переходов g – определяющая переход автомат из одного состояния в другое под действием входных сигналов ( т.е. имеется состояние, подается вход и автомат переходит в другое состояние)

• Функция выходов p – определяющая зависимость выходного сигнала автомата от состояния автомата и входного сигнала.

Будем считать, что в каждый момент времени t=1,2,3, … на вход системе подается некоторый сигнал из множества S, а на выходе появляется соответствующий сигнал из множества R. Состояние автомата используется для описания систем, выходные сигналы, которые зависят не только от входных сигналов в данный момент времени, но и от некоторой предыстории, т.е. сигналов, которые поступали на входы системы ранее. Следовательно, конечные автоматы относятся к последовательным схемам, которые обладают памятью.

Определение конечного автомата

Пример 1, автомат с памятью

Пример 2, автомат без памяти

Рассмотрим примеры автомата с памятью и без памяти

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

Определение конечного автомата

Конечным автоматом , называется система с конечным входным алфавитом S , конечным выходным алфавитом R , конечным множеством состояний K и двумя характерическими функциям

и g и p .

M = {S, R, K, g, p}

Конечность множества состояний говорит о том, что автомат (именно поэтому он называется конечным) обладает ограниченной памятью.

Критерий применимости автоматного подхода

С простым поведением Со сложным поведением

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

Пример Вы сможете рассмотреть самостоятельно в выданной Вам теории

Способы задания конечных автоматов.

Для описания конечных автоматов применяются:

• Таблица переходов состояний – это табличное представление конечного автомата

• Диаграмма перехода состояний – это представление конечного автомата в виде графа, вершины которого соответствуют состояниям, а ребра – переходам между ними .

Для задания конечного автомата необходимо описать все элементы множества M = {S, R, K, g, p}, т.е. входной, выходной и внутренний (состояний) алфавиты, а также функции переходов и выходов.

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

Таблицы и графы – это различные формы представления характерических функций конечного автомата, который описывает систему. Такое представление совершенно необходимо для проведения любого точного анализа или синтеза конечного автомата. Поскольку одной формой представления автомата выгодно пользоваться при одних обстоятельствах, другой – при других, необходимо знать их все.

Способы задания конечных автоматов.

Пример 2 , совмещенная таблица переходов и выходов

Состояния (К) : Идет, стоит

Входные сигналы (S) : Свет зеленый, свет зеленым мигающий, Свет красный.

Выходные сигналы (R): Начало движения, продолжение движения, ожидание и остановка.

Входные сигналы

Состояния

Свет зеленый

Стоит

Свет зеленый мигающий

Идет

Начало движения, переход в состояние идет

Свет красный

Продолжение движения, остается в состоянии идет

Стоит, переход в состояние ожидания

Остановка, переход в состояние стоит

Стоит, переход в состояние ожидания

Остановка, переход в состояние стоит

Таблицы и графы – это различные формы представления характерических функций конечного автомата, который описывает систему.

Характеристические функции g и p , могут быть представлены в форме таблицы переходов.

Чтобы задать автомат табличным способом , нужно заполнить его таблицу выходов и переходов , исходя из функции выходов р и функции переходов g .

Строки этих таблиц соответствуют входным сигналам, а столбцы – состояниям. На пересечении строки и столбца в таблице переходов ставится состояние, в которое автомат перейдет под воздействием входного сигнала (S); а в таблице выходов – соответствующий этому переходу выходной сигнал.

Удобнее составлять совмещенную таблицу переходов и выходов представленную на рисунке.

Способы задания конечных автоматов.

Граф переходов – состоят из вершин и ориентированных дуг.

Пример 3, граф переходов

Граф переходов - представляет собой структуру, состоящую из вершин, изображаемых в виде малых кружков, и ориентированных дуг, изображаемых в виде линий между парами вершин и снабженных стрелками, указывающими направление от одной вершины к другой. Граф переходов, описывающий автомат с n постоянными , содержит n вершин , причем каждая вершина соответствует одному состоянию автомата; состояние, изображаемое вершиной, снабжается обозначением, соответствующим этому состоянию.

Дуга проводится из вершины 1в вершину 2 тогда, когда в данном автомате возможен переход из состояния 1 в состояние 2 по некоторому входному сигналу. Стрелка указывает направление перехода. Над началом дуги указывается входной сигнал, а над стрелкой – выходной сигнал (Мура)

Либо граф Мили, сигналы указываются посередине дуги.

В системах с высокой степенью зависимости от состояния диаграммы или таблицы переходов состояний могут оказаться очень полезными для понимания функционирования системы.

Такая спецификация конечного автомата зачастую более точна и понятна, чем словесное описание.

Способы задания конечных автоматов

Каждую форму представления можно задать двумя классами автоматов :

• Автоматы Мура (Moore) – выходные сигналы зависят только от текущего состояния.

• Автоматы Мили (Mealy) Мили - выходные сигналы зависят как от текущего состояния, так и от текущих значений входных сигналов.

Иначе говоря:

• В автомате Мура все действия привязаны к состояниям. В автомате Мили все действия привязаны к переходам.
• В автомате Мура все действия привязаны к состояниям.
• В автомате Мили все действия привязаны к переходам.

В реальных ситуациях модель обычно представляет собой комбинацию машин Мура и Мили.

Области применения конечного автомата

• Пример 1 , применение метода конечных автоматов при моделировании работы электронного сейфа - открытие двери с кодовым замком.

Состояниями автомата будут являться:

• Закрыт
• Проверка кода
• Открыт

Входные сигналы , которые должен принимать автомат, будут следующие:

• Верный код
• Неверный код

Области применения конечных автоматов охватывают принципиально различные классы программных подсистем. В действительности круг задач, при решении которых целесообразно использовать автоматный подход, очень широк и включает создание программных систем. Однако автоматные модели, используемые при создании различных видов программных систем, могут отличаться друг от друга.

Рассмотрим несколько примеров из абсолютно разных сфер.

Области применения конечного автомата

Составим таблицу переходов системы:

Входные сигналы

Состояния

ЗакрытК1

Верный код S1

Проверка кодаК2

Индикатор выкл., переход в состояние проверка кода(Z1)

Неверный код S2

ОткрытК3

индикатор выкл., переход в состояние проверка кода (Z1)

индикатор зеленый, переход в состояние открыт(Z2)

сигнал открытия, остается в состоянии открыт

индикатор красный, переход в состояние закрыт(z3)

(Z4)

---------

Области применения конечного автомата

Составим граф переходов:

Области применения конечного автомата

Пример 2 , система климат – контроля в автомобиле.

Состояния системы:

• системы выкл ., когда система находится ни в одном их состояний, они находится в покое;
• охлаждение , система охлаждает воздух до установленной температуры;
• обогрев , система осуществляет нагрев воздуха в салоне до нужной температуры .

Входными сигналами будем считать :

• холодно , человек, находящийся в автомобиле замерз;
• жарко , человеку, находящемуся в автомобиле стало жарко;
• климат-контроль выключен , систему выключили за ненадобностью.

В автомобильной отрасли особенно явно выражается применение конечных автоматов. Стоит только подумать сколько раз в одном автомобиле можно использовать метод конечного автомата: автоматическое включение дворников, датчики парковки, система круиз - контроля, система климат – контроля, автоматические изменение яркости света фар.

Рассмотрим пример, система климат – контроля. В автомобиле находится человек, которому может стать жарко или хорошо. Он сам определяет комфортные для себя условия, может включить или выключить систему.

Области применения конечного автомата

Составим таблицу переходов системы:

Входные сигналы

Состояния

Система выкл.

Холодно

Охлаждение

Включение повышения t, переход в состояние «Обогрев»

Жарко

Включение понижения t, переход в состояние «Охлаждение»

Обогрев

Выключение системы

Выключение понижения t, переход в состояние «Обогрев»

Понижение t, остается в состоянии «Охлаждение»

Увеличение t, остается в состояние «Обогрев»

-----

Выключение повышения t, переход в состояние «Охлаждение»

Переход в состояние «Система выкл.»

Переход в состояние «Система выкл.»

ЗАДАНИЕ

Построить Граф переходов для Примера 2 , системы климат – контроля в автомобиле