Зміст
Введення
1. Постановка завдання
2. Математичні та алгоритмічні основи рішення задачі
2.1 Поняття кінцевого автомата
2.2 Способи опису
2.3 Детермінованість
2.4 Автомати й регулярні мови
3. Функціональні моделі та блок-схеми виконання завдання
4. Програмна реалізація рішення задачі
5. Приклад виконання програми
Висновок
Список використаних джерел та літератури
Введення
Як приклад, добре поясняющего сутність кінцевого автомата, часто призводять автомат для продажу якихось товарів. Опускаються в автомат монети відповідають записуваних вхідним символам. Сам автомат зберігає в пам'яті дані про отриману до теперішнього моменту загальній сумі, до якої буде додаватися нова сума, що складається з тільки що опущених в автомат монет. Ця зберігається в пам'яті колишня сума відповідає стану кінцевого автомата. Коли в автомат опускаються гроші, що становлять ціну квитка, порції кави і т.д., спрацьовує механічний пристрій, що видає покупцеві товар разом з рештою, і опущена в проріз автомата сума скидається в Нуль.
Сучасні автомати не просто продають якийсь один вид товару. У них зроблені спеціальні віконечка, в яких висвічується опущена в проріз автомата сума. Вказується у віконці сума відповідає стану, набір монет відповідає вхідному символу, а видається автоматом товар разом зі здачею - вихідного символу. Якщо навіть кинути монети в автомат навмання, але сума перевищить певну величину, товар буде виданий разом зі здачею. Кинута в автомат сума повинна мати верхню межу, тобто не може бути необмежено великою. Таким чином, число станів, число вхідних символів (число комбінацій монет) і число вихідних символів (кількість видаваних різновидів товару разом із здачею) кінцеві.
Як тільки автомат встановлено, він включається в мережу обслуговування, яка стежить за регулярним вилученням грошей і поповненням автомата товаром. Тому час роботи автомата можна вважати необмеженим. Поки автомат справний, він перебуває на обліку, і повний термін його служби в загальному непередбачуваний.
Пристрій виконання операцій, пристрій управління і оперативне (основне) запам'ятовуючий пристрій, що входять до складу машини Тьюрінга, роблять її машиною з обмеженим числом станів, тобто самим справжнім кінцевим автоматом. Іншими словами, при запам'ятовуванні кінцевого числа якихось елементів можна характеристики цих елементів представити у вигляді набору станів кінцевого автомата. Нескінченне число станів або, говорячи мовою логіки, як завгодно велике наперед задане число станів запам'ятати неможливо.
У кінцевому автоматі не можна запам'ятати число станів, більше числа, заздалегідь заданого для цього автомата, яке визначається параметрами робочих стрічок. Хоча кількість різновидів символів, використовуваних на стрічках, є кінцевим, число комірок може бути нескінченним, як нескінченний сам натуральний ряд чисел. Як у двійковій, так і в десятковій системах числення на робочих стрічках можна записати послідовність цифр з необхідним числом розрядів і, таким чином, запам'ятати будь-яке велике число даної розрядності.
Метою даної курсової роботи є ЛИСП-реалізація кінцевих автоматів.
1. Постановка завдання
Кінцевий автомат - автомат, перевіряючий допустимість слова на стрічці, та повертає True / False (в даному випадку Correct / Incorrect).
Кінцевий автомат може рухатися по стрічці тільки в одному напрямку.
Потрібно написати функцію, що реалізовує кінцевий автомат.
На вхід їй подається початковий стан, кінцеві стани, функція зміни станів і вміст стрічки.
Значення, що повертається - відповідь на питання, чи припустимо дане слово таким одним автоматом.
Приклад 1.
Таблиця 1 - Таблиця переходів
char | a | b | c | c | - |
cur | qb | qb | q1 | q2 | - |
q1 | q1 | q2 | qe | qe | q0 |
q b - початковий стан автомата;
q e - безліч заключних станів;
a, b, c - вхідний алфавіт, з якого формуються рядки, що прочитуються автоматом;
cc - рядок, зчитувальна автоматом.
Перевіримо чи припустимо слово на стрічці для даного автомата.
Згідно таблиці переходів отримуємо:
з q b ® q 0
з q 0 ® q 0.
Так як q 0 не відповідає множині заключних станів, отже дане слово cc не припустимо.
Приклад 2.
Таблиця 2 - Таблиця переходів
char | a | b | c | a | b | з |
cur | qb | qb | qb | q1 | q2 | q3 |
state | q1 | q2 | q3 | q1 | q2 | q3 |
q1 - початковий стан автомата;
q1, q2, q3 - безліч заключних станів;
a, b, c - вхідний алфавіт, з якого формуються рядки, що прочитуються автоматом;
aaaaaa - рядок, зчитувальна автоматом.
Перевіримо чи припустимо слово на стрічці для даного автомата.
Згідно таблиці переходів отримуємо:
a q 1 ® q1
a q1 ® q1
a q1 ® q1
a q1 ® q1
a q1 ® q1
a q1 ® q1
Так як q 1 відповідає безлічі заключних станів, отже дане слово aaaaaa припустимо для даного автомата.
2. Математичні та алгоритмічні основи рішення задачі
2.1 Поняття кінцевого автомата
Кінцевий автомат - в теорії алгоритмів математична абстракція, що дозволяє описувати шляху зміни стану об'єкту в залежності від його поточного стану і вхідних даних, за умови, що загальна можливу кількість станів звичайно. Кінцевий автомат є окремим випадком абстрактного автомата.
Існують різні варіанти завдання кінцевого автомата. Наприклад, кінцевий автомат може бути заданий за допомогою п'яти параметрів:
де:
Q - кінцеве безліч станів автомата;
q 0 - початковий стан автомата ( );
F - безліч заключних (або допускають) станів, таких що ;
Σ - припустимий вхідний алфавіт (кінцеве безліч допустимих вхідних символів), з якого формуються рядки, що прочитуються автоматом;
δ - заданий відображення множини в безліч
підмножин Q:
(Іноді δ називають функцією переходів автомата).
Автомат починає роботу у стані q 0, зчитуючи по одному символу вхідного рядка. Лічені символ переводить автомат в новий стан з Q у відповідності з функцією переходів. Якщо після завершення зчитування вхідного слова (ланцюжки символів) автомат опиняється в одному з допускають станів, то слово «приймається» автоматом. У цьому випадку говорять, що воно належить мові даного автомата. В іншому випадку слово «відкидається».
Кінцеві автомати широко використовуються на практиці, наприклад у синтаксичних, лексичних аналізаторах, і тестуванні програмного забезпечення на основі моделей.
2.2 Способи опису
Діаграма станів (або іноді граф переходів) - графічне представлення безлічі станів і функції переходів. Являє собою навантажений односпрямований граф, вершини якого - стану кінцевого автомата, дуги - переходи з одного стану в інший, а навантаження - символи, при яких здійснюється даний перехід. Якщо перехід зі стану q1 в q2 може бути здійснено при появі одного з декількох символів, то над дугою повинні бути надписані всі вони.
Таблиця переходів - табличне представлення функції δ. Зазвичай у такій таблиці кожному рядку відповідає один стан, а стовпцю - один допустимий вхідний символ. У клітинці на перетині рядка і стовпця записується дію, яку повинен виконати автомат, якщо в ситуації, коли він знаходився в даному стані на вході він отримав цей знак.
2.3 Детермінованість
Кінцеві автомати підрозділяються на детерміновані і недетерміновані.
Малюнок 1 - Детермінований кінцевий автомат
Детермінованим кінцевим автоматом (ДКА) називається такий автомат, в якому для кожної послідовності вхідних символів існує лише один стан, до якого автомат може перейти з поточного.
Недетермінірованние кінцевий автомат (НКА) є узагальненням детермінованого. Недетермінірованності автоматів досягається двома способами.
1. Існують переходи, помічені порожній ланцюжком ε (малюнок 2).
Малюнок 2 - Недетермінірованние кінцевий автомат з порожніми переходами
2. З одного стану виходить кілька переходів, помічених одним і тим же символом (рисунок 3).
Малюнок 3 - Недетермінірованние кінцевий автомат з кількома переходами
Існує теорема, яка говорить, що «Будь-який недетермінованих кінцевий автомат може бути перетворений в детермінований так, щоб їхні мови збігалися» (такі автомати називаються еквівалентними). Проте, оскільки кількість станів в еквівалентному детермінованому кінцевому автоматі в гіршому випадку зростає експоненціально з ростом кількості станів вихідного недетермінірованного кінцевого автомата, на практиці подібна детермінізації не завжди можлива. Крім того, кінцеві автомати з виходом в загальному випадку не піддаються детермінізації.
У силу останніх двох зауважень, незважаючи на б про більшу складність недетермінованих кінцевих автоматів, для завдань, пов'язаних з обробкою тексту, переважно застосовуються саме недетерміновані кінцеві автомати.
2.4 Автомати й регулярні мови
Для автомата можна визначити мову (безліч слів) в алфавіті Σ, який він представляє - так називається безліч слів, при введенні яких автомат переходить з початкового стану в один зі станів множини F.
Теорема Кліні свідчить, що клас мов, які представлені кінцевими автоматами, збігається з класом регулярних мов. Крім того, цей клас збігається з класом мов, що задаються регулярними граматиками.
3. Функціональні моделі та блок-схеми виконання завдання
Функціональні моделі та блок-схеми виконання завдання представлені на малюнках 4 - 7.
Умовні позначення:
cur - поточне слово;
char - поточний символ;
text - вхідне слово;
funct - функція зміни станів;
start - початковий стан;
end - список кінцевих станів.
Рисунок 4 - Функціональна модель вирішення задачі для функції KA
Рисунок 5 - Функціональна модель вирішення задачі для функції function 1
Малюнок 6 - Функціональна модель вирішення задачі для функції function 2
Малюнок 7 - Функціональна модель вирішення задачі для функції isOneof
4. Програмна реалізація рішення задачі
; Тестовий кінцевий автомат - функція, преобразуюцая стан
; Аргументи: 'cur' - поточний стан
; 'Char' - поточний символ
; Значення, що повертається: новий стан
(Defun function 1 (cur char)
(Cond
((And (eq char `a) (eq cur` qb)) `q1)
((And (eq char `b) (eq cur` qb)) `q2)
((And (eq char `c) (eq cur` q1)) `qe)
((And (eq char `c) (eq cur` q2)) `qe)
(T `q0)
)
)
; Тестовий кінцевий автомат - функція, преобразуюцая стан
; Аргументи: 'cur' - поточний стан
; 'Char' - поточний символ
; Значення, що повертається: новий стан
(Defun function2 (cur char)
(Cond
((And (eq char `a) (eq cur` qb)) `q1)
((And (eq char `b) (eq cur` qb)) `q2)
((And (eq char `c) (eq cur` qb)) `q3)
((And (eq char `a) (eq cur` q1)) `q1)
((And (eq char `b) (eq cur` q2)) `q2)
((And (eq char `c) (eq cur` q3)) `q3)
(T nil)
)
)
; Функція перевірки, чи є 'char' елементом 'set' (необхідна для зупинки)
; Алгоритм перевірки:
; 1. 'Set' порожньо => немає
; 2. 'Char' збігається з головою 'set' => та
; 3. 'Char' є злементи хвоста "set '=> та
; 4. 'Set' - не список => немає
(Defun isOneOf (set char)
(Cond
((Eq set nil) nil)
((Eq char (car set)) T)
((IsOneOf (cdr set) char) T)
(T nil)
)
)
; Безпосередньо кінцевий автомат
; Аргументи: 'begin' - початковий стан
; 'End' - список кінцевих станів
; 'Move' - функція зміни станів
; 'Text' - вхідне слово
; Значення, що повертається: 'Correct' - вхідне слово допустимо
; 'Incorrect' - вхідне слово неприпустимо
; Алгоритм:
; 1. Стрічка порожня і
; А. поточний стан фінальне => слово допустимо
; Б. поточне стан не фінальне => слово неприпустимо
; 2. Поточний символ допустимо і стрічка не порожня => рухаємося далі
(Defun KA (begin end move text)
(Cond
((Eq text nil)
(Cond
((IsOneOf end begin) `Correct)
(T `Incorrect)
)
)
(T (KA (funcall move begin (car text)) end move (cdr text)))
)
)
(Setq input_stream (open «D: \ \ text.txt»: direction: input))
; Вхідне слово
(Setq text (read input_stream))
; Функція зміни станів
(Setq funct (read input_stream))
; Початковий стан
(Setq start (read input_stream))
; Список кінцевих станів
(Setq end (read input_stream))
(Close input_stream)
(Setq output_stream (open «D: \ \ KA.txt»: direction: output))
(Print (KA start end funct text) output_stream)
(Terpri output_stream)
(Close output_stream)
5. Приклад виконання програми
Приклад 1
Малюнок 8 - Вхідні дані
Рисунок 9 - Вихідні дані
Приклад 2
Рисунок 10 - Вхідні дані
Малюнок 11 - Вихідні дані
Приклад 3.
Рисунок 12 - Вхідні дані
Малюнок 13 - Вихідні дані
Висновок
Мислення в термінах кінцевих автоматів (тобто розбиття виконання програми на кроки автомата та передача інформації від кроку до кроку через стан) необхідно при побудові подієво-орієнтованих додатків. У цьому випадку програмування в стилі кінцевих автоматів виявляється єдиною альтернативою породженню безлічі процесів або потоків управління.
Часто поняття станів і машин станів використовується для специфікації програм. Так, при проектуванні програмного забезпечення за допомогою UML для опису поведінки об'єктів використовуються діаграми станів. Крім того, явне виділення станів використовується в описі мережевих протоколів.
Підсумком роботи можна вважати створену функціональну модель реалізації кінцевих автоматів. Створена функціональна модель і її програмна реалізація можуть служити органічною частиною вирішення більш складних завдань.
Список використаних джерел та літератури
Бронштейн, І.М. Довідник з математики для інженерів і учнів втузів [Текст] / І.М. Бронштейн, К.А. Семендяев. - М.: Наука, 2007. - 708 с.
Дехтяр, М.І. Введення в схеми, автомати і алгоритми. [Електронний ресурс] / М.І. Дехтяр. - М.: Наука, 2002. С. 642.
Кінцевий автомат [Електронний ресурс] - Режим доступу: http: / / ru / wikipedia. Org / wiki / Конечний_автомат.
Мозговий, М.В. Класика програмування: алгоритми, мови, автомати, компілятори. Практичний підхід. / М.В. Мозговий. - М.: Наука і Техніка, 2006. С. 320.
Семакін, І.Г. Основи програмування. [Текст] / І.Г. Семакін, А.П. Шестаков. - М.: Світ, 2006. C. 346.
Сіманков, В.С. Основи функціонального програмування [Текст] / В.С. Сіманков, Т.Т. Зангієв, І.В. Зайцев. - Краснодар: КубГТУ, 2002. - 160 с.
Степанов, П.А. Функціональне програмування мовою Lisp. [Електронний ресурс] / П.А. Степанов, А.В. Бржезовскій. - М.: ГУАП, 2003. С. 79.
Хювенен Е. Світ Ліспу [Текст] / Е. Хювенен, Й. Сеппянен. - М.: Світ, 1990. - 460 с.