Главная > Методы обработки данных > Введение в теорию конечных автоматов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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

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

Рассмотрим автомат М с множеством состояний Пусть обозначает множество всех последовательностей вход - выход, описываемых путями длины k, которые заканчиваются в состоянии По лемме 6.1, если М является автоматом с памятью то

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

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

Алгоритм 6.1. Задан автомат М с множеством состояний требуется найти память автомата М. (1) Полагаем Составляем последовательность (а) Если для некоторых , то переходим к (4). (б) Если для всех то k является памятью М. (4) (а) Если то увеличиваем k на и возвращаемся к (2). (б) Если , то М не является автоматом с конечной памятью.

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

являются элементами множества По матрице и диаграмме переходов для автомата М может быть построена таблица, в которой столбец содержит элементы если нет двух столбцов, имеющих общий член, то k должно быть памятью автомата М.

В качестве примера рассмотрим автомат показанный на рис. 6.6.

Таблица 6.3. Множества для

Рис. 6.6. Автомат

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

По (6.24) и (6.23) можно построить таблицу 6.3, в которой перечислены .

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

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

По (6.25) и (6.23) можно построить таблицу 6.4, в которой перечислены .

Таблица 6.4

Множества для

Автомат должен иметь память 2, так как никакая последовательность вход - выход не появляется в двух различных столбцах этой таблицы. Если бы автомат не был автоматом с конечной памятью, то этот факт обнаружился бы из таблицы, перечисляющей

<< Предыдущий параграф Следующий параграф >>
Оглавление