Определение памяти автомата

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

Рассмотрим автомат М с множеством состояний {σ₁, σ₂,..., σ_n}. Пусть Q^{( l )}_k обозначает множество всех последовательностей вход-выход, описываемых путями длины k, которые заканчиваются в состоянии σ_i. По лемме 6.1, если М является автоматом с памятью µ, то

По теореме 6.1, если М не является автоматом с конечной памятью, то

Следовательно, для определения памяти автомата можно сформулировать следующий алгоритм.

Алгоритм 6.1. Задан автомат М с множеством состояний {σ₁, σ₂,..., σ_n}; требуется найти память автомата М. (1) Полагаем k=1. (2) Составляем последовательность Q⁽¹⁾_k,

Q⁽²⁾_k,..., Q⁽ⁿ⁾_k,. (3) (а) Если Q⁽ⁱ⁾_k ∩ Q^(j)_k ≠ 0 для некоторых i и j ≠ i, то переходим к (4). (б) Если Q⁽ⁱ⁾_k ∩ Q^(j)_k = 0 для всех i и j ≠ i, то k является памятью М. (4) (а) Если k<n(n—1)/2, то увеличиваем k на 1 и возвращаемся к (2). (б) Если k = n(n—1)/2, то М не является автоматом с конечной памятью.

Выполнение алгоритма 6.1 облегчается при использовании матриц переходов высокого порядка, введенных в главе 2. В клетке (i, j) матрицы переходов k-го порядка записаны все пути длины k, ведущие из состояния σ_i в состояние σ_j. Поэтому клетки j-го столбца матрицы представляют все пути длины k, заканчивающиеся в состоянии σ_j. Таким образом, последовательности вход-выход, представленные путями, перечисленными в столбце матрицы ,

являются элементами множества Q^{( j )}_k . По матрице и диаграмме переходов для автомата М может быть построена таблица, в которой j-й столбец содержит элементы Q^{( j )}_k; если нет двух столбцов, имеющих общий член, то k должно быть памятью автомата М.

В качестве примера рассмотрим автомат A28, показанный на рис. 6.6. Матрица переходов автомата A28 задана

выражением (6.23), а матрица переходов первого порядка — выражением (6.24).

По (6.24) и (6.23) можно построить таблицу 6.3, в которой перечислены Q⁽¹⁾₁, Q⁽²⁾₁, Q⁽³⁾₁, Q⁽⁴⁾₁.

Так как последовательности вход-выход (0/1) и (1/1) появляются в двух различных столбцах этой таблицы, память автомата A28 будет превышать 1. Выражение (6.25)

представляет собой матрицу переходов второго порядка для автомата A28.

По (6.25) и (6.23) можно построить таблицу 6.4, в которой перечислены Q⁽¹⁾₂, Q⁽²⁾₂, Q⁽³⁾₂, Q⁽⁴⁾₂.

Автомат A28 должен иметь память 2, так как никакая последовательность вход-выход не появляется в двух различных столбцах этой таблицы. Если бы автомат A28 не был автоматом с конечной памятью, то этот факт обнаружился бы из таблицы, перечисляющей Q⁽¹⁾₆, Q⁽²⁾₆, Q⁽³⁾₆, Q⁽⁴⁾₆.