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

[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]

условный эксперимент для распознавания автомата и его начального состояния.

4.4. Задайте автомат с шестью состояниями, в котором два состояния могут быть различены с помощью входной последова-

(fi/W Ш Ш)

V/7J (a/ff) (a/OJ

Ш (a/ffj (a/ff/ в

Рис. 3 4.1.

тельности длины 5, но не меньше. Проверьте, что приведенное выше требование удовлетворяется.

4.5. Задайте автомат с шестью состояниями и автомат с девятью состояниями, в которых два состояния (по одному в каждом автомате) могут быть различены с помощью входной последовательности длины 14, но не меньше. Убедитесь, что указанное требование удовлетворяется.

4.6. Рис. 3 4.2 показывает уровни от О до 3 частично снабженного обозначениями дерева преемников, где Gj, Gj и Gg суть Л-группы. Покажите, что три пути, проходящих через G,, и G3 уровня 3, не могут представлять минимальных диагностических последовательностей для М и А (Af).

4.7. Покажите, что минимальная диагностическая последовательность для автомата с q выходными символами и множеством

Таблица 3 4.1

Таблица 34.2



допустимых начальных состояний мощности т. не может быть короче, чем (log т)/(log q) символов.

4.8. Определите минимальную диагностическую последовательность для автомата, представленного таблицей 3 4.3 и множеством допустимых начальных состояний {1, 2, 3, 4, 5}.

Урове/fd О

Рис. 3 4.2.

4.9. Известно, что заданный автомат есть автомат, определенный либо таблицей 3 4.4, либо таблицей 3 4.5. Постройте кратчайший безусловный эксперимент для распознавания автомата и его начального состояния.

Таблица 3 4.3

*v+l

v \

4.10. Для автомата, определенного таблицей 3 4.6. (а) Постройте безусловные диагностические эксперименты, если множества допустимых начальных состояний таковы: (I) {4,5}, (II) {1,2,5}, (III) {1, 2, 3, 4, 5}. (б) Для случаев (II) и (III) опишите условный диагностический эксперимент, если истинное начальное состояние есть 1 (что сначала не известно).

4.11. Заданный автомат представлен графом переходов на рис. 3 4.3. (а) Постройте кратчайший безусловный эксперимент для распознавания начального состояния автомата, (б) Постройте кратчайший безусловный эксперимент для распознавания конечного состояния автомата.



*v+l

*v+l

S \

*v \

V \

Таблица 3 4.6

*v+l

S \

S \

4.12. Для автомата, заданного таблицей 3 4.6, и множества допустимых начальных состояний {1, 2, 3, 4, 5}. (а) Постройте кратчайший безусловный установочный эксперимент, (б) Постройте регулярный безусловный установочный эксперимент, (в) Опишите регулярный условный установочный эксперимент, если истинное начальное состояние есть 5 (что заранее не известно).

4.13. Для автомата, показанного на рис. 3 4.4. (а) Постройте регулярный безусловный установочный эксперимент, если истинное начальное состояние есть 7 (что сначала не известно).

4.14. Неизвестное начальное состояние автомата на рис. 3 4.4 есть 1. Опишите условный эксперимент, который будет переводить автомат в состояние 7.

4.15. Известно, что заданный автомат есть либо А, либо В из задачи 4.2. Постройте безусловный эксперимент для распознавания автомата и определите его конечное состояние.

4.16. Pi-разбиение минимального автомата Men состояниями имеет и классов, (а) Покажите, что любая диагностическая задача для двух состояний для М может быть решена с помощью простого безусловного эксперимента, длина которого не превышает п - и--1. (б) Покажите, что любая установочная задача для Af может быть решена с помощью простого безусловного эксперимента, длина которого не превышает (и-1) (и - и-\-\). (в) Покажите, что любая установочная задача для Af может быть решена с помощью простого условного эксперимента, длина которого не

Таблица 3 4.4

Таблица 3 4.5



[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.0008