Федеральное агентство по образованию фгоу впо «чувашский государственный университет имени и. Н. Ульянова» алатырский филиал

Вид материала

Курсовая

Подобный материал:

• Экобиологические механизмы акустического и теплового взаимодействия пчел 03. 02., 944.94kb.
• Архивное дело в чувашии в XVIII начале, 410.68kb.
• Молодежь чувашии в 1917 1985 годы: исторический опыт реализации советской молодежной, 726.89kb.
• Социально-технологический аспект цивилизационных и формационных изменений общества, 631.83kb.
• Становление марийской, мордовской и чувашской автономий в 20 30-е годы XX века, 795.46kb.
• Методические особенности обучения тригонометрии учащихся профильных классов 13. 00., 424.17kb.
• Перечень вступительных испытаний в фгбоу впо чувашский государственный университет, 172.51kb.
• Морфофункциональная характеристика пульпы зуба и оценка иммунного статуса при кариесе,, 552.48kb.
• Этнография детства чувашей Волго-Уралья во второй половине XIX первой трети XX вв.:, 721.38kb.
• «Молодые ученые о современном финансовом рынке рф», 228.93kb.

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ФГОУ ВПО

«ЧУВАШСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ И.Н.УЛЬЯНОВА»

АЛАТЫРСКИЙ ФИЛИАЛ

 

ФАКУЛЬТЕТ УПРАВЛЕНИЯ И ЭКОНОМИКИ

Кафедра высшей математики и информационных технологий

 

 


КУРСОВАЯ РАБОТА

По дисциплине «Математическая Логика»

на тему:

«Алгоритмы и автоматы»

 

 

Студент: Яшин А.В.

Группа: АФТ-0508

Руководитель: асс. Мигунова Е.С.


 

«Допустить к защите»

«______» __________ 2009 г.

Дата представления работы: «______» __________ 2009 г.

Дата защиты:                         «______» __________ 2009 г.

Оценка: _________________

 

 

Алатырь,

2009 год

Содержание

Введение 3

1. Проблема определения понятия «алгоритм» 4

2. Понятие алгоритма 5

3. Формализация понятия алгоритмов. Теория алгоритмов 8

4. История конечных автоматов: машина Поста и машина Тьюринга 9

5. Детерминированные конечные автоматы 11

6. Представление детерминированного конечного автомата в виде

графа 13

7. Минимизация детерминированного конечного автомата 14

8. Устройство автоматов с магазинной памятью 15

9. Отличия автоматов с магазинной памятью от обычных конечных автоматов 16

Заключение 18

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


Введение

Компьютерная наука — область весьма прагматичная. В далеко не чуждой ей математике до сих пор существует (хотя и весьма условное) разделение на «чистую» и «прикладную» ветви. Насколько известно, многие математики и поныне занимаются лишь абстрактными моделями, не имеющими видимого применения в современном мире. Некоторые из таких, казалось бы, абсолютно бесполезных конструкций, изученных в прошлом, пришлись весьма кстати сейчас; другие все еще ждут своего момента, третьи, вероятно, не окажутся востребованными никогда, оста­ваясь не более чем затейливыми интеллектуальными игрушками.

Компьютерная наука не витает в облаках, а прочно стоит на земле. Здесь всегда действует марксистский принцип «практика — критерии истины». Любое, даже самое, на первый взгляд, абстрактное понятие призвано содействовать решению практических задач. Иногда, впрочем, компью­терные модели могут увести далеко от реальности; бывают и ситуации, когда изначально искусственные конструкции вызывают живые аналогии с процессами, происходящими в природе. Тогда компьютерная наука, ото­рвавшись от привычного жонглирования числами, начинает претендовать на роль мощного инструмента, с помощью которого можно попытаться познать мир и даже самих себя. Так или иначе, любая модель, любая умозрительная конструкция в конечном итоге подлежит реализации на компьютере и проверке практикой. Тогда становится ясно, какие идеи содержат в себе здравое зерно, а какие являются всего лишь неадекватной решаемой задаче игрой воображения.

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

- Что такое алгоритм?

- Почему одну задачу решить просто, другую сложно, а третью вообще никак не удастся?

- Как создать машину (автомат), решающую задачи?

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


Проблема определения понятия «алгоритм»

