6.3. Свойства автоматов с конечной памятью

Конечный автомат, представляющий систему с конечной памятью, будем называть автоматом с конечной памятью. Таким образом, автомат с конечной памятью М, является автоматом, в котором

где любой из аргументов (за исключением одного из ) может быть несущественной переменной. Числа называются соответственно памятью и памятью z автомата М. Целое число

называется максимальной памятью М. Если в дополнение к (6.10) имеет место

то будем говорить, что автомат М имеет память . Таким образом, является памятью автомата в том случае, если предсказание выходной реакции, по крайней мере, на одно входное воздействие в момент времени требует знания входного воздействия и (или) выходной реакции в момент времени возможно, входных воздействий и выходных реакций, которые возникают в более поздние моменты времени), но не требует знания каких-либо входных воздействий и выходных реакций в моменты времени более ранние, чем

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

Лемма 6.1. В минимальном автомате с памятью

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

реакции на Однако это невозможно, так как по предположению автомат имеет память и, следовательно,

Это равенство означает, что выходная реакция в настоящий момент времени может быть однозначно определена с помощью прошедшей последовательности вход - выход длиной Лемма, таким образом, следует из полученного противоречия.

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

Рис. 6.3. - совпадающие пути.

Лемма 6.1 означает, что диаграмма переходов автомата с памятью должна обладать следующими свойствами. Пути, которые являются -совпадающими. должны пересекаться в своих конечных состояниях. Кроме того, должна быть, по крайней мере, одна пара совпадающих путей, которые пересекаются в своих конечных состояниях, но не имеют других пересечений. Такая пара путей показана на рис. 6.3.

Лемма 6.2. Если в заданном автомате М

то M является автоматом с максимальной памятью

Доказательство. Для любого конечного автомата

Тогда для М

Следовательно, по определению, M является автоматом с максимальной памятью

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

Теорема 6.1. Пусть -минимальный автомат с памятью и числом состояний n. Тогда

Доказательство. Если автомат М является минимальным и имеет память то должно существовать два пути, которые пересекаются не раньше, чем в своих конечных состояниях, как показано на рис. 6.3. Пусть является парой состояний, а является парой состояний этих путей. Предположим, что совпадают (являются одними и теми же состояниями) а также Тогда два пути, начинающихся в каждый из которых описывает последовательность вход - выход представляют собой замкнутые пути, которые являются - совпадающими, и следовательно, пути бесконечной длины, которые описывают одну и ту же

последовательность вход - выход, но не пересекаются, (рис. 6.4). По лемме 6.1 такие пути не могут существовать в автомате с конечной памятью. Теперь предположим, что совпадает с . Тогда начинающиеся в пути, каждый из которых описывает последовательность вход - выход представляют собой замкнутые пути, которые являются - совпадающими, и, следовательно, пути бесконечной длины, которые описывают одну и ту же последовательность вход - выход, но не пересекаются (рис. 6.5). Снова, по лемме 6.1, такие пути не могут существовать.

Рис. 6.4. Иллюстрация доказательства теоремы 6.1.

Рис. 6.5. Иллюстрация доказательства теоремы 6.1.

Таким образом, неупорядоченная пара и неупорядоченная пара не могут быть совпадающими неупорядоченными парами. Поэтому длина любого из путей, показанных на рис. 6.3, не может превышать число неупорядоченных пар состояний, которые могут быть выбраны в автомате с состояниями. Это число равно

Отсюда следует соотношение (6.18).