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

Тема: Построение простейших автоматов, распознающих

заданные свойства слова

Цели работы:

1) изучить основные понятия теории автоматов;

2) научиться строить автоматы.

Пояснения:

Абстрактный автомат – дискретный преобразователь информации; представляет собой множество, состоящее из шести элементов: S = {X, Q, Y, δ, λ, q₁}, S – абстрактный автомат; X – множество входных символов (входной алфавит автомата): X = {x₁,..., x_m}; Q – множество состояний автомата: Q = {q₁,..., q_n}; Y – множество выходных символов (выходной алфавит автомата): Y = {y₁,..., y_p}; δ – функция переходов автомата из одного состояния в другое: q_j = δ(q_i, x_k), где: q_j – следующее (новое) состояние автомата; q_i – текущее состояние автомата; x_k – текущий входной символ; λ – функция выходов: y_l = λ (q_i, x_k); q₁ – начальное состояние автомата (применяется также обозначение q₀). Автомат называется конечным, если множества X, Q, Y – конечны.

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

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

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

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

В табличном способе автоматные функции задаются двумя конечными таблицами, именуемыми соответственно матрицей переходов и матрицей выходов. В этих таблицах строки обозначаются буквами входного алфавита, а столбцы – буквами внутреннего алфавита (символами, кодирующими внутреннее состояние автомата). В матрице переходов на пересечении строки (x_k) и столбца (q_r) помещаются значения функции Y (q_r, x_k), а в матрице выходов – значения функции Q(q_r, x_k).

Диаграмма состояний (или иногда граф переходов) – графическое представление множества состояний и функции переходов. Представляет собой размеченный ориентированный граф, вершины которого – состояния КА, дуги – переходы из одного состояния в другое, а метки дуг – символы, по которым осуществляется переход из одного состояния в другое. Если переход из состояния q₁ в q₂ может быть осуществлен по одному из нескольких символов, то все они должны быть надписаны над дугой диаграммы.

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

Порядок выполнения работы:

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

1. Задан автомат А в табличном виде. Определить его входной и выходной алфавиты. Определить тип автомата и представить в виде графа. Определить выходную последовательность букв, если на вход поступает последовательность вида Х₃Х₁Х₂Х₁Х₂Х₃.

Таблица 1 – Задание № 1

№ варианта	Исходные данные
	S0 S1 S2 S3 Х1 S3 S0 S2 S0 Х2 S1 S2 S0 S3 Х3 S0 S1 S3 S1   S0 S1 S2 S3 Х1 Y1 Y2 Y3 Y5 Х2 Y1 Y1 Y4 Y2 Х3 Y5 Y4 Y1 Y5
	S0 S1 S2 S3 Х1 S3 S0 S2 S0 Х2 S1 S2 S0 S3 Х3 S0 S1 S3 S1   S0 S1 S2 S3 Х1 Y1 Y2 Y3 Y5 Х2 Y1 Y1 Y4 Y2 Х3 Y5 Y4 Y1 Y5
	S0 S1 S2 S3 Х1 S3 S0 S2 S0 Х2 S1 S2 S0 S3 Х3 S0 S1 S3 S1   S0 S1 S2 S3 Х1 Y1 Y2 Y3 Y5 Х2 Y1 Y1 Y4 Y2 Х3 Y5 Y4 Y1 Y5
	S0 S1 S2 S3 Х1 S3 S0 S2 S0 Х2 S1 S2 S0 S3 Х3 S0 S1 S3 S1   S0 S1 S2 S3 Х1 Y1 Y2 Y3 Y5 Х2 Y1 Y1 Y4 Y2 Х3 Y5 Y4 Y1 Y5
	S0 S1 S2 S3 Х1 S3 S0 S2 S0 Х2 S1 S2 S0 S3 Х3 S0 S1 S3 S1   S0 S1 S2 S3 Х1 Y1 Y2 Y3 Y5 Х2 Y1 Y1 Y4 Y2 Х3 Y5 Y4 Y1 Y5
	S0 S1 S2 S3 Х1 S3 S0 S2 S0 Х2 S1 S2 S0 S3 Х3 S0 S1 S3 S1   S0 S1 S2 S3 Х1 Y1 Y2 Y3 Y5 Х2 Y1 Y1 Y4 Y2 Х3 Y5 Y4 Y1 Y5
	S0 S1 S2 S3 Х1 S3 S0 S2 S0 Х2 S1 S2 S0 S3 Х3 S0 S1 S3 S1   S0 S1 S2 S3 Х1 Y1 Y2 Y3 Y5 Х2 Y1 Y1 Y4 Y2 Х3 Y5 Y4 Y1 Y5
	S0 S1 S2 S3 Х1 S3 S0 S2 S0 Х2 S1 S2 S0 S3 Х3 S0 S1 S3 S1   S0 S1 S2 S3 Х1 Y1 Y2 Y3 Y5 Х2 Y1 Y1 Y4 Y2 Х3 Y5 Y4 Y1 Y5
	S0 S1 S2 S3 Х1 S3 S0 S2 S0 Х2 S1 S2 S0 S3 Х3 S0 S1 S3 S1   S0 S1 S2 S3 Х1 Y1 Y2 Y3 Y5 Х2 Y1 Y1 Y4 Y2 Х3 Y5 Y4 Y1 Y5
	S0 S1 S2 S3 Х1 S3 S0 S2 S0 Х2 S1 S2 S0 S3 Х3 S0 S1 S3 S1   S0 S1 S2 S3 Х1 Y1 Y2 Y3 Y5 Х2 Y1 Y1 Y4 Y2 Х3 Y5 Y4 Y1 Y5