На протяжении многих веков понятие алгоритма связывалось с числами и относительно простыми действиями над ними, да и сама математика была, по большей части, наукой о вычислениях, наукой прикладной. Чаще всего алгоритмы представлялись в виде математических формул. Порядок элементарных шагов алгоритма задавался расстановкой скобок, а сами шаги заключались в выполнении арифметических операций и операций отношения (проверки равенства, неравенства и т.д.). Часто вычисления были громоздкими, а вычисления вручную – трудоемкими, но суть самого вычислительного процесса оставалась очевидной. У математиков не возникала потребность в осознании и строгом определении понятия алгоритма, в его обобщении. Но с развитием математики появлялись новые объекты, которыми приходилось оперировать: векторы, графы, матрицы, множества и др. Как определить для них однозначность или как установить конечность алгоритма, какие шаги считать элементарными? В 1920-х задача точного определения понятия алгоритма стала одной из центральных проблем математики. В то время существовало две точки зрения на математические проблемы:

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

Есть проблемы, для которых алгоритм вообще не может существовать.

Идея о существовании алгоритмически неразрешимых проблем оказалась верной, но для того, чтобы ее обосновать, необходимо было дать точное определение алгоритма. Попытки выработать такое определение привели к возникновению теории алгоритмов, в которую вошли труды многих известных математиков – К.Гедель, К.Черч, С.Клини, А.Тьюринг, Э.Пост, А.Марков, А.Колмогоров и многие другие.

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

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


Понятие алгоритма

В повседневной жизни каждый человек сталкивается с необходимостью решения задач самой разной сложности. Некоторые из них трудны и требуют длительных размышлений для поиска решений (а иногда его так и не удается найти), другие же, напротив, столь просты и привычны, что решаются автоматически. При этом выполнение даже самой простой задачи осуществляется в несколько последовательных этапов (шагов). В виде последовательности шагов можно описать процесс решения многих задач, известных из школьного курса математики: приведение дробей к общему знаменателю, решение системы линейных уравнений путем последовательного исключения неизвестных, построение треугольника по трем сторонам с помощью циркуля и линейки и т.д. Такая последовательность шагов в решении задачи называется алгоритмом. Каждое отдельное действие – это шаг алгоритма. Последовательность шагов алгоритма строго фиксирована, т.е. шаги должны быть упорядоченными. Правда, существуют параллельные алгоритмы, для которых это требование не соблюдается.

Понятие алгоритма близко к другим понятиям, таким, как метод (метод Гаусса решения систем линейных уравнений), способ (способ построения треугольника по трем сторонам с помощью циркуля и линейки). Можно сформулировать основные особенности именно алгоритмов.

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

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

Детерминированность. При применении алгоритма к одним и тем же исходным данным должен получаться всегда один и тот же результат, поэтому, например, процесс преобразования информации, в котором участвует бросание монеты, не является детерминированным и не может быть назван алгоритмом.

Результативность. Выполнение алгоритма должно обязательно приводить к его завершению. В то же время можно привести примеры формально бесконечных алгоритмов, широко применяемых на практике. Например, алгоритм работы системы сбора метеорологических данных состоит в непрерывном повторении последовательности действий («измерить температуру воздуха», «определить атмосферное давление»), выполняемых с определенной частотой (через минуту, час) во все время существования данной системы.

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

Формы представления алгоритмов. Для записи алгоритмов необходим некоторый язык, при этом очень важно, какой именно язык выбран. Записывать алгоритмы на русском языке (или любом другом естественном языке) громоздко и неудобно.

Например, описание алгоритма Евклида нахождения НОД (наибольшего общего делителя) двух целых положительных чисел может быть представлено в виде трех шагов. Шаг 1: Разделить m на n. Пусть p – остаток от деления.

Шаг 2: Если p равно нулю, то n и есть исходный НОД.

Шаг 3: Если p не равно нулю, то сделаем m равным n, а n равным p. Вернуться к шагу 1.

Приведенная здесь запись алгоритма нахождения НОД очень упрощенная. Запись, данная Евклидом, представляет собой страницу текста, причем последовательность действий существенно сложней.

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

На рисунке представлена блок-схема алгоритма нахождения НОД:



Построение блок-схем из элементов всего лишь нескольких типов дает возможность преобразовать их в компьютерные программы и позволяет формализовать этот процесс.


Формализация понятия алгоритмов. Теория алгоритмов

