К. Е. Карасёв Введение в теорию конечных автоматов
| Вид материала | Учебное пособие |
- Виртуальная лаборатория обучения генетическому программированию для генерации управляющих, 64.24kb.
- Рабочая программа Дисциплины «Теория автоматов» Для студентов специальности 23010065, 57.28kb.
- Прикладная теория цифровых автоматов, 27.51kb.
- Джон Р. Хикс. "Стоимость и капитал", 4314.44kb.
- Царев Федор Николаевич Разработка метода совместного применения генетического программирования, 417.18kb.
- А. В. Корицкий введение в теорию человеческого капитала учебное пособие, 1340.03kb.
- Полная программа на прологе 6 Схема ответов на вопросы по результатам практических, 73.73kb.
- Курсовая работа "Синтез дискретных устройств управления", 306.46kb.
- Лекция №11 «Антивирусные программы», 55.93kb.
- Г. В. Мелихов миф. Идентичность. Знание: введение в теорию социально-антропологических, 741.74kb.
4. Эксперименты над автоматами
В теории экспериментов над автоматами рассматривается следующая задача. Имеется неизвестный автомат («чёрный ящик») с известным входным и выходным алфавитом и некоторыми другими известными свойствами, позволяющие отнести его к некоторому известному классу автоматов. Требуется определить неизвестные свойства автомата (восстановить автомат, определить, каким именно автоматом из класса является данный) путём ввода в автомат входных последовательностей и наблюдения за выводом автомата. Алгоритм, который решает подобную задачу, называют экспериментом над автоматом. Эксперименты делятся на условные и безусловные, кратные и простые. Более формально, определения таковы:
Простым безусловным экспериментом называется слово во входном алфавите автомата. Испытание осуществляется путём ввода в автомат, находящийся в начальном состоянии, этого слова. Результатом эксперимента называется слово, выводимое автоматом при этом.
Кратным безусловным экспериментом называется конечное множество слов во входном алфавите автомата. Испытание осуществляется путём ввода в автомат, находящийся в начальном состоянии, каждого слова с переводом автомата в начальное состояние после ввода. (Считается, что автомат имеет «кнопку возврата в начальное состояние» или имеется достаточное количество экземпляров автомата для испытаний).
Простой условный эксперимент определяется как ориентированный граф без ориентированных циклов с одной вершиной-источником, вершины которого (кроме конечных) помечены словами из входного алфавита, а рёбра – словами из выходного алфавита. При применении эксперимента в автомат на первом шаге вводится слово, которым помечен источник; после каждого шага выбирается ребро, помеченное словом, полученным при этом шаге на выходе, и на следующем шаге в автомат вводится слово, которым помечена вершина, к которому это ребро ведёт. Конечные вершины помечаются как результаты эксперимента.
Кратный условный эксперимент определяется аналогично кратному безусловному, но вместо входных слов вершины помечаются простыми условными экспериментами, а рёбра – результатами соответствующих экспериментов в вершинах, из которых они исходят.
Эксперимент называется диагностическим для данного класса, если его результаты различны для любых двух автоматов этого класса. Эксперимент называется тестовым для данного автомата и данного класса автоматов, если по результату эксперимента можно определить, принадлежит автомат классу или нет.
Для оценки сложности экспериментов (относительно данного класса автоматов) применяются следующие величины:
Длина эксперимента – максимальная длина слова, которое может быть введено в автомат при применении эксперимента.
Объём эксперимента – максимальная суммарная длина слов, которые могут быть введены в автомат при применении эксперимента.
Кратность условного кратного эксперимента – максимальное число простых экспериментов, которые могут быть применены к автомату при применении данного эксперимента. Кратность безусловного кратного эксперимента – число входящих в него простых.
4.1. Переформулируйте теорему Мура о различении состояний, используя понятия теории экспериментов.
Очевидно, что простой эксперимент – частный случай кратного, и безусловный - частный случай условного; однако возможности простых и условных экспериментов больше, чем кратных и безусловных.
Теорема. Существует класс автоматов, для которого не существует диагностического простого эксперимента.
4.2. Постройте класс автоматов, для которого существует условный кратный диагностический эксперимент кратности 2, но не существует безусловного кратного диагностического эксперимента такой или меньшей кратности.
4.3. Пусть n – фиксированное натуральное число, {А} – класс автоматов Мура A=({1..n}, {0,1}n,{0,1}, ,,(0 … 0)), таких, что
- Входной алфавит {1..n} – множество натуральных чисел от 1 до n, множество состояний - множество строк из 0 и 1 длины n, выходной алфавит {0,1}, начальное состояние – строка (0 … 0) - общие для всех автоматов класса;
- функция переходов , также общая для всех автоматов, от строки q и входного символа k выдаёт строку q, в которой k-й символ заменён на 1;
- функция выходов (q,x)=f((q,x)), где f – некоторая функция алгебры логики от n переменных, своя для каждого автомата класса.
- Покажите, что уже при n≥2 простой диагностический эксперимент для этого класса невозможен. Покажите, что объём кратного диагностического эксперимента не ниже 2n, длина не ниже n.
- Покажите, что при n≥2d кратность эксперимента не ниже .
- Покажите, что существует эксперимент кратности, равной наибольшему коэффициенту в разложении многочлена (1+x)n, диагностический для данного класса. Каков его объём?
Упражнение. 3.4. Пусть n – фиксированное натуральное число, {Аi} – класс автоматов Мура Ai=({0,1},Zn,{0,1}, i,,0), i=1..n, таких, что:
i(0,k)=k+1 mod n,
i(1,k)=k+1 mod n, при k≠i
i(1,k)=i-1 mod n.
Постройте условный диагностический эксперимент для этого класса автоматов. Оцените его длину, объём, кратность.