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