Главная  Кибернетика 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [ 58 ] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]

превышает

„ 2+[(/г-« + 2) (,г-« + 1)/2].

4.17. Может быть показано, что автомат с п состояниями и множеством допустимых начальных состояний мощности т всегда может быть переведен в известное состояние с помощью безусловного эксперимента длины /, где / < (/г- 1) (/п - 1)--2""" -2 - ит.



Ш Рис. 3 4.3.

Рис. 34.4.

где и есть любое положительное целое число). (а) Найдите и (как функцию /п), которое минимизирует верхнюю границу /. (б) Оцените наименьшую верхнюю границу / для /п = 2, 4, 8, 1024.

4.18. Таблица пар автомата М. z п состояниями содержит только различные пары. Покажите, что начальное состояние М всегда может быть определено простым безусловным экспериментом, длина которого не превышает {п-1).

4.19. Не строя каких-либо диагностических экспериментов, покажите, что диагностическая задача для восьми состояний для автомата, представленного в таблице 34.3, может быть решена с помощью простого эксперимента и что диагностическая задача для пяти состояний для автомата, представленного таблицей 34.6, не может быть решена с помощью простого эксперимента.

4.20. (а) Постройте минимальный (3, 2, 2)-автомат с входным алфавитом {а, Р}, в котором имеется пара а-совместимых состоя-

) Автором этого результата является Гинзбург (S. О i п s -burg, On the Length of the Smallest Uniform Experiment which Distinguishes the Terminal States of a Machine, J. Assoc. Comput. Mach., vol. 5, pp. 266-280, 1958. Русский перевод: С. Гинзбург, О длине кратчайшего однородного эксперимента, устанавливающего конечные состояния машины, «Кибернетический сборник», № 3, ИЛ, 1961).



НИИ и в котором диагностическая задача для трех состояний может быть решена с помощью простого эксперимента, (б) Постройте минимальный (3, 2, 2)-автомат с входным алфавитом {а, р}, в котором имеется пара а-совместимых состояний, но нет ни одной пары р-совместимых состояний и в котором диагностическая задача для трех состояний не может быть решена простым экспериментом.

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

4.22. Постройте автомат с пятью состояниями, для которого диагностическая и установочная задачи для пяти состояний не могут быть решены никаким безусловным экспериментом длины, меньшей чем 10. Постройте диагностическое дерево и установочное дерево для этого автомата.



ГЛАВА 5

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

5.1. Введение

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

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

) Материал этой главы частично базируется на работе Мура (Е. г. Moore, Oedanken-Experlments on Sequential Machines, ♦Automata Studies*, pp. 129-153, Princeton University Press, Princeton, N. Y., 1956. Русский перевод: Э. Ф. Мур, Умозрительные эксперименты с последовательностными машинами. В сборнике «Автоматы» под редакцией К. Э. Шеннона и Дж. Маккарти, ИЛ, М., 1956).



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [ 58 ] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]

0.0009