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

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

Содержание

Введение

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

1. Актуальность темы

Конечные автоматы являются уникальной моделью представления потока выполнения каких-либо команд. Такая модель успешно используется как в технике (проектирование вычислительных машин, систем управления и связи), так и в других областях деятельности человека – теории и практике административного управления, лингвистике (анализ синтаксиса формального языка, расшифровка древних рукописей) и т. д. Универсальность теории автоматов позволяет рассматривать с единой точки зрения различные объекты, учитывать связи и аналогии между ними, переносить результаты из одной области в другую [1].

Конечные автоматы имеют широкий диапазон использования. Теория автоматов применяется в компьютерных играх при написании искусственного интеллекта для персонажа [2]. Автоматы используют в системах подготовки и редакции текстов [3], в разработке управляющих программных систем [4], при программировании мобильных устройств [5], для тестирования программных решений [6].

Широко используются конечные автоматы в криптографии: в построении криптосистем и в качестве компонент криптоалгоритмов [7]. В частности, применяются КА в поточных и автоматных шифросистемах, в симметричных шифрах и криптосистемах с открытым ключом [8].

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

2. Цель и задачи исследования, планируемые результаты

Объектом исследования является поведение приведенного автомата-распознавателя при переброске дуг.

Предметом исследования выступает нахождение условий, при которых автомат после переброски k дуг принимает тот же язык, что и исходный – автомат-эталон.

Цель: разработка и исследование метода анализа автоматов-распознавателей, порождаемых локальными преобразованиями эталона.

Основные задачи исследования:

  1. Провести анализ поведения автомата-распознавателя при переброске k дуг, k ≥ 1.
  2. Систематизировать полученные в ходе решения практических примеров результаты.
  3. Найти закономерности, при которых возможна или не возможна переброска k дуг с сохранением поведения автомата.
  4. Сделать выводы и описать класс автоматов, допускающих переброску дуг с сохранением эквивалентности.

3. Обзор исследований и разработок

3.1 Обзор международных источников

Анализ и исследование структуры автоматов со схожим поведением являются весьма распространенными явлениями, и проводятся давно. Эти задачи относятся к экспериментальной теории с автоматами, которая тщательно изложена в книге А. Гилла Введение в теорию конечных автоматов [9]. Гилл предложил рассматривать автомат, как чёрный ящик, а задачу распознавания автомата, как задачу определения для черного ящика вход-выходных характеристик при помощи измерений на его внешних выходах.

Основные положения теории экспериментов над автоматами были описаны Эдвардом Муром [10]. Он внес большой вклад в развитие методов исследования КА, впервые предложив алгоритм распознавания эквивалентных автоматов.

В частности, теорию экспериментов освещают работы Р. Брауэра [11], П. Штарке [12], Ф. Хенни [13] и многих других авторов.

3.2 Обзор национальных источников

На национальном уровне исследование автоматов и их поведения с помощью экспериментов было рассмотрено М.П. Василевским [14], Н.В. Евтушенко, А.Ф. Петренко [15-18], В.Б. Кудрявцевым, И.С. Грунским, В.А. Козловским [19-28], В.А. Буевичем, Н.Г. Каландарашвили, А.А. Талем [29, 30].

Вышеперечисленные работы охватывают три основных этапа исследования поведения КА: сложностной, комбинаторный и характеризационный.

Комбинаторный тип основывается на выборе средств анализа и методов проведения экспериментальных исследований автоматов.

