Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Курсовая работа: Лисп-реализация конечных автоматов

Название: Лисп-реализация конечных автоматов
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 11:35:27 15 января 2010 Похожие работы
Просмотров: 396 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Содержание

Введение

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

qb – начальное состояние автомата;

qe – множество заключительных состояний;

a, b, c – входной алфавит, из которого формируются строки, считываемые автоматом;

cc – строка, считываемая автоматом.

Проверим допустимо ли слово на ленте для данного автомата.

Согласно таблице переходов получаем:

с qb®q0

с q0®q0.

Так как q0 не соответствует множеству заключительных состояний, следовательно данное слово 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 q1®q1

a q1®q1

a q1®q1

a q1®q1

a q1®q1

a q1®q1

Так как q1 соответствует множеству заключительных состояний, следовательно данное слово aaaaaa допустимо для данного автомата.

2. Математические и алгоритмические основы решения задачи

2.1 Понятие конечного автомата

Конечный автомат – в теории алгоритмов математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных, при условии, что общее возможное количество состояний конечно. Конечный автомат является частным случаем абстрактного автомата.

Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров:

где:

Q – конечное множество состояний автомата;

q0 – начальное состояние автомата ();

F – множество заключительных (или допускающих) состояний, таких что ;

Σ – допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;

δ – заданное отображение множества во множество подмножеств Q:

(иногда δ называют функцией переходов автомата).

Автомат начинает работу в состоянии q0 , считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».

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

2.2 Способы описания

Диаграмма состояний (или иногда граф переходов) – графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф, вершины которого – состояния конечного автомата, дуги – переходы из одного состояния в другое, а нагрузка – символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой должны быть надписаны все они.

Таблица переходов – табличное представление функции δ. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу – один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ.

2.3 Детерминированность

Конечные автоматы подразделяются на детерминированные и недетерминированные.


http://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:%D0%94%D0%9A%D0%90.jpg

Рисунок 1 – Детерминированный http://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:%D0%94%D0%9A%D0%90.jpgконечный автомат

Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.

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

1. Существуют переходы, помеченные пустой цепочкой ε (рисунок 2).

Рисунок 2 – Недетерминированный конечный автомат с пустыми переходами

2. Из одного состояния выходит несколько переходов, помеченных одним и тем же символом (рисунок 3).


Рисунок 3 – Недетерминированный конечный автомат с несколькими переходами

Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном детерминированном конечном автомате в худшем случае растёт экспоненциально с ростом количества состояний исходного недетерминированного конечного автомата, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.

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

2.4 Автоматы и регулярные языки

Для автомата можно определить язык (множество слов) в алфавите Σ, который он представляет – так называется множество слов, при вводе которых автомат переходит из начального состояния в одно из состояний множества F.

Теорема Клини гласит, что класс языков, представимых конечными автоматами, совпадает с классом регулярных языков. Кроме того, этот класс совпадает с классом языков, задаваемых регулярными грамматиками.

3. Функциональные модели и блок-схемы решения задачи

Функциональные модели и блок-схемы решения задачи представлены на рисунках 4 – 7.

Условные обозначения:

· cur – текущее слово;

· char – текущий символ;

· text – входное слово;

· funct – функция смены состояний;

· start – начальное состояние;

· end – список конечных состояний.

Рисунок 4 – Функциональная модель решения задачи для функции KA


Рисунок 5 – Функциональная модель решения задачи для функции function1


Рисунок 6 – Функциональная модель решения задачи для функции function2


Рисунок 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 для описания поведения объектов используются диаграммы состояний. Кроме того, явное выделение состояний используется в описании сетевых протоколов.

Итогом работы можно считать созданную функциональную модель реализации конечных автоматов. Созданная функциональная модель и ее программная реализация могут служить органической частью решения более сложных задач.

Список использованных источников и литературы

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 с.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений07:25:06 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
19:38:22 28 ноября 2015

Работы, похожие на Курсовая работа: Лисп-реализация конечных автоматов

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(150728)
Комментарии (1839)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru