47514 (Лисп-реализация конечных автоматов)

Содержание

Введение

1. Постановка задачи

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

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

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

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

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

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

4. Программная реализация решения задачи

5. Пример выполнения программы

Заключение

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

Введение

В качестве примера, хорошо поясняющего сущность конечного автомата, часто приводят автомат для продажи каких-то товаров. Опускаемые в автомат монеты соответствуют записываемым входным символам. Сам автомат хранит в памяти данные о полученной до настоящего момента общей сумме, к которой будет добавляться новая сумма, состоящая из только что опущенных в автомат монет. Эта хранящаяся в памяти прежняя сумма соответствует состоянию конечного автомата. Когда в автомат опускаются деньги, составляющие цену билета, порции кофе и т.д., срабатывает механическое устройство, выдающее покупателю товар вместе со сдачей, и опущенная в прорезь автомата сумма сбрасывается в Нуль.

Современные автоматы не просто продают какой-то один вид товара. В них сделаны специальные окошечки, в которых высвечивается опущенная в прорезь автомата сумма. Указываемая в окошке сумма соответствует состоянию, набор монет соответствует входному символу, а выдаваемый автоматом товар вместе со сдачей – выходному символу. Если даже бросить монеты в автомат наугад, но сумма превысит определенную величину, товар будет выдан вместе со сдачей. Брошенная в автомат сумма должна иметь верхний предел, то есть не может быть неограниченно большой. Таким образом, число состояний, число входных символов (число комбинаций монет) и число выходных символов (число выдаваемых разновидностей товара вместе со сдачей) конечны.

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

Устройство выполнения операций, устройство управления и оперативное (основное) запоминающее устройство, входящие в состав машины Тьюринга, делают ее машиной с ограниченным числом состояний, то есть самым настоящим конечным автоматом. Другими словами, при запоминании конечного числа каких-то элементов можно характеристики этих элементов представить в виде набора состояний конечного автомата. Бесконечное число состояний или, говоря языком логики, сколь угодно большое наперед заданное число состояний запомнить невозможно.

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

Целью данной курсовой работы является ЛИСП-реализация конечных автоматов.

1. Постановка задачи

Конечный автомат – автомат, проверяющий допустимость слова на ленте, и возвращающий True / False (в данном случае Correct / Incorrect).

Конечный автомат может двигаться по ленте только в одном направлении.

Требуется написать функцию, реализующую конечный автомат.

На вход ей подается начальное состояние, конечные состояния, функция смены состояний и содержимое ленты.

Возвращаемое значение – ответ на вопрос, допустимо ли данное слово данным конечным автоматом.

Пример 1.

Таблица 1 – Таблица переходов

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

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

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

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

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

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

с qb q0

с q0 q0.

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

Пример 2.

Таблица 2 – Таблица переходов

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 – конечное множество состояний автомата;

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

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

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

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

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

Автомат начинает работу в состоянии q₀, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из 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 – Функциональная модель решения задачи для функции function1

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

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