ВУЗ:
Составители:
84
3. КОНЕЧНЫЕ АВТОМАТЫ И ЛОГИЧЕСКИЕ ФУНКЦИИ
3.1. Основные понятия теории автоматов
Рассмотрим некоторое абстрактное устройство (рис. 3.1) с n
входами и m выходами, на каждый вход которого может быть подан
произвольный символ из конечного алфавита
Х={х
1
, х
2
, …, х
k
},
называемого входным алфавитом.
Совокупность символов, поданных на вход
устройства, образует входное слово P
i
алфавита Х
данного устройства. Один из символов алфавита Х
(например, х
1
) соответствует пустому символу.
Если на некоторый вход устройства подается сим-
вол х
1
, то физически это означает отсутствие какого-либо возбужде-
ния по данному входу. Простейший пример входного алфавита:
Х={х
1
, х
2
}, где элементы х
1
и х
2
могут интерпретироваться как {0,1}.
На выходах устройства могут появляться выходные слова, со-
ставленные из символов выходного алфавита
Y={y
1
, y
2
, …, y
e
}.
В силу конечности как алфавитов Х и Y, так и входных и вы-
ходных слов (длина P
i
=n, а Q
j
=m) общее число различных входных и
выходных слов конечно.
Элементарный акт работы устройства состоит в том, что при
появлении на входе устройства в определенный момент времени
входного слова P
i
устройство выдает на выходах в тот же момент
комбинацию выходных символов, образующих выходное слово Q
j
.
Пусть выходное слово устройства полностью определяется
лишь входным словом. Тогда процесс функционирования такого
Рис. 3.1
Р
i
→
Q
j
1 2 n
1 2 m
Страницы
- « первая
- ‹ предыдущая
- …
- 86
- 87
- 88
- 89
- 90
- …
- следующая ›
- последняя »
