Дискретная математика. Громов Ю.Ю - 97 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

97
19. ТАБЛИЦА ПЕРЕХОДОВ КОНЕЧНОГО АВТОМАТА
Таблица, состоящая из z
ν
-подтаблицы и s
ν+1
-подтаблицы, которые
задают соответственно характеристические функции f
z
(x
ν
, s
ν
) и f
s
(x
ν
, s
ν
),
называется таблицей переходов конечного автомата. Общий вид таблицы
переходов представляет табл. 22. В некоторой ячейке z
ν
-подтаблицы
на пересечении столбца ξ
i
(i = 1, 2, …, p) и строки σ
j
( j = 1, 2, …, n) запи-
сывается значение функции f
z
(ξ
i
, σ
j
) ∈ Z, а в соответствующей ячейке
s
ν+1
-подтаблицы − значение функции f
s
(ξ
i
, σ
j
) ∈ S.
Для иллюстрации рассмотрим табл. 23, представляющую собой таб-
лицу переходов автомата A1, который приведён в качестве примера ко-
нечного автомата в предыдущем параграфе. В её z
ν
-подтаблице цифры 1
и 0 соответствуют выходным символам «считать» и «не считать», а в
s
ν+1
-подтаблице цифры 1, 2, 3, 4 и 5 − состояниям «новое слово», «ожида-
ние нового слова», «появление u», «появление u-n» и «появление u-n-d».
Заметим, что таблица переходов позволяет более кратко и компакт-
но, по сравнению со словесным описанием, охарактеризовать работу ко-
нечного автомата.
Одним из важных применений таблицы переходов является её ис-
пользование для перечисления автоматов, принадлежащих к тому или
иному классу.
Таблица 22
z
ν
s
ν+1
x
ν
s
ν
ξ
1
... ξ
i
... ξ
p
ξ
1
... ξ
i
... ξ
p
σ
1
... ... ... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ... ... ... ...
σ
j
... ... f
z
(ξ
i
, σ
j
) ... ... ... ... f
s
(ξ
i
, σ
j
) ... ...
... ... ... ... ... ... ... ... ... ... ...
σ
n
... ... ... ... ... ... ... ... ... ...
Таблица 23
z
ν
s
ν+1
x
ν
s
ν
d n u π λ d n u π λ
1 0 0 0 0 0 2 2 3 1 2
2 0 0 0 0 0 2 2 2 1 2
3 0 0 0 0 0 2 4 2 1 2
4 0 0 0 0 0 5 4 4 1 4
5 0 0 0 1 0 5 4 4 1 4

Страницы