Сложностной включает построение алгоритмов необходимой сложности для анализа поведения автоматов, а также расчёт сложности экспериментов над автоматами. Отсюда возникла потребность исследования этапов экспериментов. М.П. Василевский [14] реализовал данную задачу путем внедрения некоторых последовательностей во входные слова с целью выявления внутренних состояний автомата, исследуя реакции исходного автомата на данные последовательности. И.С. Грунский назвал эти последовательности и реакции на них идентификаторами состояний, занялся их систематическим изучением и обнаружил существование идентификаторов других ненаблюдаемых компонент поведения (например, входных последовательностей [22].

На характеризационном этапе рассматриваются частные случаи контрольных и распознающих экспериментов при условии, что такие эксперименты заведомо существуют. Этот этап ознаменовался выведением В.А. Козловским первых характеризационных теорем [26].

3.3 Обзор локальных источников

Исследование поведения автоматов при переброске на локальном уровне было проведено О.М. Копытовой [31-33], а также О.С. Швец [34] и Е.И. Бурлаевой [35] в рамках выполнения магистерских работ.

Для приведенных автоматов Мили были получены следующие результаты:

4. Автоматная модель

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

По видам устройства управления автоматы делятся на:

Нами будут рассматриваться детерминированные автоматы. Дадим определение такого КА.

Детерминированным конечным автоматом-распознавателем называется устройство или алгоритм A = ( S, X, δ, s0, F ) где S – непустое конечное множество состояний, X – конечный входной алфавит, s0 ∈ S – начальное состояние, δ – функция переходов, F ⊆ S – множество заключительных состояний.

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

Два состояния a и b одного и того же автомата A или двух разных автоматов, соответственно A и B, называются эквивалентными, если для всякого входного слова р ∈ X* одновременно выполняется либо

либо

С каждым состоянием а ассоциируется язык L(а), состоящий из множества слов в алфавите X, которые переводят состояние а в одно из заключительных состояний:

Из определения эквивалентности состояний a и b следует: L(a) = L(b). Автомат называется приведенным, если все его состояния попарно неэквивалентны, то есть для ∀ a, b: L(a) ≠ L(b) [3].

Проводить анализ переброски дуг в автомате будем поэтапно:

5. Теоретические результаты

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

Рассмотрим некоторое преобразование. Выберем в исходном автомате А дугу (а, х, b). Заменим на дугу (а, х, g) так, чтобы g ≠ b и g ∈ SA. То есть получили новый автомат из автомата-эталона путем переброски дуги (а, х, b) в состояние g.

Теорема 1. Переброска одной дуги в приведенном автомате-распознавателе приводит к неизоморфному автомату.

Доказательство. Пусть автомат В получили вследствие переброски дуги (а, х, b) в состояние g. Покажем, что А не эквивалентен В. Чтобы различать состояния автомата-эталона и состояния автомата, полученного переброской дуги, будем возле состояний последнего ставить штрих: s ∈ SA и s' ∈ SB соответственно. Будем называть эти состояния двойственными.

Построим автомат C = ( SC, X, δC, s0s0', F ∪ F' ), который равен сумме автоматов А и В. Если А эквивалентен В, то в автомате С есть п пар эквивалентных состояний. Каждая пара таких состояний включает одно состояние из A и одно состояние из В. Покажем, что эти автоматы не эквиваленты с помощью Рk-таблиц, составленных для автомата С. При построении проверяем каждый класс эквивалентности: совпадает ли количество состояний автомата В и эталона.

Так как таблица переходов A идентична таблице переходов В, то в таблице P1 число состояний эталона в каждом классе равно числу состояний автомата В соответственно. Это связано с тем, что каждый класс содержит двойственные состояния s и s'. Любая пара (s, s'), где s ≠ a, по любому х переходит в другую пару двойственных состояний. Для пары (а, а') в автомате С данный переход не выполняется, потому что δC (а, х') = b и δC (а', х') = g'. То есть, пока состояние а k-эквивалентно состоянию а', то любая пара s, s', при условии, что s ≠ a, (k + 1)-эквивалентна.

В то же время пара a, a' k-эквивалентна, пока b (k – 1)-эквивалентно g'. Если b, g' (k – 1)-эквивалентны, то пары (а, а'), (b, b'), (g, g') k-эквивалентны. Это значит, что состояния b, b', g, g' принадлежат одному классу эквивалентности Рk–1-таблицы.

Исходя из того, что автомат А является приведенным и имеет п состояний, то состояния b и g для некоторого i ≤ п – 1 будут (i – 1)-эквивалентны, но вместе с тем i-различимы. То есть, b и g будут i-различимы, а состояния а и а' будут в некотором классе К таблицы Рi. В таблице Рi+1 класс К распадется таким образом, что состояния а и а' в результате войдут в разные классы. Оставшиеся состояния класса К со своими двойственными состояниями войдут в другие классы Рi+1-таблицы. Следовательно, в классе таблицы Рi+1, содержащем а, будет на одно состояние автомата А больше, чем состояний В. В таком случае итоговая Рn–1-таблица будет включать класс с этими же свойствами. Таким образом, автоматы А и В не являются эквивалентными.

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

Теорема 2. Для любого k ≥ 3 существует автомат-распознаватель, допускающий переброску k-дуг.

Доказательство. Построим приведенный акцептор, содержащий n > 3 состояний, с одним входным и одним заключительным состоянием. По единице каждое состояние переходит само в себя. По нулю – переходит в состояние i + 1. Первое состояние – входное, n-ое состояние – заключительное (по нулю тоже переходит само в себя).

На рисунке 1 представлен автомат-распознаватель.

Общий вид акцептора

Рисунок 1 – Общий вид акцептора

Покажем, что автомат приведенный. Возьмем два состояния i и j, где n – 1 > i ≥ 1, n ≥ j ≥ 1, j > i. Из построения видно, что δ (j, 0n-j) ∈ F, а δ (i, 0n-i) ∉ F. А состояния n и n – 1 различимы единицей: δ (n, 1) ∈ F, а δ (n – 1, 1) ∉ F.

