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

5.1. Введение

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

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

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