Приведенное определение алгоритма нельзя считать представленным в привычном математическом смысле. Математические определения фигур, чисел, уравнений, неравенств и многих других объектов очень четки. Каждый математически определенный объект можно сравнить с другим объектом, соответствующим тому же определению. Например, прямоугольник можно сравнить с другим прямоугольником по площади или по длине периметра. Возможность сравнения математически определенных объектов – важный момент математического изучения этих объектов. Данное определение алгоритма не позволяет сравнивать какие-либо две таким образом определенные инструкции. Можно, например, сравнить два алгоритма решения системы уравнений и выбрать более подходящий в данном случае, но невозможно сравнить алгоритм перехода через улицу с алгоритмом извлечения квадратного корня. С этой целью нужно формализовать понятие алгоритма, т.е. отвлечься от существа решаемой данным алгоритмом задачи, и выделить свойства различных алгоритмов, привлекая к рассмотрению только его форму записи. Задача нахождения единообразной формы записи алгоритмов, решающих различные задачи, является одной из основных задач теории алгоритмов. В теории алгоритмов предполагается, что каждый шаг алгоритма таков, что его может выполнить достаточно простое устройство (машина), Желательно, чтобы это устройство было универсальным, т.е. чтобы на нем можно было выполнять любой алгоритм. Механизм работы машины должен быть максимально простым по логической структуре, но настолько точным, чтобы эта структура могла служить предметом математического исследования. Впервые это было сделано американским математиком Эмилем Постом в 1936 (машина Поста) еще до создания современных вычислительных машин и (практически одновременно) английским математиком Аланом Тьюрингом (машина Тьюринга).


История конечных автоматов: машина Поста и машина Тьюринга

