Домашняя работа № 7 Проектирование конечного автомата. Эквивалентные Автоматы

Задание 1. Для заданного конечного автомата построить:

1. Неформальное описание

2. Описание множеств X, Q, Y

3. Функции переходов состояний и выходов

4. Граф переходов

5. Закодированную таблицу реализации КА

Задание 2.

1. Построить автомат А, имеющий 2 состояния (заданы множества состояний, входных и выходных сигналов)

2. Построить автомат В, эквивалентный А, имеющий 3 состояния

3. Доказать эквивалентность построенных автоматов, построив прямое произведение автоматов А и В (А х В)

Задание 1

Автомат «Чай-кофе»

I. Неформальное описание работы автомата:

• В начальном состоянии автомат ожидает монету. Если в этот момент в монетоприемник опустить монету в 2 рубля, автомат начнет готовить чай (закрывает монетоприемник, ставит стакан, насыпает концентрат, греет и наливает кипяток, открывает монетоприемник, подает сигнал «напиток готов»). Получив этот сигнал, автомат снова переходит в режим ожидания монеты и подает световой сигнал «положите монету».

• Если опустить монету в 5 рублей, автомат аналогичным образом в течение времени приготовит кофе.

• Сдачи автомат не выдает. Если опустить монету иного достоинства (не 2 и не 5) автомат ее выбросит в лоток для денег. Если опустить гнутую монету, автомат сломается.

II. Формальное описание автомата А = < X, Y, Q, q0, ψ, θ >,

1. Множества X, q, y

Множество входных сигналов Х:

x0 – положили 2 рубля

x1 – положили 5 рублей

x2 – положили иную монету

x3 – положили гнутую монету

x4 – сигнал «напиток готов»

Множество состояний Q:

q0 – ожидание монеты (начальное состояние)

q1 – приготовление чая

q2 – приготовление кофе

q3 – состояние неисправности

Множество выходных сигналов Y:

y0 – готовит чай (закрывает монетоприемник, ставит стакан, насыпает концентрат, греет и наливает кипяток, открывает монетоприемник, подает сигнал «напиток готов»)

y1 – готовит кофе (аналогично приготовлению чая)

y2 – выбрасывает монету в лоток

y3 – звуковой сигнал «автомат неисправен»

y4 – световой сигнал «положите монету» (подсвечивает монетоприемнник)

2. Описание автоматных функций

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

		Текущие состояния Q
	Ψ	q0	q1	q2	q3
Входные сигналы X	x0	q1	-	-	q3
	x1	q2	-	-	q3
	x2	q0	-	-	q3
	x3	q3	-	-	q3
	x4	-	q0	q0	q3
		Следующие состояния

Функция выходов (Θ) – описывает реакцию автомата на входные сигналы с учетом текущего состояния.

		Текущие состояния Q
	Ψ	q0	q1	q2	q3
Входные сигналы X	x0	y0	-	-	y3
	x1	y1	-	-	y3
	x2	y2	-	-	y3
	x3	y3	-	-	y3
	x4	-	y4	y4	y3
		Выходные сигналы