Как представить поведение конечного автомата
Практическая работа № 13
Тема: Решение задач по теории конечных автоматов. Алгебраическая теория конечных автоматов.
Цель: ознакомление с понятием конечного автомата; ознакомление с приемами построения лингвистических формально -логических моделей, описываемых конечно - автоматными функциями; усвоение навыков решения задач прогнозирования, управления, диагностики на конечно - автоматных моделях; освоение способов задания автоматов, построение абстрактного автомата первого рода, эквивалентного автомату второго рода.
Задачи: использования специального программного обеспечения для моделирования; построение адекватной модели.
Материальное обеспечение: практическая работа, программа Automata Guide.
Общие теоретические положения
Алгебраическая теория автоматов представляет собой ветвь теории систем. В приложениях автомат оказывается наиболее подходящим объектом для моделирования действия ряда логических элементов, когда не удается непосредственно воспользоваться вычислительными системами. Моделиалгебраической теории автоматов ограничиваются только такими явлениями, действие которых можно описать конечными автоматами. Рассматриваются только абстрактные состояния и их изменения под действием последовательности входных сигналов. Пренебрегают изменением состояний при установке электронных элементов - триггеров и линий задержки, а также в реакции на входные воздействия при установке этих элементов. Инженеры постоянно сталкиваются с конструированием конечных автоматов, так как последние являются важнейшими элементами вычислительных машин, средств связи и систем автоматического управления. Современная техника проектирования в основном эмпирическая, поэтому следовало бы приветствовать любые методы, которые вели бы к более надежному и хорошему конечному результату. Инженеры постоянно сталкиваются с конструированием конечных автоматов, так как последние являются важнейшими элементами вычислительных машин, средств связи и систем автоматического управления.
|
|
|
Конечный автомат – это функционирующий в дискретном времени Т
логико - математический объект
С=(X, Y, S, δ , λ) , где
Т ={0,1,2,…} – множество моментов времени,
X – конечный входной алфавит,
Y – конечный выходной алфавит,
S – конечное множество состояний,
δ :S× X → S – функция переходов,
λ :S× X →Y – функция выходов.
Если конечный автомат представляет собой модель поведения
реального объекта, то
• X – множество возможных действий по отношению к объекту;
• Y – множество возможных наблюдаемых реакций объекта;
|
|
|
• S – множество состояний, выражающих совокупность значений
ненаблюдаемых переменных, и играющих роль внутренней памяти;
• функция переходов s(t+1)=δ(s(t),x(t)) описывает процесс переходов автомата из состояния в состояние под влиянием входных
воздействий;
• функция выходов y(t)=λ(s(t),x(t)) описывает зависимость выходной реакции моделируемого объекта от его состояния и входного
воздействия.
Обе функции выражают причинно- следственные связи, определяющие закономерности поведения моделируемого реального объекта в дискретном времени .
Символы входного алфавита x(t)∈ X и символы выходного алфавита y(t)∈ Y представляют собою , как правило, лингвистические переменные, то есть слова и фразы естественного языка, аббревиатуры или жаргона предметной области.
Иными словами, конечный автомат функционирует в дискретные
такты времени T={0, 1, 2,...} так, что находясь в момент t∈T в состоянии s(t)∈S и получая на входе сигнал x(t)∈ X, он переходит в очередное состояние s(t+1) ∈ S и формирует на выходе сигнал y(t)∈ Y , то есть
s(t+1)=δ (s(t),x(t)),
y(t)=λ (s(t),x(t)) .
Последовательность символов входного или выходного алфавита
называют входным или выходным Uсловом U, соответственно . Длина слова определяется количеством следующих друг за другом символов. Тогда можно говорить о том, что конечный автомат формулирует (индуцирует) отображение множества входных слов в множество выходных. Другими словами, на временную последовательность входных воздействий (событий) он отвечает равной по длине временной последовательностью выходных реакций (событий).
|
|
|
Из множества слов, которые можно составить («слепить») из символов входного алфавита, выделяется подмножество слов, допустимых для данного начального состояния. Это те слова, которые реально реализуемы в отношении моделируемого объекта, находящегося в конкретном состоянии.
Например, если настольная лампа светит, то нельзя вставить ее вилку в розетку, так как она уже вставлена (иначе бы лампа не светилась). Поэтому все слова, начинающиеся с символа «вставить вилку в розетку», для названного состояния недопустимы, ибо они нереализуемы. Входное слово (длина равна 2) <вставить вилку в розетку, вставить вилку в розетку недопустимо при любом начальном состоянии. Получая входное слово, автомат поочередно заменяет его символы на символы выходного слова по правилам, определяемым функциями переходов и выходов.
|
|
|
При такой интерпретации конечно - автоматная модель может быть задана множеством правил, следующего типа :
« если текущее состояние есть p и входное событие есть х,
то выходное событие – у и следующее состояние – q»,
то есть q=δ (p, x), y= λ (p, x) .
где p, q – текущее и последующее состояния конечного автомата;
х, у – имена входного и выходного событий.
Или иначе, «если состояние и вход, то состояние и выход».
Запомните последнюю фразу. Она всегда напомнит вам о том , что
такое функции переходов и выходов.
Функции переходов и выходов, описывающие поведение конечного
автомата, могут быть заданы:
• в форме графа,
• в форме таблиц переходов и выходов,
• в форме построчного описания по установленным для него
синтаксическим правилам.
Как представить поведение конечного автомата
В форме графа
Для наглядности процесс функционирования конечного автомата
можно представить в виде направленного графа, вершины которого
сопоставляются с состояниями автомата, а направленные дуги – с.
переходами из состояний в состояния. Дуги при этом помечаются
символами входного алфавита, инициирующими переходы (над чертой), и символами выходного алфавита, выражающими реакцию объекта (под
чертой). При заданном начальном состоянии реакцию автомата на заданное входное слово нетрудно найти, пройдя от вершины, соответствующей начальному состоянию , по последовательности дуг, помеченных символами входного слова, считывая встречающиеся на пути символы выходного алфавита .
Пример. Пусть задан конечный автомат такой, что X={x1, x2} – множество входов, Y={y1, y2} – множество выходов , S={s1, s2, s3} – множество состояний. Предположим, что его поведение описывается функциями переходов и выходов, интерпретируемыми графом, приведенном на рисунке 1.
Такой автомат ведет себя следующим образом (проследите по графу ).
• При начальном состоянии s1 и входе x2 автомат переходит в состояние s3 и дает на выходе сигнал y2 .
• При начальном состоянии s3 и входном слове x2x1 автомат переходит в состояние s2 и дает выходное слово y2y1 .
• При начальном состоянии s1 и входном слове x1x2x1 выходная реакция автомата y2y2y1, конечное состояние s2.
• При начальном состоянии s2 и входном слове x1x2x1 выходная реакция автомата y1y1y2, конечное состояние s1.
• И так далее. Для любой пары <начальное состояние, входное слово> по графу можно найти конечное состояние автомата и его выходную реакцию (выходное слово).
Как задать конечный автомат таблицами
Переходов и выходов
Таблицы переходов и выходов являются одной из возможных форм представления функций переходов и выходов. Так как каждая из них –функция двух аргументов , то представляющие их таблицы двумерны. Это значит, что таблица состоит из столбцов и строк. В строках пишутся значения одного аргумента, в столбцах – другого. На пересечении столбца со строкой указывается значение функции, которое она принимает при данных значениях аргументов.
Пусть
X={x1, x2, …, xk} – множество входов конечного автомата;
Y={y1, y2, …, ym} – множество выходов;
S={s1, s2, …, sn} – множество состояний.
Функция переходов конечного автомата s(t+1)=δ(s(t),x(t)) описывает
процесс переходов автомата из состояния в состояние под влиянием
входных воздействий. Представляющая эту функцию таблица переходов
выглядит следующим образом.
Значение δ (si,xj), указанное в клетке таблицы на пересечении столбца si и строки xj – это значение функции переходов при указанных аргументах , то есть это состояние s(t+1) , в которое перейдет автомат из состояния si при входном воздействии xj.
Таблица переходов конечного автомата
Функция выходов конечного автомата y(t)=λ (s(t),x(t)) описывает
зависимость выходной реакции моделируемого объекта от его состояния и входного воздействия. Представляющая ее таблица выходов имеет
следующий вид.
Выходная реакция λ (si,xj) возникает при входном воздействии xj в
состоянии si.
Таблица выходов конечного автомата
Так как аргументы обеих функций одни и те же, то обе функции могут быть заданы одной таблицей, называемой совмещенной таблицей
переходов и выходов.
Совмещенная таблица переходов и выходов конечного автомата
Пример. У телевизора две кнопки включения - выключения электропитания: одна на корпусе, вторая на пульте дистанционного управления. Если подать электропитание , нажав кнопку на корпусе (КнК ), то засветится сигнальная лампочка. Если нажать эту кнопку при светящейся лампочке, то питание выключится и сигнальная лампочка погаснет. Если сигнальная лампочка светится , то нажатие кнопки на пульте ( КнП ) приводит к появлению картинки на экране телевизора . Если при наличии картинки нажать кнопку на пульте , то картинка исчезнет, но сигнальная лампочка будет светиться. Если нажать кнопку на пульте, когда индикатор не светит, то он по прежнему не светит , и картинка не появляется.
Тогда X={ Нажать КнК , Нажать КнП }; Y={СгнлЕсть, СгнлНет , КртнЕсть, КртнНет}; S={ Сост1, Сост2, Сост3)}.
Совмещенная таблица переходов и выходов будет выглядеть так.
Поведение автомата по такой таблице можно представить себе так.
Если начальное состояние Сост1 (см. первый столбец таблицы) и выполняется входное воздействие Нажать КнК ( см. первую строку ), то автомат переходит в состояние Сост2 и его выходная реакция (СгнлЕсть, КртнНет) (см. пересечение названных столбца и строки).
Если начальное состояние Сост2 (см. второй столбец таблицы ) и выполняется входное воздействие НажатьКнП ( см. вторую строку ), то автомат переходит в состояние Сост3 и его выходная реакция (СгнлЕсть, КртнЕсть) ( см. пересечение названных столбца и строки ).
И так далее.
Можете проверить, совпадает ли поведение автомата , заданное таблицей , с описанием рассматриваемого объекта, заданным текстом, и с вашим мысленным представлением этого, известного вам из повседневной деятельности , объекта.
Интерпретация состояний здесь такова: Сост1 – телевизор выключен; Сост2 – телевизор в дежурном режиме; Сост3 – телевизор в рабочем состоянии.
Пример построения конечного автомата:
1. Формулировка задания: d|a2(ab)*c
2. Диаграмма переходов конечного автомата:
Примечание:
| – обозначение начального состояния |
| – обозначение конечного состояния |
| – обозначение перехода изсостояния q 1 вcсостояние q 2 илипо a илипо b |
3. Построенный автомат является недетерминированным, потому что есть е-переходы. Детерминируем конечный автомат.
4. Для полученного конечного автомата построим таблицу состояний.
| a | b | c | d | |
| q0 | q1 | q2 | ||
| q1 | q3 | |||
| q2 | ||||
| q3 | q4 | q2 | ||
| q4 | q5 | |||
| q5 | q4 | q2 |
5. Конечный автомат является неминимизированным. Минимизируем .
Вводим дополнительное состояниеq6
Строим дерево разбора.
Алгоритм минимизации.
1. Пусть множество П(0,1,2,3,4,5,6) – множество всех состояний. Разобьем его на два подмножества согласно условию с состояниями (0,1,2,3,4,6) и (5).
2. Первое подмножество разбиваем еще на 2 с состояниями (0,1,3,6) и (2,4), потому что для всех входных символов переход по входному символу в состояние из одной и той же группы.
3. Первое подмножество делим на 2 с состояниями (0,1,6) и (3).
4. Перовое подмножество делим на 2 с состояниями (0,6) и (1).
5. Первое подмножество после предыдущего деления делим на 2 с состояниями (0) и (6).
В результате получили, что из состояний 2 и 4 можно оставить только одно, например 2. Количество состояний конечного автомата уменьшилось на одно.
Из полученного дерева видим, что состояния q 2 иq 4можно объединить в одно состояние q 3.
Дата добавления: 2019-02-22; просмотров: 2110; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!