по МДК 01.02: Математический аппарат для построения компьютерных сетей наименование работы: Решение задач по теории конечных автоматов. Алгебраическая теория конечных автоматов.

Смоленский колледж телекоммуникаций
(филиал) федерального государственного
бюджетного образовательного учреждения высшего образования
«Санкт-Петербургский государственный университет телекоммуникаций
им. проф. М.А. Бонч-Бруевича»












Практическая работа №7

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

наименование работы: Решение задач по теории конечных автоматов. Алгебраическая теория конечных автоматов.

для специальности: 09.02.02
работа рассчитана на 2 часа
составлена преподавателем: Скряго О.С.


















Смоленск, 2016


1. Цель работы: овладение практическими навыками с приемами построения лингвистических формально - логических моделей, описываемых конечно - автоматными функциями; усвоение навыков решения задач прогнозирования, управления, диагностики на конечно - автоматных моделях; освоение способов задания автоматов, построение абстрактного автомата первого рода, эквивалентного автомату второго рода.

2. Литература:
2.1. Асанов, М. О. Дискретная математика: графы, матроиды, алгоритмы: Учебное пособие. 2-е изд. / М.О. Асанов , В.А.Баранский , В.В. Расин - СПб. : Издательство «Лань» 2012 г. 368с. - ISBN 978-5-8114-1068-2
2.2. Мельников, О.И. Теория графов в занимательных задачах. Изд.4, испр. и доп./О.И. Мельников 2012. 240 с. М.: Книжный дом "Либриком" ISBN978-5-9775-0232-0
2. 3. Новиков, Ф.А. Дискретная математика: Учебник для вузов. 2-е изд. Стандарт третьего поколения: учебник / Ф.А. Новиков. - СПб. : Питер 2012, 400с.- ISBN 978-5-496-00015-4

3. Подготовка к работе:
3.1. Повторить тему «Теория конечных автоматов».
3.2. Подготовить бланк отчета (см.п.7).
3.3. Ответить на вопросы допуска:
3.3.1. Что представляет собой алгебраическая теория автоматов?
3.3.2. Сформулируйте определение конечного автомата?
3.3.3. Как задается конечно-автоматная модель?
4. Основное оборудование: ПЭВМ.
5. Задание:
1.1. Выполните задания согласно варианту. Построить конечные автоматы в программе AutomataGuide. Проработать основные операторы данной программы.
Вариант 1.
Вариант 2.
Вариант 3.

Вариант 4.

Вариант 5.


6. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ.
6.1. Ознакомиться с заданием.
6.2. Определить номер варианта (в соответствии с номером в журнале).
6.3. Повторить правила техники безопасности:
Правила техники безопасности в компьютерном классе.
Перед началом работы необходимо убедиться в отсутствии видимых повреждений аппаратуры.
Работа с компьютером производится строго по указаниям преподавателя.
Запрещается:







Разъединять или соединять разъемы аппаратуры;
Прикасаться к экрану монитора;
Включать и выключать аппаратуру без указания преподавателя;
Класть какие-либо предметы на монитор, системный блок или клавиатуру;
Работать во влажной одежде, а также влажными или грязными руками;
Пытаться самостоятельно исправлять возникшую в аппаратуре неисправность.
Включите компьютер.
Включите в сеть стабилизатор напряжения (если он имеется).
Включите принтер (если он имеется).
Включите монитор.
Включите системный блок (большая кнопка на передней панели).
Выключение компьютера.
Завершите выполнение всех программ.
Выполните команду: Пуск ( Завершение работы ( Выключить компьютер (Alt+F4 Завершение работы).
Выключите системный блок.


6.4. Приступить к выполнению задания.
6.5.Оформить отчет.

7. Содержание отчёта:
7.1. Название и цель работы.
7.2 Ответы на вопросы допуска.
7.2. Указать номер варианта, привести условия заданий своего варианта.
7.3. Представить результат выполнения заданий.
7.4. Ответы на контрольные вопросы.
7.5. Вывод о проделанной работе.

8. Контрольные вопросы:
8.1. Укажите, где применяются конечные автоматы?
8.2. Как можно представить (задать) конечный автомат?
8.3. Можно ли использовать конечный автомат в словаре?
8.4. Что значит конечный автомат неминимизированный?
8.5. Какой автомат называют детерминированный и минимизированный?

Составил преподаватель __________________________Скряго О.С.
Приложение

Алгебраическая теория автоматов представляет собой ветвь теории систем. В приложениях автомат оказывается наиболее подходящим объектом для моделирования действия ряда логических элементов, когда не удается непосредственно воспользоваться вычислительными системами. Модели алгебраической теории автоматов ограничиваются только такими явлениями, действие которых можно описать конечными автоматами. Рассматриваются только абстрактные состояния и их изменения под действием последовательности входных сигналов. Пренебрегают изменением состояний при установке электронных элементов - триггеров и линий задержки, а также в реакции на входные воздействия при установке этих элементов. Инженеры постоянно сталкиваются с конструированием конечных автоматов, так как последние являются важнейшими элементами вычислительных машин, средств связи и систем автоматического управления. Современная техника проектирования в основном эмпирическая, поэтому следовало бы приветствовать любые методы, которые вели бы к более надежному и хорошему конечному результату. Инженеры постоянно сталкиваются с конструированием конечных автоматов, так как последние являются важнейшими элементами вычислительных машин, средств связи и систем автоматического управления. 
Конечный автомат – это функционирующий в дискретном времени Т
логико - математический объект
С=(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 – телевизор в рабочем состоянии.
Пример построения конечного автомата:
Формулировка задания: d|a2(ab)*c
Диаграмма переходов конечного автомата:

Примечание:

– обозначение начального состояния

HYPER13 EMBED PBrush HYPER14HYPER15
– обозначение конечного состояния

HYPER13 EMBED PBrush HYPER14HYPER15
– обозначение перехода изсостоянияq1вcсостояниеq2илипоaилипоb


Построенный автомат является недетерминированным, потому что есть е-переходы. Детерминируем конечный автомат.




Для полученного конечного автомата построим таблицу состояний.

a
b
c
d

q0
q1


q2

q1
q3




q2





q3
q4

q2


q4

q5



q5
q4

q2



Конечный автомат является неминимизированным. Минимизируем .
Вводим дополнительное состояниеq6

Строим дерево разбора.
Алгоритм минимизации.
Пусть множество П(0,1,2,3,4,5,6) – множество всех состояний. Разобьем его на два подмножества согласно условию с состояниями (0,1,2,3,4,6) и (5).
Первое подмножество разбиваем еще на 2 с состояниями (0,1,3,6) и (2,4), потому что для всех входных символов переход по входному символу в состояние из одной и той же группы.
Первое подмножество делим на 2 с состояниями (0,1,6) и (3).
Перовое подмножество делим на 2 с состояниями (0,6) и (1).
Первое подмножество после предыдущего деления делим на 2 с состояниями (0) и (6).
В результате получили, что из состояний 2 и 4 можно оставить только одно, например 2. Количество состояний конечного автомата уменьшилось на одно.

Из полученного дерева видим, что состояния q2 иq4можно объединить в одно состояние q3.

Получили детерминированный и минимизированный конечный автомат.




















Рисунок 29Рисунок 32Рисунок 1Рисунок 13Рисунок 4Root Entry

Приложенные файлы

  • doc 112
    Скряго
    Размер файла: 2 MB Загрузок: 19

Добавить комментарий