Основы дискретной математики. Щипцов В.В - 41 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

41
Рассмотрим общие принципы анализа поведения автоматического
устройства. В процессе работы ДА может находиться в одном из состояний S
1
,
S
2
, ... , S
r
. Пусть в некоторый момент времени ДА находится в состоянии S
k
(k=1, 2, ... ,r) и под воздействием входного сигнала x, поступающего в
устройство в тот же момент времени, переходит в некоторое другое состояние
S
ℓ
(ℓ=1, 2, ..,r), вырабатывая при этом выходной сигнал y. Состояние S
ℓ
в
зависимости от поступающего сигнала (и от состояния блока “памяти”, если
речь идет о ДА с памятью), вообще говоря, может совпадать с состоянием S
k
.
Этот процесс перехода ДА из состояния S
k
в состояние S
ℓ
описывается
соотношением
S
k
→ xyS
ℓ
. (27)
Работа автоматического устройства будет определена, если аналогичное
соотношение задано для каждой пары состояний S
1
, S
2
, ... , S
r
.
Функционирование ДА удобно представить в виде графа, в вершинах которого
помещают состояния автомата, которые затем соединяют дугами в
соответствии с правилами работы автомата (27). При этом рядом с дугой S
k
S
ℓ
выходящей из вершины графа S
k
и входящей в вершину S
ℓ
пишут (x,y) -
зчения входного и выходного сигнала соответственно.
Нетрудно заметить, что приаботе ДА реализуется некоторый
формальный язык множество терминальных символов которого M
T
состоит из
значений выходного сигнала y, а множество нетерминальных символов M
N
- из
состояний S
1
, S
2
, ... , S
r
.
Рассмотрим конкретный пример.
Пример 12.
Функционирование ДА задано следующими правилами
вывода
S
1
→ x
2
y
2
S
1
, S
1
→ x
1
y
1
S
2
, S
2
→ x
1
y
1
S
2
, S
2
→ x
2
y
1
S
3
,
S
3
→ x
2
y
1
S
2
,
S
3
→ x
1
y
2
S
1
. (28)
Автомат установлен в начальное состояние S
1
, и на вход подана
последовательность символов (x
2
, x
1
, x
2
, x
1
). Определить последовательность
на выходе.
Решение.
Интерпретируем в виде графа правила работы автомата (28)
(рис. 14).

Страницы