Московский государственный университет 1 страница

Стр 1 из 4Следующая ⇒

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

имени М.В. ЛОМОНОСОВА

Механико-математический факультет

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

Об эффективной реализации экспериментов

с конечными автоматами.

Автор:

Студент 4 курса, 412 группы ______________________Оспанов Б.П.

Научный руководитель:

к.ф.-м.н., доцент ______________________________Пантелеев П.А.

Рецензент:

к.ф.-м.н., с.н.с_________________________________Галатенко А.В

Москва 2015 г.

Содержание:

1. Введение ……………………………………………………………………………………………………………………..3

2. Основные определения………………………………………………………………………………………………. 4

2.1. Различимость, изоморфизм и минимизация ………………………………………………………….6

2.2 Проблемы тестирования ……………………………………………………………………………………………7

2.3 Установочная последовательность ………………………………………………………………………. 8

2.4 Синхронизирующие последовательности…………………………………………………………………9

3. Идентификация и верификация состояния………………………………………………………………….10

3.1. Простые безусловные диагностические эксперименты.………………………………………..11

3.2. Простые условные диагностические эксперименты ….…………………………………………..12

3.3. Построение простого условного диагностического эксперимента.……………………….13

3.4. Верификация состояния…………………………………………………………………………………………….15

4. Тест на соответствие……………………………………………………………………………………………………….16

4.1. Статусные сообщения и сброс…………………………………………………………………………………..18

4.2. Разделяющие последовательности……………………………………………………………………….…19

5. Вывод……………………………………………………………………………………………………………………………...22

6. Список литературы ………………………………………………………………………………………………………..23

7.Приложение……………………………………………………………………………………………………………………..24

1. Введение.

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

Есть 2 вида конечных автоматов: автомат Мили и автомат Мура. Здесь мы рассматриваем модель Мили, т.к. она более удобна для следующих высказываний и является более распространенной, чем модель Мура.

Рассматривается 2 вида проблем тестирования. В первом случае мы имеем диаграмму переходов конечного автомата, но не знаем в каком состоянии он находится. На вход автомату подается последовательность, анализируя вход-выходные данные, получаем информацию о текущем состоянии. В проблеме идентификации состояния нас волнует определение начального состояния автомата. Тестовая последовательность, которая решает эту проблему, называется простым диагностическим экспериментом.

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

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

2. Основные определения.

Cначала, мы представим главные определения: неразличимые состояния и автоматы, изоморфизм, минимизация.

Опр.1 Конечный автомат M это пятерка:

M=(I,O,S, ),

Где I,O и S конечные и непустые множества входного алфавита, выходного алфавита и состояний, соответственно. - функция переходов,

- функция выходов.

Если автомат находится в состоянии s S и получает на вход сигнал a I, то автомат переходит в состояние (s,a) и подает на выход сигнал (s,a).

Конечный автомат может быть представлен в виде диаграммы переходов: направленный граф, вершины которого отвечают за состояния, а грани за переходы между состояниями, на них отмечены входные и выходные сигналы. Для конечного автомата на рис.1, предположим, что он находится в состоянии . Под действием сигнала b автомат переходит в состояние и выдает сигнал 1. Точно также конечный автомат может быть представлен таблицей состояний: в первом столбце находятся все состояния, в каждом следующем столбце указано, куда перейдет автомат и что подаст на выход и так для каждого входного сигнала. Как на таблице 1, которая определяет диаграмму переходов на рис.1.

	a	b
	,0	,1
	,1	,1
	,0	,1

таблица 1.

Определим количество элементов во множествах: n=|S|, p=|I|, q=|O|. Определим функции переходов и выходов для последовательностей. Для начального состояния входная последовательность x= проводит автомат в состояния:

, i=1,…..,k и в финальное . Получаем выходную последовательность , где , i=1,…,k. Для автомата на рис.1 входная последовательность abb переводит его в состояния и выводит 011. Также функции переходов и выходов можно расширить на множества: и .

