47514 (Лисп-реализация конечных автоматов), страница 2
Описание файла
Документ из архива "Лисп-реализация конечных автоматов", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "47514"
Текст 2 страницы из документа "47514"
4. Программная реализация решения задачи
; Тестовый конечный автомат – функция, преобразуюцая состояние
; Аргументы: 'cur' – текущее состояние
; 'char' – текущий символ
; Возвращаемое значение: новое состояние
(defun function1 (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 с.