Переброска k-дуг осуществляется следующим образом:

Для наглядности приведем результат переброски k-дуг в акцепторе (рисунок 2).

Автомат-распознаватель после переброски

Рисунок 2 – Автомат-распознаватель после переброски

Из рисунка 2 видно, что в результате получили автомат, эквивалентный исходному.

На рисунке 3 проиллюстрирован пример переброски 3-х дуг с сохранением эквивалентности автомата.

Пример переброски 3-х дуг в акцепторе

Рисунок 3 – Пример переброски 3-х дуг в акцепторе
(анимация: 18 кадров, 3 цикла повторения, 134 килобайт)
(на вход подается слово 00100, красным цветом отмечен процесс распознавания слова автоматом, синим – процесс переброски дуг)

Выводы

В работе было рассмотрено поведение автомата-распознавателя при переброске одной дуги, а также при переброске k-дуг, где k > 2. Результаты переброски двух дуг на данный момент неизвестны и будут получены в результате выполнения магистерской работы.

На основании полученных данных были сделаны следующие выводы:

При написании данного реферата магистерская работа еще не завершена. Окончательное завершение: май 2018 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.

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

  1. Паулин О.Н. Основы теории алгоритмов: учебное пособие / О.Н. Паулин. – Одесса: Автограф, 2005. – 188 с.
  2. Алимов А.А., Шабалина О.А. Искусственный интеллект в компьютерных играх. Многоуровневое планирование и реактивное поведение агентовагентов / А.А. Алимов, О.А. Шабалина // Известия ВолгГТУ. – 2011. – № 10. – С. 90-94.
  3. Капитонова Ю.В. Основы дискретной математики / Ю.В. Капитонова, С.Л. Кривий, А.А. Летичевский, Г.М. Луцкий, Н.К. Печурин. – К.: Наукова думка, 2002. – 568 с.
  4. Смирнова Н.В., Смирнов В.В. Применение теории конечных автоматов в разработке программных систем / Н.В. Смирнова, В.В., Смирнов // Збірник наукових праць Кіровоградського національного технічного університету. Техніка в сільськогосподарському виробництві, галузеве машинобудування, автоматизація. – 2014. – Вип. 27. – С. 316-320.
  5. Салмре И. Программирование мобильных устройств на платформе .Net Compact Framework / И. Салмре. – М.: Вильямс, 2006. – 702 с.
  6. Бурдонов И.Б., Косачев А.С., Кулямин В.В. Использование конечных автоматов для тестирования программ / И.Б. Бурдонов, А.С. Косачев, В.В Кулямин // Программирование. – 2000. – № 2. – С. 12-28.
  7. Фомичев В.М. Дискретная математика и криптология / В.М. Фомичев. – М.: ДИАЛОГ-МИФИ, 2003. – 400 с.
  8. Агибалов Г.П. Конечные автоматы в криптографии / Г.П. Агибалов // Прикладная дискретная математика. Приложение. – 2009. – № 2. – С. 43-73.
  9. Гилл А. Введение в теорию конечных автоматов / А. Гилл. – М.: Наука, 1966. – 272 с.
  10. Мур Э.Ф. Умозрительные эксперименты с последовательностными машинами / Э.Ф. Мур // Автоматы. – М.: Иностр. лит. – 1956. – С. 179-210.
  11. Брауэр Р. Введение в теорию конечных автоматов/ Р. Брауэр. – М.: Радио и связь, 1987. – 392 с.
  12. Starke P. Abstract automata / P. Stapke // American Elsevier, 1972. – 419 с.
  13. Hennie F.C. Fault detecting experiments for sequential circuits / F.C. Hennie // Proc. 5 Annual Symp. «Switch. Circuits Th. and Logic. Design». – 1964. – P. 95-110.
  14. Василевский М.П. О распознавании неисправностей автомата / М.П. Василевский // Кибернетика. – 1973. – № 4. – С. 93-108.
  15. Евтушенко Н.В., Лебедев А.В., Петренко А. Ф. О проверяющих экспериментах с недетерминированными автоматами / Н.В. Евтушенко, А.В. Лебедев, А.Ф. Петренко // Автоматика и вычислительная техника. – 1991. – № 6. – С. 81-85.
  16. Евтушенко Н.В., Петренко А.Ф. Метод построения проверяющих экспериментов для произвольного недетерминированного автомата / Н.В. Евтушенко, А.Ф. Петренко // Автоматика и вычислительная техника. – 1990. – № 5. – С. 73-76.
  17. Евтушенко Н.В., Петренко А.Ф. О проверяющих возможностях кратных экспериментов / Н.В. Евтушенко, А.Ф. Петренко // Автоматика и вычислительная техника. – 1989. – №3. – С. 9-14.
  18. Петренко А.Ф. Эксперименты над протокольными объектами / А.Ф. Петренко // Автоматика и вычислительная техника. – 1987. – № 1. – С. 16-21.
  19. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов/ В.Б. Кудрявцев, С.В. Алешин, А.С. Подколзин. – М.: Наука, 1985. – 320 с.
  20. Кудрявцев В.Б., Грунский И.С., Козловский В.А. Анализ поведения автоматов / В.Б. Кудрявцев, И.С. Грунский, В.А. Козловский // Дискретная математика. – 2009. – №1. – С. 3-35.
  21. Кудявцев В.Б., Грунский И.С., Козловский В.А. Анализ и синтез абстрактных автоматов / В.Б. Кудрявцев, И.С. Грунский, В.А. Козловский //Фундаментальная и прикладная математика. – Т. 15, № 4. – 2009. – С. 101-175.
  22. Грунский И.С., Козловский В.А., Пономаренко Г.Г. Представления конечных автоматов фрагментами поведения/ И.С. Грунский, В.А. Козловский, Г.Г. Пономаренко. – Киев: Наукова думка, 1990. – 232 с.
  23. Грунский И.С. Анализ поведения конечных автоматов/ И.С. Грунский. – Луганск: изд-во Луганск. гос. пед. ун-та, 2003. – 318 с.
  24. Грунский И.С., Козловский В.А. Синтез и идентификация автоматов/ И.С. Грунский, В.А. Козловский. – Киев: Наукова думка, 2004. – 246 с.
  25. Грунский И.С., Максименко И.И. Об экспериментах с автоматами при отсутствии верхней оценки числа состояний / И.С. Грунский, И.И. Максименко // Кибернетика и системный анализ. – 1999. – № 4. – С. 59-71.
  26. Козловский В.А. О структуре контрольных экспериментов с автоматом / В.А. Козловский // Кибернетика. – 1978. – № 3. – С. 19-33.
  27. Козловский В.А. О распознавании автомата относительно локально порожденного класса / В.А. Козловский // ДАН СССР. – 1981. – № 5. – С. 1047-1049.
  28. Козловский В.А., Копытова О.М. Представления автоматов относительно m-плотных классов / В.А. Козловский, О.М. Копытова // Матер. VIII Межд. семинара «Дискретная математика и ее приложения» (Москва, 2-6 февраля 2004 г.) – М.: Изд. МГУ. – С. 277-280.
  29. Буевич В.А., Каландарашвили Н.Г., Таль А.А. Об описании конечного автомата с помощью конечного множества вход-выходных слов / В.А. Буевич, Н.Г. Каландарашвили, А.А. Таль // Автоматика и телемеханика. 1970. – № 1. – С. 112-122.
  30. Буевич В.А., Каландарашвили Н.Г., Таль А.А. Конечные автоматы – эквивалентность и поведение/ В.А. Буевич, Н.Г. Каландарашвили, А.А. Таль. – М.: Наука, 1984. – 192 с.
  31. Копытова О.М. О структуре автоматов, сохраняющих поведение при перебросках дуг / О.М. Копытова // Труды VIII Международной конференции «Дискретные модели в теории управляющих систем». – М.: Макс-Пресс, 2009. – C. 155-159.
  32. Копытова О.М. О возможности сохранения поведения автомата при перебросках дуг / О.М. Копытова // Материалы VI Международной научно–практической конференции Новости научной мысли – 2010 (27.10-05.11.2010), Чехия. Прага. Издательский дом Образование и наука, 2010 – C. 41-46.
  33. Копытова О.М. Устойчивость автоматов к неисправностям их функции переходов / О.М. Копытова // Труды ИПММ АН Украины. – 2010. – № 21. – С. 57-66.
  34. Швец О.С., Копытова О.М. О сравнении поведения ОДk-эталона и автоматов, порождаемых его локальными преобразованиями / О.С. Швец, О.М. Копытова // Материалы V всеукраинской научно-технической конференции студентов, аспирантов и молодых ученых «Информационные управляющие системы и компьютерный мониторинг (ИУС КМ 2014)» (22.04-23.04.2014). Донецк: ДонНТУ, 2014. – С. 365-369.
  35. Бурлаева Е.И., Копытова О.М. Об одном типе локальных преобразований автомата / Е.И. Бурлаева, О.М. Копытова // Материалы IV всеукраинской научно-технической конфиренции студентов, аспирантов и молодых ученых «Информационные управляющие системы и компьютерный мониторинг (ИУС КМ 2013)» (24.04-25.04.2013). Донецк: ДонНТУ, 2013. – C. 479-484.