Входная последовательность x индуцирует разбиение множества состояний S, где два состояния находятся в одном блоке тогда и только тогда, когда они не различимы последовательностью x, т.е. Такое разбиение называется неопределенность начального состояния последовательности x. Заметим, что после подачи входной последовательности x в M и обзора выходной последовательности, информация о начальном состоянии, которую мы получим это блок , к которому принадлежит выходная последовательность. Информация о текущем состоянии автомата M, в котором он находится после подачи входной последовательности x, хранится в семействе множеств: , называющееся неопределенностью текущего состояния последовательности x. Заметим, что не обязательно является разбиением, т.е. множества в могут пересекаться. Выходной сигнал произведенный автоматом M, в ответ на входной сигнал, указывает на то, какому множеству семейства принадлежит текущее состояние. Например, для автомата на рис.1 подаем на вход b. Если на выход получим 1, значит начальным состоянием могло быть или , а текущим состоянием или , если получим 0, то значит, начальным состоянием было , а текущее . Таким образом, для сигнала b неопределенность начального состояния: и неопределенность текущего состояния:

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

Таким образом, корень обозначен всем набором состояний, правый потомок обозначен: с соответствующими выходами и и т.д.

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

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

2.1 Различимость, изоморфизм и минимизация.

Два состояния и неразличимы тогда и только тогда, когда для каждой входной последовательности автомат будет выдавать одинаковый сигнал, независимо от того, какое состояние является начальным или , т.е. для любой входной последовательности x справедливо, что , иначе два состояния разичимы, если существует входная последовательность x, для которой . Такая последовательность называется разделяющая последовательностью. Для двух состояний в разных автоматах с одинаковыми входными и выходными алфавитами определение такое же. Два автомата M и M’ эквивалентны тогда и только тогда, когда для каждого состояния из M существует неразличимое состояние из M’. Пусть M=(I,O,S, ) и M’=(I,O,S’, ) два автомата с общим входным и выходным алфавитами. Гомеоморфизм из M в M’ это отображение такое, что для каждого состояния и для каждого входного сигнала a справедливо, что и . Если -биекция, то такое отношение называется изоморфизмом, в этом случае M и M’ должны иметь одинаковое количество состояний идентичных друг другу с учетом возможного переименования. Два автомата называются изоморфными, если существует изоморфизм из одного в другой. Очевидно, два изоморфных конечных автомата эквивалентны друг другу, обратное строго говоря неверно.

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

Если дан автомат M, то мы можем найти минимизированный, эквивалентный ему автомат следующим образом. Эквивалентные друг другу состояния образуют блок, мы можем разбить множество состояний на такие блоки. Сначала проводим разбиение по выходным сигналам, т.е. два состояния принадлежат одному блоку тогда и только тогда, когда на каждый входной сигнал, выходные сигналы совпадают. Когда все состояния распределены по блокам, делим блоки на подблоки по переходам, т.е. два состояния входят в один подблок, если на каждый входной сигнал они переходят в одно и то же состояние. Повторяем данный процесс пока все состояния не будут полностью распределены, т.е. каждый блок содержит в себе эквивалентные состояния и состояния в разных блоках не эквивалентны друг другу. Вдобавок, для состояний в разных блоках последовательность входных сигналов, участвующая в их разделении есть разделяющая последовательность. За один круг деления мы проверяем все p входных сигналов для каждого из n состояний, а всего таких кругов не больше, чем n-1, для n состояний. Сложность такого разбиения равна O(p ). Модификация алгоритма дает сложность ).

После разбиения состояний на блоки, получим r блоков: , можем построить минимизированный автомат M’. Мы сопоставляем каждому блоку состояние: и множество состояний S’ автомата M’: . Переопределим функции выходов и переходов. Под действием входного сигнала a все состояния блока переходят в блок и подают на выход сигнал o. Тогда и . В M’ нет неразличимых состояний и он эквивалентен автомату M. Заметим, что M’ есть гомоморфное отображение M (и всех автоматов в классе эквивалентности M). Гомоморфизм переводит все состояния из в соответствующее состояние .

2.2 Проблемы тестирования.

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

Мы обсудим 4 фундаментальных проблем тестирования. В первых трех имеется полное определение автомата M=(I,O,S, ), но мы не знаем его начального состояния.

Проблема I (Установочная/Синхронизирующая Последовательность): Определить финальное состояние автомата после теста.

Проблема II (Идентификация Состояния): Найти неизвестно начальное состояние.

Проблема III (Верификация Состояния): Автомат должен быть в определенном начальном состоянии, проверим, что это так.

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

Проблема IV (Тест На Соответствие): Дано полное определение автомата A=(I,O,S, ) – автомат-эталон. Нужно определить эквивалентны ли M и A.

Для каждой из этих проблем главные вопросы это:

