Українська   English
ДонНТУ   Портал магистров

Реферат по теме выпускной работы

Содержание

Введение

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

Модель конечного автомата широко используется для описания и анализ поведения разнообразных устройств дискретного действия или протекания процессов дискретной обработки информации, для моделирования и построения устройств и процессов. Эти устройства и процессы могут претерпевать изменения, обусловленные внешними воздействиями, которые в свою очередь могут приводить к изменению поведения автомата или оставлять поведение автомата неизменным. Отсюда возникает задача изучения автоматов, обладающих поведением, близким в том или ином смысле, а также структуры классов таких автоматов. Такого рода задачи рассматривались, в частности, в теории экспериментов с автоматами. В практическом плане интерес представляют такие преобразования, при которых поведение автомата сохраняется неизменным, т.е. автомат «проявляет устойчивость» по поведению к внешним воздействиям. В общем случае автомат-распознаватель не даёт точного указания, как поступать на очередном шаге, а разрешает продолжать вычислительный процесс несколькими способами. Поэтому не все конечные автоматы-распознаватели подходят для конструирования распознающих устройств, пригодных для практических приложений.

ПОСТАНОВКА ЗАДАЧИ

Автомат-распознаватель (акцептор) – это автомат, который позволяет определить принадлежность цепочки символов некоторому языку. Задача распознавателя заключается в том, чтобы на основании исходной цепочки дать ответ, принадлежит ли она заданному языку или нет.

Детерминированным конечным автоматом-распознавателем A называется пятерка объектов A=(S, X,б,s0,F), где S – непустое конечное множество состояний, X – конечный входной алфавит, s0 – начальное состояние, б: SxX->S – функция переходов, F – множество заключительных состояний. Множество всех входных слов р, которые переводят автомат из начального в одно из заключительных состояний, называется языком L(A), распознаваемым автоматом. Обозначим через Lk(A) подмножество множества L(A), состоящие из слов длины <= k. Будем говорить, что автомат А порождает язык Lк(А), а состояние s порождает множество Lk(s) слов длины k.

Два конечных автомата-распознавателя с одним и тем же входным алфавитом называются эквивалентными, если они распознают один и тот же язык, т.е. L(A)=L(B). По известной теореме Мура [1], два автомата-распознавателя эквивалентны тогда и только тогда, когда под действием одних и тех же входных слов они всегда попадают оба в заключительные либо оба в незаключительные состояния.

Далее под автоматом будем понимать приведённый детерминированный акцептор.

Задачей исследования является нахождение таких множеств перебросок дуг, при, которых получается акцептор A', неотличимый от A экспериментами заданной длины.

СТРУКТУРА ПРЕДСТАВЛЕНИЙ АВТОМАТОВ

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

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

Диаграмма состояний автомата Мура

Рисунок 1 – Переброска 4-х дуг в автомате
(анимация: 17 кадров, 3 цикла повторения, 82,1 килобайт)

Модель конечного автомата прошла хорошую проверку временем. Использование конечных автоматов позволяет разработчикам создавать хорошо организованные логические системы с гибкими возможностями, а также анализировать их поведение в различных условиях.

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

Детерминированный конечный автомат

Детерминированным конечным автоматом (ДКА) называется машина, распознающая цепочки символов, в которой для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего (рис. 2). Она имеет входную ленту, разбитую на клетки, головку на входной ленте (входную головку) и управляющее устройство с конечным числом состояний. Конечный автомат А можно представить в виде пятерки А=(S, X, б, s0, F), где

  1. S – конечное множество состояний устройства управления;
  2. X – алфавит входных символов;
  3. б – функция переходов, отображающая S x (I U {i}) в множество подмножеств множества S;
  4. s0 – начальное состояние автомата;
  5. F – множество заключительных (допускающих) состояний.

Рисунок 2 – Детерминированный конечный автомат

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

Конечный автомат можно описать с помощью диаграмм состояний и таблиц переходов.

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

Таблица переходов – табличное представление функции F. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу – один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ.

Недетерминированный конечный автомат

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

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

Для каждого состояния и каждого входного символа НКА имеет ноль или более вариантов выбора следующего шага. Он может также выбирать, сдвигать ему входную головку при изменении состояния или нет. Приведем определение недетерминированного конечного автомата.

Существует дополнительный результат или возможность сопоставить какому-либо взятому НКА эквивалентную «детерминированную» машину. Однако детерминированный конечный автомат, эквивалентный данному НКА с n состояниями, может иметь вплоть до 2 в n степени состояний. Поэтому переход от НКА к детерминированному автомату не всегда дает эффективный способ моделирования недетерминированного конечного автомата.

Выводы

В работе рассматривается ряд примеров, показывающих существование перебросок, сохраняющих Lк (А), и показывающих, каким образом можно определить указанные переброски.

Данные примеры приводят к следующей процедуре.

Строится последовательность таблиц Р0, Р1,…, Рк, и рассматриваются классы в таблице Рк. Если в Рк есть хотя бы один класс содержащий более одного состояния (s и t), то для состояний этого класса возможны искомые переброски. Эти переброски задаются с помощью Рк-1 таким образом, чтобы состояние-приемник по любому х для s и для t не выходило за пределы того класса, которому принадлежат концы дуг (s,x,y,u) и (t,x,y,v). Если же в Рк все классы одно-элементны, то переброски невозможны.

Данную процедуру в последующем предполагается представить в виде алгоритма.

Список источников

  1. Кудрявцев, В.Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М. : Наука, 1985. – 320 с.
  2. Капитонова, Ю.В. Основы дискретной математики / Ю.В. Капитонова, С.Л. Кривий, А.А. Летичевский, Г.М. Луцкий, Н.К. Печурин. – К. : Наукова думка, 2002. – 568 с.
  3. Брауэр, В. Введение в теорию конечных автоматов / [пер. с нем]. – М.: Радио и связь, 1987. – 392 с.
  4. Копытова, О. М. Устойчивость автоматов к неисправностям их функции переходов / О. М. Копытова // Тр. ин–та ИПММ АН Украины. - 2010. - № 21. - С. 57-66.
  5. Копытова, О.М. О структуре автоматов, сохраняющих поведение при перебросках дуг / О. М. Копытова // Труды VIII Международной конференции «Дискретные модели в теории управляющих систем». – М.: Макс–Пресс. – 2009. – С. 155-159.
  6. Богомолов, А.М. Эксперименты с автоматами / А.М. Богомолов, А.С. Барашко, И.С. Грунский. – Киев : Наукова думка, 1973. – 144 с.
  7. Евтушенко, Н.В. О проверяющих возможностях кратных экспериментов / Н.В. Евтушенко, А.Ф. Петренко // Автоматика и вычислительная техника. – 1989. – № 3. – С. 9-14.
  8. Кудрявцев, В. Б Анализ поведения автоматов / В. Б. Кудрявцев, Грунский И. С., Козловский В. А. // Дискретная математика. – 2009. – Т. 21. – №. 1. – С. 3-35.