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

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

 

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

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

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

 

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

Построим для автоматов 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	q 0	q 1	q 2
a	q0	q1	q1
b	q2	q0	q0

 

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

 

Входной алфавит произведения – общий 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)}

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

 

Функция переходов состояний (Ψ)
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)

 

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

 

Перед нами несвязный граф (есть вершины, которые не связаны ребрами). В графе переходов прямого произведения автоматов есть недостижимые состояния (в них не существует пути из начального состояния, автомат не может перейти в эти состояния). Недостижимые состояния и переходы из них можно отбросить, т.к. они не влияют на поведение конечного автомата.

 

Исключим недостижимые состояния.

Прямое произведение автоматов А и В с выброшенными недостижимыми состояниями

 

 

 

Проверка: если на любую входную цепочку сигналов произведение автоматов реагирует также как и исходные автоматы, то исходные автоматы эквивалентны

 

Входная цепочка сигналов	Входная цепочка сигналов автомата А	Входная цепочка сигналов автомата В	Входная цепочка сигналов автомата А х В
abab	1100	1100	1100 1100
bbba	1010	1010	1010 1010
abba	1101	1101	1101 1101

 

 

По графу переходов видно, что из всех достижимых состояний под воздействием входных сигналов автомат А х В выдает такие же пары выходных сигналов, как и исходные автоматы, следовательно автоматы А и В эквивалентны.

 

 

⇐ Предыдущая123

Поделиться: