Z S W

Рис. 2.1. Структурная модель абстрактного автомата (нулевой уровень)

Иными словами, у полностью определенного автомата области определения функций δ, λ совпадают с множеством A х Z – множеством всевозможных пар вида (am, zf). У не полностью определенного, или частичного, автомата функцииδ или λ определены не для всех пар (am, zf) A х Z.

Состояние частичного автомата, соответствующее паре (am, zf), на котором функция переходов не определена, называют неиспользуемым состоянием автомата. Остальные состояния называют используемыми [5].

Если на каком-либо используемом состоянии автомата не определена функция выходов, то говорят, что этому состоянию соответствует безразличное состояние выхода. В частном случае может быть безразличным не состояние выхода, а лишь один или несколько выходных сигналов, набор значений которых определяет данное состояние выхода [5].

Чтобы задать конечный автомат S, необходимо описать все компоненты вектораS = (Z, A ,W, δ, λ, a 1), т.е. входной и выходной алфавиты и алфавит состояний, а также функции переходов и выходов. Среди множества состояний может быть выделено начальное состояния автомата a1, в котором автомат находится в момент t = 0.

2.3. Формальная классификация автоматов

Один из способов классификации абстрактных автоматов состоит в рассмотрении мощностей множеств A, Z, W и общих свойств функций переходовδ и выходовλ, которые также называют характеристическими [1], [2], [13].

19

1.Автомат инициальный – автомат, для которого зада-

но a1 (начальное состояние) и который всегда начинает функционировать с этого состояния.

2.Автомат не инициальный – автомат, для которого в

качестве начального состояния может быть взято л ю- бое из допустимых его состояний A={a1,…am…aF}.

3. Автомат конечный – автомат, у которого одновременно конечны множества входного, выходного алфавитов и

алфавита состояний, т.е. Z < ∞, A < ∞ и W < ∞ .

4. Автомат бесконечный – автомат, у которого бесконечны хотя бы одно из множеств входного, выходного алфави-

тов или алфавита состояний, т.е. Z = ∞, или A = ∞, или

W= ∞.

5.Автомат без памяти (комбинационный автомат) – автомат, у которого множество состояний состоит из одного

элемента, т.е. A =1. Для такого автомата характерно то, что

функция переходов вырождается (отсутствует), а функция выходов однозначно определяет выходной символ как некоторую функцию от входного символа, т.е. W= λ(Z).

6. Автомат без входов (автономный автомат) – автомат, у которого множество входных символов состоит из од-

ного элемента Z =1, т.е. автомат не имеет входов или, что то

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

7. Автомат без выхода (распознаватель) – автомат, у которого множество выходных символов состоит из одного символа. Поведение автомата без выхода можно охарактеризо-

20