Бильгаева Н.Ц. - Теория алгоритмов, формальных языков, грамматик и автоматов

Министерство образования Российской ФедерацииВосточно-Сибирский государственный технологический университетБильгаева Н.Ц.Теория алгоритмов, формальныхязыков, грамматик и автоматовУчебное пособие для студентов специальности220400 -"Программное обеспечение вычислительнойтехники и автоматизированных систем"Издательство ВСГТУУлан-Удэ 2000УДК 681.5.01:512Бильгаева Н.Ц. Теория алгоритмов, формальных языков, грамматик и автоматов: Учебноепособие.

Улан-Удэ: Изд-во ВСГТУ, 2000. - с.В учебном пособии рассмотрены основные понятия теории алгоритмов, формальных языков,грамматик и автоматов; рассмотрены формальные модели алгоритмов, дается классификацияформальныхграмматик, описаны используемые в практике программирования алгоритмыпреобразования грамматик и синтеза автоматов. По каждому разделу приведен теоретическийматериал, даны методические рекомендации и примеры решения задач, а также задания длясамостоятельной работы.Рецензенты:Найханова Л.В.

- к.т.н., доцент, заведующий кафедрой систем информатики ВСГТУ.Дармаев Т.Г. – к.ф.-м. н., заведующий лабораторией геоинформационных технологий БИП СОРАН.Печатаетсяпорешениюредакционно-издательскогогосударственного технологического университетасоветаВосточно-Сибирского Восточно-Сибирский государственный технологический университет, 2000 г.ВВЕДЕНИЕВ пособии рассмотрены основные понятия теории алгоритмов и теории формальныхграмматик, языков и автоматов. Пособие ориентировано на студентов младших курсов,обучающихся по специальности 220400 - "Программное обеспечение вычислительнойтехники и автоматизированных систем". В процессе изучения одноименных дисциплинстуденты сталкиваются с тем, что учебный материал разбросан по разным источникам,написан языком труднопонимаемым для первого знакомства, а для многих понятийсуществует множество терминов.

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

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

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

Ключевская, 40-а, ВСГТУ.1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АЛГОРИТМОВ1.1. Предварительные сведенияПонятие алгоритма, являющееся одним из основных понятий математики, возниклозадолго до появления вычислительных машин. На протяжении многих веков людипользовались интуитивным понятием алгоритма. Арабский математик IX века Мухаммедибн Муса Аль-Хорезми впервые выдвинул идею о том, что решение любой поставленнойматематической и философской задачи может быть оформлено в виде последовательностимеханически выполняемых правил, т.е. может быть алгоритмизировано. Этого же мненияпридерживались Декарт, Лейбниц, Гильберт.Приведем интуитивное определение алгоритма.Алгоритм - это строгая и четкая конечная система правил решения некоторого классазадач, определяющая процесс преобразования исходных данных в искомый результат.В рамках данного определения понятие алгоритма отождествлялось с понятием методавычисления, традиции организации вычислений складывались веками и стали составнойчастью общей научной культуры, формулировались и успешно применялись на практикеразличные вычислительные алгоритмы.

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

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

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

Определенность (или детерминированность). Это свойство состоит в том, что каждоеправило алгоритма должно быть четким и однозначным. Благодаря этому свойствувыполнение алгоритма носит механический характер и не требует никаких дополнительныхуказаний или сведений о решаемой задаче.3. Результативность (или конечность). Это свойство состоит в том, что алгоритмдолжен приводить к решению задачи за конечное число шагов.4. Массовость. Это свойство состоит в том, что алгоритм решения задачиразрабатывается в общем виде и должен быть применим для некоторого класса задач,различающихся лишь исходными данными.Для задания алгоритма необходимо выделить и описать следующие его элементы:• набор объектов, составляющих совокупность данных: исходных, промежуточных иконечных;• правило начала;• правила непосредственной переработки информации;• правило окончания;• правило извлечения результатов.Алгоритм всегда рассчитан на конкретного исполнителя.

Если исполнителем являетсякомпьютер, то алгоритм должен быть записан на языке программирования.1.3. Математическое определение алгоритмаИнтуитивное определение алгоритма не позволяет рассматривать свойстваалгоритмов как свойства формальных объектов. Поэтому математическое определениеалгоритма необходимо по следующим причинам:1) только при наличии формального определения алгоритма можно сделать вывод оразрешимости или неразрешимости каких-либо проблем;2) это дает возможность для сравнения алгоритмов, предназначенных для решенияодинаковых задач;3) это дает возможность для сравнения различных проблем по сложности алгоритмов ихрешения.Одна из причин расплывчатости интуитивного определения алгоритма состоит в том,что объектом алгоритма может оказаться все, что угодно. Поэтому естественно было начатьс формализации понятия объекта.

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

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