Лисп-реализация конечных автоматов (стр. 2 из 2)
В силу последних двух замечаний, несмотря на большую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно недетерминированные конечные автоматы.
2.4 Автоматы и регулярные языки
Для автомата можно определить язык (множество слов) в алфавите Σ, который он представляет – так называется множество слов, при вводе которых автомат переходит из начального состояния в одно из состояний множества F.
Теорема Клини гласит, что класс языков, представимых конечными автоматами, совпадает с классом регулярных языков. Кроме того, этот класс совпадает с классом языков, задаваемых регулярными грамматиками.
3. Функциональные модели и блок-схемы решения задачи
Функциональные модели и блок-схемы решения задачи представлены на рисунках 4 – 7.
Условные обозначения:
· cur – текущее слово;
· char – текущий символ;
· text – входное слово;
· funct – функция смены состояний;
· start – начальное состояние;
· end – список конечных состояний.
Рисунок 4 – Функциональная модель решения задачи для функции KA
Рисунок 5 – Функциональная модель решения задачи для функции function1
Рисунок 6 – Функциональная модель решения задачи для функции function2
Рисунок 7 – Функциональная модель решения задачи для функции isOneof
4. Программная реализация решения задачи
; Тестовый конечный автомат – функция, преобразуюцая состояние
; Аргументы: 'cur' – текущее состояние
; 'char' – текущий символ
; Возвращаемое значение: новое состояние
(defunfunction1 (cur char)
(cond
((and (eqchar `a) (eq cur `qb)) `q1)
((and (eqchar `b) (eq cur `qb)) `q2)
((and (eqchar `c) (eq cur `q1)) `qe)
((and (eqchar `c) (eq cur `q2)) `qe)
(t `q0)
)
)
; Тестовый конечный автомат – функция, преобразуюцая состояние
; Аргументы: 'cur' – текущее состояние
; 'char' – текущий символ
; Возвращаемое значение: новое состояние
(defunfunction2 (cur char)
(cond
((and (eqchar `a) (eq cur `qb)) `q1)
((and (eqchar `b) (eq cur `qb)) `q2)
((and (eqchar `c) (eq cur `qb)) `q3)
((and (eqchar `a) (eq cur `q1)) `q1)
((and (eqchar `b) (eq cur `q2)) `q2)
((and (eqchar `c) (eq cur `q3)) `q3)
(Tnil)
)
)
; Функция проверки, является ли 'char' элементом 'set' (необходима для остановки)
; Алгоритм проверки:
; 1. 'set' пусто => нет
; 2. 'char' совпадает с головой 'set' => да
; 3. 'char' является злементом хвоста 'set' => да
; 4. 'set' – не список => нет
(defunisOneOf (setchar)
(cond
((eqsetnil) nil)
((eqchar (carset)) T)
((isOneOf (cdrset) char) T)
(Tnil)
)
)
; Непосредственно конечный автомат
; Аргументы: 'begin' – начальное состояние
; 'end' – список конечных состояний
; 'move' – функция смены состояний
; 'text' – входное слово
; Возвращаемое значение: 'Correct' – входное слово допустимо
; 'Incorrect' – входное слово недопустимо
; Алгоритм:
; 1. Лента пуста и
; а. текущее состояние финальное => слово допустимо
; б. текущее состояние не финальное => слово недопустимо
; 2. Текущий символ допустим и лента не пуста => движемся дальше
(defunKA (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 для описания поведения объектов используются диаграммы состояний. Кроме того, явное выделение состояний используется в описании сетевых протоколов.
Итогом работы можно считать созданную функциональную модель реализации конечных автоматов. Созданная функциональная модель и ее программная реализация могут служить органической частью решения более сложных задач.
Список использованных источников и литературы
1. Бронштейн, И.Н. Справочник по математике для инженеров и учащихся втузов [Текст] / И.Н. Бронштейн, К.А. Семендяев. – М.: Наука, 2007. – 708 с.
2. Дехтярь, М.И. Введение в схемы, автоматы и алгоритмы. [Электронный ресурс] / М.И. Дехтярь. – М.: Наука, 2002. С. 642.
3. Конечный автомат [Электронный ресурс] – Режим доступа: http://ru/wikipedia.org/wiki/Конечный_автомат.
4. Мозговой, М.В. Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход. / М.В. Мозговой. – М.: Наука и Техника, 2006. С. 320.
5. Семакин, И.Г. Основы программирования. [Текст] / И.Г. Семакин, А.П. Шестаков. – М.: Мир, 2006. C. 346.
6. Симанков, В.С. Основы функционального программирования [Текст] / В.С. Симанков, Т.Т. Зангиев, И.В. Зайцев. – Краснодар: КубГТУ, 2002. – 160 с.
7. Степанов, П.А. Функциональное программирование на языке Lisp. [Электронный ресурс] / П.А. Степанов, А.В. Бржезовский. – М.: ГУАП, 2003. С. 79.
8. Хювенен Э. Мир Лиспа [Текст] / Э. Хювенен, Й. Сеппянен. – М.: Мир, 1990. – 460 с.