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