Условия существования конечной памяти.
Допустим, первоначальная неопределенность относительно состояния машины М (S1
S2…Sn) ([6]).
Определение. 3 М есть конечная память µ-порядка если подача любой входной последовательности длиной µ переводит машину в распознаваемое состояние, и если существует входная последовательность длиной µ-1, которая, вместе с соответствующей выходной последовательностью не содержит информацию, необходимую для точного определения конечного состояния.
Утверждение 1. Последовательная машина М имеет конечную память, если и только если ее тестирующий граф не имеет циклов.
Доказательство. Допустим, G имеет цикл. Тогда, при повторении подачи символов, соответствующих метке перехода цикла, мы получим входную последовательность произвольной длины, которая не позволит определить конечное состояние, то есть машина не обладает конечной памятью. Чтобы доказать достаточность, примем, что G не имеет циклов. Если М не обладает конечной памятью, то существует произвольно длинный путь в G, соответствующий некоторой входной последовательностью Х и некоторая пара состояний SiSj
такая, что Si и Sj
не могут быть отличены при Х. Но так как число вершин в G не может превосходить (n-1)n/2
(соответствующее числу отличных пар состояний) произвольно длинный путь в G возможен только если он содержит цикл. Утверждение 1 доказано.
Пример. Из тестирующего графа M1
(Рис. 1) видно, что G1 имеет два цикла. Следовательно, M1 не обладает конечной памятью.
Следствие.
Допустим, G свободный от циклов тестирующий граф для машины М. Если длина наибольшего пути равна l, то µ=
l+1.
Доказательство. Так как G свободен от циклов, то М обладает конечной памятью. Допустим, что µ> l+1; тогда существует минимум одна неопределенная пара SiSj,
которая будет переведена при подаче входной последовательности длиной l+1 в другую пару SpSq. Следовательно, существует путь вежду вершинами SiSj
и SpSq
длиной l+1. Но это противоречит нашему допущению и, следовательно, µ не может превышать l+1.
На основании приведенного выше вытекает, что µ?(n-1)n/2.
