Конечные автоматы, сохраняющие информацию
Следующие разделы, включая раздел «Минимальная инверсная машина» (см.стр. 16) написан на основе материалов, опубликованных в книге Zvi Kohavi, Switching and Finite Automata Theory, Second Edition 1978, Memory, Definiteness, and Information Lossless ness of Finite Automata chat. 14, pp. 507.
Важная характеристика конечного автомата (КА) – наличие “памяти”, т.е. поведение Машины ([5]) определяется ее историей.
Поведение одних машин может зависеть от большего числа предшествующих событий, а других – от меньшего.
Определение. 1 Количество информации о входах и выходах, необходимое для определения будущего поведения машины, называется диапазоном памяти машины.
Известно, что если для конкретной машины определено начальное состояние и известна входная последовательность, то это однозначно определяет выходную последовательность и конечное состояние. Однако, существует ситуация, при которой неизвестно начальное состояние или некоторое число предыдущих входных значений. В такой ситуации поведение машины не всегда может быть предсказанным. Мы попробуем ответить на вопрос: а) для данной машины определить минимум информации о входах-выходах, необходимый для определения будущего поведения машины. б) При каких условиях можно восстановить входную последовательность по выходной?
