bigpo.ru
добавить свой файл
1
АНАЛИЗ РЕШЕНИЯ УСТАНОВОЧНОЙ ЗАДАЧИ ДЛЯ АВТОМАТОВ

С. В. Куценко

Саратовский государственный университет,

Саратов, Россия


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

Задачи распознавания состояния конечного детерминированного автомата можно условно разделить на два основных вида:

  1. Диагностическая задача

  2. Установочная задача

Э. Мур в 1956 г. в работе [1] показал, что существует решение установочной задачи с помощью простого безусловного эксперимента, предложил метод решения установочной задачи и нашел оценку длины эксперимента. Поиск решения предлагается осуществлять с помощью установочного дерева.

А. Гилл в 1962 г. в работе [2] свел задачу распознавания автомата в конечном семействе автоматов к установочной задаче. На практике, часто возникает задача распознавания автомата, о котором известно, что он принадлежит к определенному конечному семейству автоматов, т.е. необходимо определить, каким из автоматов семейства , где - конечный детерминированный автомат, является автомат . Решение этой задачи может быть найдено путем приложения такого слова , которое удовлетворяет предикату .

А. Гиллом из оценки Мура для установочной задачи получена оценка длины простого безусловного эксперимента для решения задачи распознавания автомата в семействе автоматов: , где n – максимальное число состояний автоматов семейства и N – число автоматов в семействе.

Метод решения задачи распознавания автомата в заданном семействе автоматов, предложенный А. Гиллом, имеет один недостаток: для решения задачи необходимо построение установочного дерева, которое напрямую зависит от конкретных функций переходов и выходов автоматов заданного семейства, таким образом построенный тест является неприменимым для тестирования других семейств автоматов.

В 1981-1982 годах в работах [3,4] Твердохлебовым В.А. был предложен метод универсального решения задачи распознавания автомата в заданном семействе автоматов. Некоторые вопросы построения УТ для всех семейств автоматов, входящих в достаточно широкий специальный класс автоматов, рассмотрены в работе Пономаренко[5]. В его работе предлагается новый подход к построению универсальных тестов, основанный на использовании специфических свойств диагностируемых систем, исследуется возможность сокращения универсального теста в некоторых специфических классах автоматов.

В данной статье приведены результаты исследований установочных решений для всевозможных пар автоматов из класса (2,2,2) – автоматов и определение некоторых свойств.


Пусть M – множество пар, исключительных классов автоматов из множества (2,2,2)-автоматов.


Анализ структуры покрытия множества М, подмножествами соответствующим конкретным решениям установочной задачи.

Класс (2,2,2) автоматов состоит из 256 автоматов. Не уменьшая общности решения задачи универсального тестирования над этим классом, проведем его редукцию воспользовавшись следующим алгоритмом:

  1. Исходное множество автоматов необходимо разбить на классы эквивалентности по критерию изоморфизма функции переходов.

  2. Оставив только по одному представителю от каждого класса эквивалентности мы сможем снизить количество исследуемых автоматов. Очевидно, что удаление изоморфных автоматов ни как не повлияет на окончательное решение задачи поиска универсального теста, так как с точки зрения тестирования автоматы с изоморфными функциями переходов и одинаковыми функциями выходов являются эквивалентными.

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

Автомат поглощается автоматом

Автомат поглощается автоматом

После применения данного алгоритма мощность исследуемого множества автоматов упала до 96 автоматов. Таким образом, любой исключительный класс автоматов из данного множества, состоит из не более чем 96 автоматов. Из оценки Гилла следует, что для любого исключительного класса автоматов во множестве (2,2,2) автоматов, существует решение установочной задачи – , с оценкой длины . Оценка Гилла, примененная к УТ, может быть понижена. Для разработки УТ и понижения оценки длины УТ, Твердохлебовым было предложено представление исключительного класса автоматов, множеством пар и использование решений установочной задачи для каждой пары с последующим построением универсального теста на основе конкатенации частных решений.[6]

Новым является исследование возможности сокращения оценки длины универсального теста, в результате применения трех процедур:

  1. Использование для пар наименьших по длине решений.

  2. Исследование общих решений

  3. Частичное покрытие тестов

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

Проведенные вычислительные эксперименты показали, что конкретные подмножества множества M, имеют решение установочной задачи со следующими оценками длины, представленными в таблице.


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

Установочный тест

Число пар автоматов, распознаваемых данным тестом и нераспознаваемых любой его частью

Число пар автоматов, распознаваемых данным тестом

Установочный тест

Число пар автоматов, распознаваемых данным тестом и нераспознаваемых любой его частью

Число пар автоматов, распознаваемых данным тестом

0

64

64

1

64

64

00

1008

1088

10

1312

1440

000

256

1600

100

536

2864

001

464

2784

1001

4

3608

0010

20

3568

10010

4

3888

01

1312

1440

101

496

2816

010

496

2816

1010

24

3344

0100

12

3600

1011

12

3600

01001

4

3904

10110

4

3904

0101

24

3344

11

1008

1088

011

536

2864

110

464

2784

0110

4

3608

1101

20

3568

01101

4

3888

111

256

1600



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

  1. Решением установочной задачи для наибольшего числа (3904) пар автоматов являются следующие тесты: 10110, 01001.

  2. Решением установочной задачи для наименьшего числа (4) пар автоматов, распознаваемых тестом и не распознаваемых никакой его частью, являются следующие тесты: 01001, 0110, 01101, 1001, 10010, 10110.

  3. Максимальная разница между числом пар автоматов, распознаваемых тестом и не распознаваемых никакой его частью равна 3900.

  4. Число пар автоматов, распознаваемых конкретным тестом, не равно сумме числа пар автоматов, распознаваемых всевозможными его частями.

Для подтверждения третьего пункта, приведем следующий пример:

Автомат А1:

S1 S1/1 S1/0

S2 S1/0 S1/0

Автомат А2:

S1 S1/0 S1/1

S2 S1/1 S1/1

Данная пара автоматов, образует исключительный класс и распознается следующими решениями: 1, 00.


СПИСОК ЛИТЕРАТУРЫ:

  1. Мур Э. Ф. Умозрительные эксперименты с последовательностными машинами /Э. Ф. Мур // Автоматы: Сб. под ред. К. Э. Шеннона и Дж. Маккарти. – пер. с англ. – М.:ИЛ. – 1956. С. 179 – 212.

  2. Гилл. А. Введение в теорию конечных автоматов /А. Гилл. – Пер. с англ. – М.: Изд-во «Наука», 1966. – 272 с.

  3. Твердохлебов В. А. Универсальное решение задачи распознавания автоматов /В. А. Твердохлебов //Методы и системы технической диагностики. – Саратов: Изд-во Сарат. ун-та, 1981. - Вып. 2.

  4. Твердохлебов В. А. Универсальные генераторы тестов и системы диагностирования /В. А. Твердохлебов /Техническая диагностика. – Ростов-на/Д.: Изд-во РИСИ, 1982.

  5. Пономаренко А. В. Универсальное диагностирование в частных классах конечных автоматов /А В Пономаренко // Мехатроника, Автоматизация, Управление- Москва, 2006. - №12. - с. 17 – 24.

  6. Твердохлебов В. А. Методы построения универсальных тестов для конечных автоматов /В. А. Твердохлебов // «Автоматика и Телемеханика». – М., 2005. - №1. с. - 154 – 163.