Dfl'jbvgil

  • 23 дек. 2010 г.
  • 1917 Слова
Содержание

Введение
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 – входной алфавит, из которого формируются строки, считываемые...
tracking img