Бильгаева Н.Ц.
Теория алгоритмов, формальных языков, грамматик и автоматов
Учебное пособие для студентов специальности 220400 -"Программное обеспечение вычислительной техники и автоматизированных систем"
Издательство ВСГТУ
Улан-Удэ 2000
УДК 681.5.01:
Бильгаева Н.Ц. Теория алгоритмов, формальных языков, грамматик и автоматов: Учебное пособие. Улан-Удэ: Изд-во ВСГТУ, 2000. - с.
В учебном пособии рассмотрены основные понятия теории алгоритмов, формальных языков, грамматик и автоматов; рассмотрены формальные модели алгоритмов, дается классификация формальных грамматик, описаны используемые в практике программирования алгоритмы преобразования грамматик и синтеза автоматов. По каждому разделу приведен теоретический материал, даны методические рекомендации и примеры решения задач, а также задания для самостоятельной работы.
Рецензенты:
Найханова Л.В. - к.т.н., доцент, заведующий кафедрой систем информатики ВСГТУ.
Дармаев Т.Г. – к.ф.-м. н., заведующий лабораторией геоинформационных технологий БИП СО РАН.
Печатается по решению редакционно-издательского совета Восточно-Сибирского государственного технологического университета
Восточно-Сибирский государственный технологический университет, 2000 г.
ВВЕДЕНИЕ
В пособии рассмотрены основные понятия теории алгоритмов и теории формальных грамматик, языков и автоматов. Пособие ориентировано на студентов младших курсов, обучающихся по специальности 220400 - "Программное обеспечение вычислительной техники и автоматизированных систем". В процессе изучения одноименных дисциплин студенты сталкиваются с тем, что учебный материал разбросан по разным источникам, написан языком труднопонимаемым для первого знакомства, а для многих понятий существует множество терминов. Поэтому при работе над пособием автор старался совместить строгость изложения основных понятий с доходчивостью восприятия.
Теоретический материал по каждому разделу сопровождается методикой решения задач, примерами, а также приводятся задания для самостоятельной работы. При написании учебного пособия широко использовались книги и монографии, указанные в списке литературы, без специальных ссылок на них в тексте пособия.
Пособие содержит введение, пять разделов и заключение. В первом разделе рассмотрены основные понятия теории алгоритмов и необходимость математического определения алгоритма. Во втором разделе рассмотрены рекурсивные функции, приводится понятие простейших функций и приемы построения сложных арифметических функций с помощью операций суперпозиции, примитивной рекурсии и минимизации. В третьем разделе дано описание машин Тьюринга, рассмотрены способы их представления, операции над машинами Тьюринга, рассмотрены алгоритмически неразрешимые проблемы теории алгоритмов. В четвертом разделе рассмотрены основные понятия формальных грамматик и языков, приводится классификация грамматик, стратегии грамматического разбора, а также эквивалентные преобразования КС-грамматик. В пятом разделе рассмотрены различные типы автоматов (конечные автоматы, автоматы с магазинной памятью, автоматы Мили и Мура) и их связь с грамматиками и языками.
Автор считает своим долгом выразить признательность Бриковой М., Жаргалову Б., Крюкову Е., которые выполнили компьютерный набор первоначального варианта текста пособия, оказали помощь при подборе заданий для самостоятельной работы.
Все замечания и пожелания по пособию автор просит направлять по адресу: 670013, г.Улан-Удэ, ул. Ключевская, 40-а, ВСГТУ.
1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АЛГОРИТМОВ
1.1. Предварительные сведения
Понятие алгоритма, являющееся одним из основных понятий математики, возникло задолго до появления вычислительных машин. На протяжении многих веков люди пользовались интуитивным понятием алгоритма. Арабский математик IX века Мухаммед ибн Муса Аль-Хорезми впервые выдвинул идею о том, что решение любой поставленной математической и философской задачи может быть оформлено в виде последовательности механически выполняемых правил, т.е. может быть алгоритмизировано. Этого же мнения придерживались Декарт, Лейбниц, Гильберт.
Приведем интуитивное определение алгоритма.
Алгоритм - это строгая и четкая конечная система правил решения некоторого класса задач, определяющая процесс преобразования исходных данных в искомый результат.
В рамках данного определения понятие алгоритма отождествлялось с понятием метода вычисления, традиции организации вычислений складывались веками и стали составной частью общей научной культуры, формулировались и успешно применялись на практике различные вычислительные алгоритмы. Поэтому понятие метода вычислений считалось изначально ясным и потребности в изучении самого этого понятия не возникало.
1.2. Основные требования к алгоритмам
Каждый алгоритм имеет дело с данными - входными, промежуточными и выходными. Данные как объекты, с которыми могут работать алгоритмы, должны быть четко определены и отличимы как друг от друга, так и от другой информации.
Данные для своего размещения требуют памяти. Память обычно считается однородной и дискретной. Единицы измерения объема данных и памяти согласованы, при этом память может быть бесконечной.
Если выполнение алгоритма заканчивается получением результатов, то говорят, что он применим к рассматриваемой совокупности исходных данных. Любой применимый алгоритм имеет следующие основные свойства, раскрывающие его определение.
1. Дискретность. Это свойство состоит в том, что алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. При этом для выполнения каждого шага алгоритма требуется некоторый конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
2. Определенность (или детерминированность). Это свойство состоит в том, что каждое правило алгоритма должно быть четким и однозначным. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
3. Результативность (или конечность). Это свойство состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов.
4. Массовость. Это свойство состоит в том, что алгоритм решения задачи разрабатывается в общем виде и должен быть применим для некоторого класса задач, различающихся лишь исходными данными.
Для задания алгоритма необходимо выделить и описать следующие его элементы:
• набор объектов, составляющих совокупность данных: исходных, промежуточных и конечных;
• правило начала;
• правила непосредственной переработки информации;
• правило окончания;
• правило извлечения результатов.
Алгоритм всегда рассчитан на конкретного исполнителя. Если исполнителем является компьютер, то алгоритм должен быть записан на языке программирования.
1.3. Математическое определение алгоритма
Интуитивное определение алгоритма не позволяет рассматривать свойства алгоритмов как свойства формальных объектов. Поэтому математическое определение алгоритма необходимо по следующим причинам:
1) только при наличии формального определения алгоритма можно сделать вывод о разрешимости или неразрешимости каких-либо проблем;
2) это дает возможность для сравнения алгоритмов, предназначенных для решения одинаковых задач;
3) это дает возможность для сравнения различных проблем по сложности алгоритмов их решения.
Одна из причин расплывчатости интуитивного определения алгоритма состоит в том, что объектом алгоритма может оказаться все, что угодно. Поэтому естественно было начать с формализации понятия объекта. В вычислительных алгоритмах объектами работы являются числа, в алгоритме шахматной игры - фигуры и позиции, при алгоритмизации производственных процессов объектами служат, например, показания приборов. Однако алгоритмы оперируют не с объектами реального мира, а с изображениями этих объектов.
Поэтому алгоритмами в современной математике принято называть конструктивно задаваемые соответствия между изображениями объектов в абстрактных алфавитах. Абстрактным алфавитом называется любая конечная совокупность объектов, называемых буквами или символами данного алфавита. При этом природа этих объектов нас совершенно не интересует. Символом абстрактных алфавитов можно считать буквы алфавита какого-либо языка, цифры, любые значки и даже слова некоторого конкретного языка. Основным требованием к алфавиту является его конечность. Таким образом, можно утверждать, что алфавит - это конечное множество различных символов. Алфавит, как любое множество, задается перечислением его элементов.
Итак, объекты реального мира можно изображать словами в различных алфавитах. Это позволяет считать, что объектами работы алгоритмов могут быть только слова. Тогда можно сформулировать следующее определение.
Алгоритм есть четкая конечная система правил для преобразования слов из некоторого алфавита в слова из этого же алфавита.
Слово, к которому применяется алгоритм, называется входным. Слово, вырабатываемое в результате применения алгоритма, называется выходным.
Совокупность слов, к которым применим данный алгоритм, называется областью применимости этого алгоритма.
Формальные определения алгоритма появились в 30-х - 40-х годах XX века. Можно выделить три основных типа универсальных алгоритмических моделей, различающихся исходными эвристическими соображениями относительно того, что такое алгоритм. Первый тип связывает понятие алгоритма с наиболее традиционными понятиями математики - вычислениями и числовыми функциями. Наиболее развитая и изученная модель этого типа - рекурсивные функции - является исторически первой формализацией понятия алгоритма. Эта модель основана на функциональном подходе и рассматривает понятие алгоритма с точки зрения того, что можно вычислить с его помощью.
Второй тип основан на представлении алгоритма как некоторого детерминированного устройства, способного выполнять в каждый отдельный момент некоторые примитивные операции, или инструкции. Такое представление не оставляет сомнений в однозначности алгоритма и элементарности его шагов. Основной теоретической моделью этого типа, созданной в 30-х годах, является машина Тьюринга, которая представляет собой автоматную модель, в основе которой лежит анализ процесса выполнения алгоритма как совокупности набора инструкций.
Третий тип алгоритмических моделей - это преобразования слов в произвольных алфавитах, в которых элементарными операциями являются подстановки, т.е. замены части слова (подслова) другим словом. Преимущество этого типа состоит в его максимальной абстрактности и возможности применить понятие алгоритма к объектам произвольной природы. Модели второго и третьего типа довольно близки и отличаются в основном эвристическими подходами. Примерами моделей этого типа являются нормальные алгоритмы Маркова и канонические системы Поста.
1.4. Понятие алфавитного оператора
Понятие алфавитного оператора является наиболее общим. К нему фактически сводятся любые процессы преобразования информации. К изучению алфавитных операторов фактически сводится теория любых преобразователей информации. Основой теории алфавитных операторов являются способы их задания. Если область определения алфавитного оператора конечна, то оператор может быть задан простой таблицей соответствия. В случае бесконечной области определения алфавитного оператора он задается системой правил, позволяющей за конечное число шагов найти выходное слово, соответствующее заданному входному слову. Алфавитные операторы, задаваемые с помощью конечной системы правил, называются алгоритмами.
Алгоритмы, в соответствии с которыми решение поставленных задач сводится к арифметическим действиям, называются численными алгоритмами.
Алгоритмы, в соответствии с которыми решение поставленных задач сводится к логическим действиям, называются логическими алгоритмами.
Различают однозначные и многозначные алфавитные операторы.
Под однозначным алфавитным оператором понимается такой алфавитный оператор, который каждому входному слову ставит в соответствие не более одного выходного слова.
Под многозначным алфавитным оператором понимается такой алфавитный оператор, который каждому входному слову ставит в соответствие более одного выходного слова.
Алфавитный оператор, не сопоставляющий данному входному слову аi никакого выходного слова bj (в том числе и пустого), не определен на этом слове.
Совокупность всех слов, на которых алфавитный оператор определен, называется областью его определения.
Два алфавитных оператора считаются равными, если равны соответствующие им алфавитные операторы и совпадает система правил, задающих действие этих алгоритмов на выходные слова.
Два алгоритма считаются эквивалентными, если у них совпадают алфавитные операторы, но не совпадают способы их задания (система правил). Обычно в теории алгоритмов рассматриваются лишь такие алгоритмы, которым соответствуют однозначные алфавитные операторы.
1.5. Задания для самостоятельной работы
Во всех заданиях необходимо разработать схемы алгоритмов и проанализировать процесс реализации алгоритма, т.е. последовательность шагов, которая будет порождена при применении алгоритма к конкретным исходным данным.
(Для ознайомлення з повним текстом статті необхідно залогінитись)