Однонаправленная функция с секретом на базе КАМСИ

       

Конечные автоматы, сохраняющие информацию


Следующие разделы, включая раздел «Минимальная инверсная машина» (см.стр. 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 Количество информации о входах и выходах, необходимое для определения будущего поведения машины, называется диапазоном памяти машины.

Известно, что если для конкретной машины определено начальное состояние и известна входная последовательность, то это однозначно определяет выходную последовательность и конечное состояние. Однако, существует ситуация, при которой неизвестно начальное состояние или некоторое число предыдущих входных значений. В такой ситуации поведение машины не всегда может быть предсказанным. Мы  попробуем ответить на вопрос: а) для данной машины определить минимум информации о входах-выходах, необходимый для определения будущего поведения машины. б) При каких условиях  можно восстановить входную последовательность по выходной?



Содержание раздела