Машина Поста – абстрактная вычислительная машина, предложенная Постом (Emil L.Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».

В 1935 американский математик Пост опубликовал в «Журнале символической логики» статью Финитные комбинаторные процессы, формулировка 1. В этой статье и появившейся одновременно в Трудах Лондонского математического общества статье английского математика Тьюринга О вычислимых числах с приложением к проблеме решения были даны первые уточнения понятия «алгоритм». Важность идей Поста состоит в том, что был предложен простейший способ преобразования информации, именно он построил алгоритмическую систему (алгоритмическая система Поста). Пост доказал, что его система обладает алгоритмической полнотой. В 1967 профессор В.Успенский пересказал эти статьи с новых позиций. Он ввел термин «машина Поста». Машина Поста – абстрактная машина, которая работает по алгоритмам, разработанным человеком, она решает следующую проблему: если для решения задачи можно построить машину Поста, то она алгоритмически разрешима. В 1970 машина Поста была разработана в металле в Симферопольском университете. Машина Тьюринга была построена в металле в 1973 в Малой Крымской Академии Наук.

Абстрактная машина Поста представляет собой бесконечную ленту, разделенную на одинаковые клетки, каждая из которых может быть либо пустой, либо заполненной меткой «V». У машины есть головка, которая может перемещаться вдоль ленты на одну клетку вправо или влево, наносить в клетку ленты метку, если этой метки там ранее не было, стирать метку, если она была, либо проверять наличие в клетке метки. Информация о заполненных метками клетках ленты характеризует состояние ленты, которое может меняться в процессе работы машины. В каждый момент времени головка находится над одной из клеток ленты и, как говорят, обозревает ее. Информация о местоположения головки вместе с состоянием ленты характеризует состояние машины Поста. Работа машины Поста заключается в том, что головка передвигается вдоль ленты (на одну клетку за один шаг) влево или вправо, наносит или стирает метки, а также распознает, есть ли метка в клетке в соответствии с заданной программой, состоящей из отдельных команд.

Машина Тьюринга состоит из счетной ленты (разделенной на ячейки и ограниченной слева, но не справа), читающей и пишущей головки, лентопротяжного механизма и операционного исполнительного устройства, которое может находиться в одном из дискретных состояний q0, q1, …, qs , принадлежащих некоторой конечной совокупности (алфавиту внутренних состояний), при этом q0 называется начальным состоянием. Читающая и пишущая головка может читать буквы рабочего алфавита A = {a0, a1, …, at }, стирать их и печатать. Каждая ячейка ленты в каждый момент времени занята буквой из множества А. Чаще всего встречается буква а0 – «пробел». Головка находится в каждый момент времени над некоторой ячейкой ленты – текущей рабочей ячейкой. Лентопротяжный механизм может перемещать ленту так, что головка оказывается над соседней ячейкой ленты, при этом возможна ситуация выхода за левый край ленты, которая является аварийной (недопустимой), или машинного останова, когда машина выполняет предписание об остановке.


Детерминированные конечные автоматы



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

Итак, на какие элементы автомата следует обратить внимание?

- Сам по себе автомат является неким «виртуальным устройством», умеющим выполнять определенного рода работу.

- У автомата есть подвижная «стрелка», указывающая на то или иное число, называемое его состоянием. Таким образом, изображенный на рисунке автомат в настоящий момент находится в состоянии номер три.

- Самих состояний может быть сколь угодно много, но их число конечно (поэтому и автомат называется конечным).

- Среди всех состояний можно выделить «особые»: это, в первую оче­редь, начальное состояние и одно или более допускающих состояний. Начальное состояние — это состояние автомата на момент запуска (то есть пока он еще не выполнил никакой работы). Допуска­ющие состояния ничем не отличаются от обычных, просто их набор оговаривается заранее, и мы в любой момент знаем, какое состояние считается допускающим, а какое — нет. На рисунке допускающие состояния выделены контурным шрифтом (таким образом, у нашего автомата всего одно допускающее состояние — номер два). Допускающие состояния нужны для анализа результатов работы автомата. В зависимости от того, относится ли на момент завершения всех действий текущее состояние к допускающим или не относится, мы будем делать различные выводы о данных, поступающих автомату на вход.

- На правой стенке автомата установлено считывающее устройство, уме­ющее обрабатывать бумажные ленты конечной длины, разграфленные на клетки и содержащие в каждой клетке некий символ (разумеется, пустая клетка тоже в известном смысле может считаться символом). Лента в нашем случае содержит строку СААВ.

- В памяти автомата (нарисована слева вверху) находится конечная «та­блица правил» (или «таблица переходов»), сверяясь с которой, автомат определяет, что делать в той или иной ситуации. По существу, набор его действий состоит только из переходов в то или иное состояние (как видно из рисунка, кроме подвижной стрелки у автомата нет никаких активно действующих узлов вроде встроенного лазерного принтера или бортовой крупнокалиберной пушки). Элементы таблицы правил следует читать так: «если очередной входной символ — В, а текущее состояние — второе, то переходим в состояние номер четыре», «если очередной входной символ — С, а текущее состояние — третье, то переходим в состояние номер один» и так далее.

- Пара (текущее состояние, очередной входной символ) однозначным образом определяет используемое в данной ситуации правило пере­хода. Поэтому автомат называется детерминированным.

Автомат работает по следующей простой схеме. Сначала считывается очередной входной символ с ленты, затем производится переход в новое состояние согласно таблице правил, затем цикл повторяется. Работа за­канчивается после того, как входная лента будет обработана целиком. Таким образом, процесс работы автомата, изображенного на рис. 2.1, выглядит так:

начальное состояние = 3

считать символ (результат = С)

перейти к состоянию 1 (правило 3, С -> 1)

считать символ (результат = А)

перейти к состоянию 5 (правило 1, А -> 5)

считать символ (результат = А)

перейти к состоянию 2 (правило 5, А -> 2)

считать символ (результат = В)

перейти к состоянию 4 (правило 2, В -> 4)

закончить работу

На момент завершения работы текущим состоянием автомата является состояние номер четыре.


Представление детерминированного конечного автомата в виде графа

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

Рассмотрим граф, соответствующий уже знакомому нам по рисунку автомату.



Как «читать» такой чертеж? Кружочки (узлы графа) представляют собой состояния конечного автомата. Сразу же видно, что их пять, и обозначены они с помощью чисел от 1 до 5.

Допускающее состояние (второе) отмечено двойной границей круга. Стрелки (ребра графа) наглядно изображают таблицу правил (например, правило 3, С -> 1 обозначается ребром, помеченным буквой С, которое соединяет узел 3 с узлом 1). Стрелка, идущая «из ниоткуда», указывает на начальное состояние автомата (третье).


Минимизация детерминированного конечного автомата

Длинная и неэффективная программа вполне может выполнять ту же самую работу, что и другая — короткая и скоростная. Точно так же не исключено, что два различных автомата распознают один и тот же язык. А «если нет разницы, зачем платить больше?» Зачем использовать громоздкий, сложный автомат вместо маленького и простого?

Прежде чем обсуждать эту тему дальше, справедливости ради стоит отметить одно различие между «некоторой данной программой» и про­граммной реализацией детерминированного конечного автомата. Дело в том, что две программы, реализующие одну и ту же функциональность, могут иметь совершенно различные характеристики как по скорости работы, так и по требуемым ресурсам. Автоматы же всегда затрачивают на работу время, пропорциональное длине входной ленты, независимо от сложности своего устройства. Поэтому единственным параметром, отличающим более предпочтительный автомат от менее предпочтитель­ного, является количество состояний. Понятно, что автомат с меньшим числом состояний требует меньшего объема памяти, да и устроен он обычно проще.

По какой причине некоторый рассматриваемый нами автомат может оказаться неоптимальным (то есть содержащим больше состояний, чем необходимо для распознавания интересующего языка)? Во-первых, раз­рабатывая автомат с помощью карандаша и бумаги, вы естественным образом думаете о распознаваемом языке, а не о минимизации состояний. Во-вторых, нередки случаи (и мы с ними познакомимся), когда конечный автомат создается, простите за тавтологию, автоматически некоторой компьютерной программой. При этом полученное устройство почти всегда будет очень далеким от оптимального¹⁶.

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

Прежде всего нам потребуется понятие эквивалентности состояний. Два состояния называются эквивалентными (не вдаваясь в математические подробности), если дальнейшее поведение автомата в первом состоянии совпадает с дальнейшим поведением автомата во втором состоянии. Сказанное – на рисунке.




Устройство автоматов с магазинной памятью

По сути, автомат с магазинной памятью — это несколько «доработан­ный» обычный конечный автомат. Доработка заключается в добавлении к автомату магазинной памяти. Слово «магазинный» в данном контек­сте, разумеется, должно ассоциироваться не с гастрономом, а, скорее, патронным магазином «Калашникова». В современной терминологии такою рода память называется всем известным словом стек. Таким образом, наша нынешняя задача - рассмотрение автоматов со стековой памятью.

Напомню, что стеком называется хранилище (обычно однород­ных) данных, для обращения к которому существуют две операции:

- положить объект данных на вершину стека (операция push);

- взять объект данных с вершины стека (операция pop).

Стек автомата считается бесконечным, поэтому проблемы переполнения не возникает. Но что случится, если в процессе работы автомата произой­ди попытка извлечь из пустого стека очередное значение? Что ж, это новый пример исключительной ситуации, аналогичный попытке перейти по несуществующему правилу. Как правило, такое событие должно рас­цениваться просто как недопускание входной строки.




Отличия автоматов с магазинной памятью от обычных конечных автоматов

Автоматы с магазинной памятью во многом похожи на обычные конечные автоматы. Отличия приведены в списке:

1. Автомат с магазинной памятью включает в себя стек, изначально пустой. В стеке можно хранить элементы, являющиеся элементами «множества стековых символов». Это множество мы выбираем сами исходя из каких-то личных соображений.

2, Правила перехода обычного конечного автомата сопоставляют паре (состояние, символ) какое-то новое состояние. Правила перехода магазинного автомата немного сложнее. Каждой тройке (состояние, символ, стек) теперь сопоставляется пара (состояние', стек'). Смысл компонентов «состояние», «символ» и «состояние» - тот же, что и раньше, при этом переходы без считывания очередного символа (е-переходы) считаются допустимыми. Компонент стек определяет, какие символы должны находиться на вершине стека в данный мо­мент (иначе текущее правило попросту не подходит в этой ситуации). При выполнении перехода эти символы снимаются с вершины стека. Компонент стек' правой части правила определяет символы, которые кладутся на вершину стека при выполнении перехода. Так, правило 1, с, а -> 2, b означает «если текущее состояние — первое, очередной символ входной ленты равен с, а на вершине находится элемент а, то снять а с вершины стека, перейти в состояние 2 и положить символ b на вершину стека». Символ е в качестве компонента стек означает «ничего не снимать со стека» (при этом текущее состояние стека не играет роли; считается, что «пустой символ» присутствует на вершине всегда). Аналогично, в роли компонента стек' означает «ничего не класть на стек» Обратите внимание, что, вообще говоря, значения компонентов стек и стек' - строки, а не одиночные символы. При этом первый символ такой строки считается лежащим на вершине стека, а последний, соответственно, — лежащим наиболее «глубоко».



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

4. Магазинный автомат по умолчанию считается недетерминирован­ным. Правила, предлагающие различные действия в одних и тех же ситуациях, допустимы.

При изображении магазинного автомата в виде графа переходы обычно метят тройками (с, s, е), где с - считываемый символ входной ленты, s - извлекаемая из стека последовательность элементов, а е - после­довательность элементов, помещаемая на вершину стека.


Заключение

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


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

1. Кормен Т., Лейзерсон, Ривес Р. Алгоритмы. Построение и анализ. М., МЦНМО, 1999

2. Касаткин В.Н. Информация, алгоритмы, ЭВМ. М., Просвещение, 1991.

3. Мозговой М.В. Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход. Спб., Наука и техника, 2006.

4. Айзерман М.А. Логика. Автоматы. Алгоритмы. М., Физматгиз, 1963.

5. А.Н. Мелихов, В.И. Кодачигов. Теория алгоритмов и формальных языков: Учебное пособие. Таганрог: ТРТУ, 2006.