Пусть заданы три конечных непустых упорядоченных множества , , , которые называются соответственно входным алфавитом, алфавитом состояний, выходным алфавитом.
Определение: Детерминированным конечным автоматом называется объект , который в дискретные моменты времени (такты) может принимать состояния из алфавита (в момент времени он находится в начальном состоянии ), причем в каждом такте . на него воздействует какой-либо символ , и он переходит из предыдущего состояния , определяемого функцией перехода = (, ) и выдает выходной символ , определяемый функцией выходов .
Автомат, находящийся в момент в состоянии , называется инициальным. В зависимости от способа задания функции различают конечные автоматы следующих видов:
1. = (, ) - автомат 1-го рода (Мили)
2. = (, ) - автомат 2-го рода
3. = (, ) - правильные автоматы
4. = () - правильные автоматы 1-го рода
5. = () - правильные автоматы 2-го рода (Мура)
6. = - абстрактные автоматы 1-го рода
7. = - абстрактные автоматы 2-го рода
8. = () - автоматы без памяти (комбинационные схемы).
|
|
Если функции и определены всюду на множествах совокупностей значений своих аргументов, то конечный автомат называется вполне определенным. В противном случае автомат называется частичным.