2. Построить автомат.

Таблица 2 – Задание № 2

№ варианта	Исходные данные
	Для выдачи билетов в автобусе. Автомат принимает монеты достоинством 2 или 5 руб., билет стоит 17 рублей.
	Для выдачи игровых жетонов. Автомат принимает монеты достоинством 2, 5 или 10 руб., жетон стоит 25 рублей

	Для выдачи пропусков на аттракцион. Автомат принимает монеты достоинством 2, 5 или 10 руб., пропуск стоит 28 рублей
	Для выдачи игровых жетонов. Автомат принимает монеты достоинством 2, 5 или 10 руб., жетон стоит 18 рублей
	Для выдачи магнитной карты в метро. Автомат принимает монеты достоинством 1, 2, 5 руб., карта стоит 13 рублей
	Для выдачи игровых жетонов. Автомат принимает монеты достоинством 2, 5 или 10 руб., жетон стоит 20 рублей
	Для выдачи билетов в автобусе. Автомат принимает монеты достоинством 2 или 5 руб., билет стоит 12 рублей.
	Для выдачи магнитной карты в метро. Автомат принимает монеты достоинством 1, 2, 5 руб., карта стоит 14 рублей
	Для выдачи пропусков на аттракцион. Автомат принимает монеты достоинством 2, 5 или 10 руб., пропуск стоит 14 рублей
	Для выдачи магнитной карты в метро. Автомат принимает монеты достоинством 1, 2, 5 руб., карта стоит 18 рублей

Требования к отчету: Отчет должен содержать:

- название практической работы;

- формулировку цели работы;

- краткие теоретические сведения по теме работы в виде таблиц, графиков, диаграмм, схем, рисунков и формул;

- результаты решения заданий;

- выводы по работе;

- краткие письменные ответы на контрольные вопросы.

Текст отчета набирается на компьютере. Допускается тип шрифта Times New Roman, размер 12 – 14, межстрочный 1,5 интервал, выравнивание текста по ширине странице, абзацный отступ 1,25.

Контрольные вопросы:

1) Что такое автоматы Мили и Мура?

2) Дайте определение входному и выходному алфавитам.

3) Опишите множество состояний автомата.

Учебная и специальная литература:

4) Спирина М.С., Спирин В.В. Дискретная математика: Учебник. – М.: Издательский центр «Академия», 2009. – 370 с.

5) Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для высш. учеб. заведений. – М.: Издательский центр «Академия», 2009. – 304 с.

6) Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВ – Петербург, 2008. – 352 с.