Проектирование конечного автомата. Эквивалентные Автоматы

Стр 1 из 3Следующая ⇒

Домашняя работа № 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 , q 0, ψ, θ >,

Множества X, Q, Y

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

		Текущие состояния Q
	Ψ	q₀	q₁	q₂	q3
Входные сигналы X	x₀	q₁	-	-	q₃
	x₁	q₂	-	-	q₃
	x ₂	q₀	-	-	q₃
	x ₃	q₃	-	-	q₃
	x ₄	-	q₀	q₀	q₃
		Следующие состояния

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

		Текущие состояния Q
	Ψ	q₀	q₁	q₂	q3
Входные сигналы X	x₀	y0	-	-	y3
	x₁	y1	-	-	y3
	x ₂	y2	-	-	y3
	x ₃	y3	-	-	y3
	x ₄	-	y4	y4	y3
		Выходные сигналы

Граф переходов автомата

Граф переходов автомата – более наглядная форма представления конечного автомата.

Возможных состояний автомата 4, следовательно у графа 4 вершины
Входных сигналов 5, следовательно у каждой вершины максимум 5 исходящих ребер (по одному на каждый входной сигнал).
Для каждого ребра:

- Направления указаны в таблице для функции переходов состояний.

- Входные сигналы - в таблице для функции переходов состояний

- Выходные сигналы - в таблице для функции выходов

4 Закодированная таблица реализации КА

Для аппаратной реализации предварительно осуществляют двоичное кодирование автомата. Для составления кодированной таблицы примем следующие обозначения:

Входные сигналы X (всего 5 сигналов, следовательно, понадобятся 3-значные коды, X-бит входного сигнала).

	Х1	Х2	Х3
х0 – положили 2 рубля	0	0	0
х1 – положили 5 рублей	0	0	1
х2 – положили иную монету	0	1	0
x3 – положили гнутую монету	0	1	1
х4 – сигнал «напиток готов»	1	0	0

Предыдущие состояния q (всего 4 состояния, следовательно, понадобятся 2х-значные коды b1,b2-биты предыдущего состояния).

	b1	b2
q0 – ожидание монеты	0	0
q1 – приготовление чая	0	1
q2 – приготовление кофе	1	0
q3 – состояние неисправности	1	1

Следующие состояния q (всего 4 состояния, следовательно, понадобятся 2х-значные коды B1,B2-биты предыдущего состояния).

	B1	B2
q0 – ожидание монеты	0	0
q1 – приготовление чая	0	1
q2 – приготовление кофе	1	0
q3 – состояние неисправности	1	1

Выходные сигналы Y (всего 5 сигналов, следовательно, понадобятся 3х-значные коды Z₁, Z₂ Z₃- биты выходных сигналов).

	Z1	Z2	Z3
y0 – готовит чай	0	0	0
y1 – готовит кофе	0	0	1
у2 – выбрасывает монету в лоток	0	1	0
y3 – сигнал «автомат неисправен»	0	1	1
y4 - сигнал «положите монету»	1	0	0

Кодированная таблица переходов и выходов

	Входной сигнал			Текущее состояние		Следующее состояние		Выходной сигнал
	X1	X2	X3	b₁	b₂	B₁	B₂	Z₁	Z₂	Z₃
x0	0	0	0	0	0	0	1	0	0	0
	0	0	0	0	1	-	-	-	-	-
	0	0	0	1	0	-	-	-	-	-
	0	0	0	1	1	1	1	0	1	1
x1	0	0	1	0	0	1	0	0	0	1
	0	0	1	0	1	-	-	-	-	-
	0	0	1	1	0	-	-	-	-	-
	0	0	1	1	1	1	1	0	1	1
x2	0	1	0	0	0	0	0	0	1	0
	0	1	0	0	1	-	-	-	-	-
	0	1	0	1	0	-	-	-	-	-
	0	1	0	1	1	1	1	0	1	1
x3	0	1	1	0	0	1	1	0	1	1
	0	1	1	0	1	-	-	-	-	-
	0	1	1	1	0	-	-	-	-	-
	0	1	1	1	1	1	1	0	1	1
x4	1	0	0	0	0	-	-	-	-	-
	1	0	0	0	1	0	0	1	0	0
	1	0	0	1	0	0	0	1	0	0
	1	0	0	1	1	1	1	0	1	1

Задание 2

Дано: Автомат А может находиться в 2х различных состояниях S = {s0, s1}, возможных входных сигналов два X = {a, b}, возможных выходных сигналов два Y = {0, 1}

Предварительная проверка эквивалентности автоматов А и В.

Возьмем несколько произвольных цепочек сигналов (abaа, bbba и тд) каждую из них сначала пропустим через автомат А, затем через В. Должны получаться пары одинаковых выходных цепочек.