Следствия, связанные с экспериментами по распознаванию состояний

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

Следствие 4.3. Пусть М есть автомат с л состояниями и известной таблицей переходов. Если начальное состояние автомата М вообще может быть определено путем проведения простого эксперимента, то оно может быть определено с помощью простого безусловного или простого условного эксперимента длины l, где

l ≤(n — 1)n^m. (4.17)

Начальное состояние М всегда может быть определено с помощью кратного безусловного эксперимента длины l и кратности с, где

и с помощью сложного условного эксперимента длины l и кратности с, где

Пусть М — автомат с входным алфавитом { ξ ₁ξ _2... ξ_p} и множеством состояний {σ₁, σ₂,..., σ_n}. Состояния σ_j и σ_i (i≠j) называются ξ _i-совместимыми, если реакции M| σ_j

и М| σ_i на ξ _i одинаковы и если σ_j и σ_i имеют одного и того же преемника по отношению к ξ _i. Пара ξ _i -совместимых состояний изображена на рис. 4.19.

Теорема 4.14. Пусть М есть автомат с n состояниями и входным алфавитом Х = {ξ ₁ξ _2... ξ_p} (а) Если М содержит пару ξ _i -совместимых состояний для каждого входного символа ξ _i из X, то диагностическая задача для n состояний для М никогда не можетбыть решена простым экспериментом, (б) Если М не содержит пары ξ _i -совместимых состояний ни для какого входного символа ξ _i из X, то диагностическая задача для n состояний для М всегда может быть решена простым экспериментом.

Доказательство, (а) Подача любого входного символа ξ _i на М заставляет пару состояний, скажем σ_j и σ_i, перейти

в одно и то же состояние с одинаковыми реакциями и, таким образом, обусловливает то, что эти состояния становятся не различимыми никакими последующими входными символами, (б) По теореме 4.12, М всегда может быть переведен в известное конечное состояние. Пусть установочной последовательностью, примененной для этой цели, является ξ _i1ξ _i2... ξ_ir; пусть соответствующая выходная последовательность будет ξ _h1ξ _h2... ξ_hr, а соответствующая последовательность состояний σ_j1, σ_j2,..., σ_jr. Предположим теперь, что σ_jk, ξ _ik и ξ _hk известны для некоторого k, 1 ≤ k ≤ r; так как по предположению ни одно состояние в M не имеет двух заходящих дуг, несущих одну и ту же пару вход-выход (ξ _ik / ξ _hk), то σ_j(k-1) может быть определено однозначно. Обозначим начальное состояние М через σ_j0, тогда σ_j0 может быть определено рекурсивно на основе знания конечного состояния М и входной и выходной последовательностей, включенных в установочный эксперимент.

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

Задачи

4.1. Опишите матричный способ решения диагностической задачи для двух состояний.

4.2. Таблицы 3 4.1 и 3 4.2 соответственно представляют автоматы А и В. Перечислите минимальные диагностические последовательности для всех пар состояний, в которых одно состояние выбирается из А, а второе состояние — из В.

4.3. Рис. 3 4.1 показывает граф переходов автоматов А а В. (а) Известно, что заданный автомат есть А в состоянии 3 или 4. Постройте кратчайший безусловный эксперимент для распознавания начального состояния, (б) Известно, что заданный автомат есть А в состоянии 1 или В в состоянии 1. Постройте кратчайший без-

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

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

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

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

4.6. Рис. 3 4.2 показывает уровни от 0 до 3 частично снабженного обозначениями дерева преемников, где G₁, G₂ и G₃ суть A-группы. Покажите, что три пути, проходящих через G₁, G₂ и G₃ уровня 3, не могут представлять минимальных диагностических последовательностей для М и А (М).

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

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

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

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

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. (а) Постройте кратчайший безусловный эксперимент для распознавания начального состояния автомата, (б) Постройте кратчайший безусловный эксперимент для распознавания конечного состояния автомата.

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. Р₁-разбиение минимального автомата M c n состояниями имеет и классов, (а) Покажите, что любая диагностическая задача для двух состояний для М может быть решена с помощью простого безусловного эксперимента, длина которого не превышает n — u+1. (б) Покажите, что любая установочная задача для М может быть решена с помощью простого безусловного эксперимента, длина которого не превышает (n—1) (n — u+1). (в) Покажите, что любая установочная задача для М может быть решена с помощью простого условного эксперимента, длина которого не

превышает

4.17. Может быть показано, что автомат с n состояниями и множеством допустимых начальных состояний мощности m всегда может быть переведен в известное состояние с помощью безусловного эксперимента длины l, где l ≤ (n— 1) (m— 1)+2^u+1 —2— um,

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

4.18. Таблица пар автомата M c n состояниями содержит только различные пары. Покажите, что начальное состояние М всегда может быть определено простым безусловным экспериментом, длина которого не превышает (n—1)².

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

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

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

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

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