ГЛАВА 4. ЭКСПЕРИМЕНТЫ ПО РАСПОЗНАВАНИЮ СОСТОЯНИЙ

4.1. Введение

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

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