Задание 2

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

1. Построим граф переходов автомата А

2. Построим граф переходов автомата В.

Автомат В должен иметь 3 состояния Q ={q0, q1, q2}и быть эквивалентным автомату А.

Одно из состояний автомата А (S1) заменяем двумя эквивалентными ему состояниями (q2 и q1). Два этих состояния вместе взятые будут реагировать на сигналы также как реагирует S1.

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

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

4. Чтобы доказать эквивалентность автоматов А и В, построим автомат А х В, являющийся их прямым произведением.

4.1. Построим для автоматов A и B функции переходов состояний и выхода

А: Функция выходов (Θ)
s x	s0	s1
a	1	0
b	1	0

А: Функция переходов состояний (Ψ)
s x	s0	s1
a	s0	s1
b	s1	s0

В В: Функция выходов (Θ) q x q0 q1 q2 a 1 0 0 b 1 0 0 : Функция переходов состояний (Ψ)
q x	q0	q1	q2
a	q0	q1	q1
b	q2	q0	q0

2. Построим прямое произведение автоматов.

Входной алфавит произведения – общий X= {a,b}

Состояния произведения – есть пары состояний множителей

QA x QB = {(q0,s0), (q0,s1), (q1,s0), (q1,s1), (q2,s0), (q2,s1)} – всего 6 состояний

Начальное состояние произведения – есть пара начальных состояний множителей (q0,s0)‏

Выходной алфавит произведения – множество пар выходных символов множителей

YB x YB = {(0,0), (0,1), (1,0), (1,1)}

4. 3. Построим для произведения функции переходов состояний и выхода.

Функция переходов состояний (Ψ)
QA x QB x	(q0,s0)	(q0,s1)	(q1,s0)	(q1,s1)	(q2,s0)	(q2,s1)
a	(q0,s0)	(q0,s1)	(q1,s0)	(q1,s1)	(q1,s0)	(q1,s1)
b	(q2,s1)	(q2,s0)	(q0,s1)	(q0,s0)	(q0,s1)	(q0,s0)

Функция выходов (Θ)
QA x QB x	(q0,s0)	(q0,s1)	(q1,s0)	(q1,s1)	(q2,s0)	(q2,s1)
a	(1,1)	(1,0)	(0,1)	(0,0)	(0,1)	(0,0)
b	(1,1)	(1,0)	(0,1)	(0,0)	(0,1)	(0,0)