Русский   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.