Существование: существует ли тестовая последовательность, решающая эту проблему?

Длина: При существовании такой последовательности, какова её длина?

Сложность: Как трудно определить существует ли такая последовательность, как трудно ее найти и как трудно построить кратчайшую?

Проблема I решается установочными и синхронизирующими последовательностями, и описываются они в части 2.3 и 2.4. Проблемы II и III решаются простыми диагностическими экспериментами и уникальными вход-выходными последовательностями,которые рассматриваются в части 3. Методы решения Проблемы IV представлены в части 4.

2.3 Установочная последовательность.

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

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

Заметим, что последовательность x является установочной, тогда и только тогда, когда все блоки неопределенности текущего состояния состоят только из одного элемента. В начале автомат может быть в любом состоянии, а значит состоит из одного множества-всех состояний S. Берем два любых состояния из одного блока, находим последовательность, которая разделяет их (она существует, потому что автомат минимизирован), применяем её к автомату и разбиваем блок текущего состояния минимум на два подблока, каждый из которых соответствует своему выходному сигналу. Повторяем данный процесс до тех пор, пока все блоки в не будут состоять только из одного элемента. В итоге получаем входную последовательность x, которая является установочной. Например, для автомата на рис.1 входной сигнал b отделяет от и , переводя автомат в состояние , и , соответственно, наблюдая выход 0. Иначе получим 1, значит автомат находится в состоянии или Затем на вход подается сигнал a, разделяющий и выходами 0 и 1. Таким образом, ba - это установочная последовательность, которая переводит автомат из состояний , и в состояния , и . Финальное состояние может быть определено наблюдая выходные последовательности 11, 10 и 00, соответственно. Заметим, что если на выход подастся b и получим 0, мы поймем, что автомат находится в состоянии и уже не нужно будет подавать a, если же получим 1 в начале, то это сделать придется. Таким образом, условный тест может быть короче, чем безусловный.

Т.к. мы можем построить разделяющую последовательность длины не больше, чем n-1 для любых двух состояний и применяем её не больше, чем n-1 раз, для того чтобы каждый блок состоял из одного элемента. Объединим все разделяющие последовательности и получим установочную последовательность длины не больше, чем .

Конечно, заданный автомат может иметь более короткую установочную последовательность, чем та, которую получим через описанный выше алгоритм. Легко найти кратчайшую последовательность, используя дерево решений. Нам нужно только найти вершину наименьшей длины, которая обозначена неопределенностью текущего состояния с блоками в каждом из которых, по одному элементу. Например, кратчайшая установочная последовательность для автомата на рис.1 это ba, это можно понять взглянув на его дерево решений на рис.2. Однако построение дерева решений занимает экспоненциальное время. Таким образом, поиск кратчайшей установочной последовательности это проблема сложности-NP.

2.4 Синхронизирующие последовательности.

Синхронизирующая последовательность приводит автомат в одно и то же финальное состояние, вне зависимости от начального состояния и выхода. Входная последовательность x является синхронизирующей тогда и только тогда, когда

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

Конечный автомат может иметь, а может и не иметь синхронизирующую последовательность, даже если он минимизирован. За полиномиальное время можно узнать, существует ли у автомата синхронизирующая последовательность, и построить её.

Дана диаграмма переходов G автомата M, мы строим дополнительный граф G G с вершинами, по одной для каждой пары (включая пары одинаковых вершин). Существует ребро, исходящее из вершины в вершину , обозначенное входным сигналом a тогда и только тогда, когда в диаграмме G существуют переходы из в и из в , обозначенные входным сигналом a. Для автомата на рис.3 дополнительный граф изображен на рис 4. Допустим сигнал a переводит состояния и в состояние , то есть в графе G G существует переход из в . Легко проверить, что существует входная последовательность, переводящая автомат из состояний и , , в состояние тогда и только тогда, когда в графе G G существует путь из вершины в . То есть, если у автомата существует синхронизирующая последовательность, значит существует путь для всех вершин , в некоторую вершину . Как мы покажем позже, обратное тоже верно. И существование такого пути необходимо и достаточно для существования синхронизирующей последовательности. На рис.4, в вершину можно попасть из вершин , значит автомат на рис.3 имеет синхронизирующую последовательность. Это условие достижимости может быть проверено поиском в ширину за время O(p ), следовательно существование синхронизирующей последовательности может быть проверено за время O(p ).