6.3.1 Общие понятия
Формальные системы приобретают все большее значение при проектировании, реализации и изучении языков программирования. Формальные системы используются для описания синтаксиса языка программирования. Такое описание играет важную роль как для пользователя, так и для создателя компиляторов. Пользователь нуждается в ясном описании языка. Создатель компилятора сталкивается с проблемами мобильности и сопровождения. Если один и тот же язык должен быть реализован на различных машинах, то допустимые строки языка должны быть так определены, чтобы их представление на пользовательском уровне было инвариантным (насколько это возможно).
Формальные системы используются для синтаксически-ориен-тированной компиляции (COK). СОК используют базу данных, содержащую синтаксические правила исходного языка, для проведения грамматического разбора.
Поскольку число языков программирования и вычислительных машин постоянно растет, возрастает и необходимость в автоматизации процесса создания компиляторов. Для этого требуется формальное описание как исходного языка, так и выходного. Аналогичной проблемой является проблема генерирования тестовых программ для проверки языкового процессора. Это может быть весьма полезным при проверке программного обеспечения, поскольку машина может выполнить более скурпулезную проверку, чем человек.
Формальные системы используются для изучения сложности языков программирования и компиляторов. Создатели и языка и компилятора хотят знать, какие свойства языка наиболее существенным образом увеличивают в компиляторе сложность фазы распознавания. Создатель компилятора, кроме того, хочет иметь некоторую основу для оценки производительности компилятора.
Формальные системы используются при попытках доказательства эквивалентности и правильности программ. Формальные системы создают почву для анализа и сравнения различных языков. Они помогают ответить на такие вопросы: что является базовыми элементами языка, какие конструкции допустимы в языке, как можно комбинировать элементы языка для построения новых конструкций, какие классы задач могут быть запрограммированы на этом языке, какова стоимость и трудность написания программ.
Язык можно представить как некоторое множество предложений или формул – строк символов – с корректно определенной структурой и, обычно, со значением. Правила определяющие допустимые конструкции языка, составляют его синтаксис.
Если бы все языки состояли из конечного числа допустимых предложений или формул, проблема описания синтаксиса не стояла бы: достаточно было бы просто перечислить все допустимые предложения – строка символов являлась бы предложением языка только в том случае, если бы она попадала в список допустимых.
Однако в этом нет необходимости, если любой элемент списка может быть сгенерирован, когда это необходимо, даже если генерация всех предложений является процессом бесконечным. Если существует алгоритм, который будет последовательно порождать правильные строки, любая строка будет отнесена к языку, если только она когда-либо появляется в генерируемом описании. Такой алгоритм называется порождающим описанием языка.
Для описания языка можно использовать и другой тип алгоритма: в этом случае проверяемая строка выступает в виде исходных данных в разрешающем алгоритме. После необходимых вычислений вырабатывается ответ "да, строка правильная" или "нет, строка неправильная".
Такое определение языка называется аналитическим. Язык с аналити-ческим описанием разрешим, если анализатор для каждой входной строки завершает свою работу за конечное число шагов.
Естественный язык не подходит для формального описания из-за его неопределенности. Компьютер не воспримет программу написанную на не до конца формализованном языке.
Самым элементарным объектом является символ. Символы соединяются друг с другом в строки, которые могут принадлежать языку или нет.
Алфавит Т – есть конечное множество символов. Строка – конкатенация символов. Обозначим Т* – класс всех возможных конечных строк алфавита Т. – нулевая или пустая строка. Обычно из всех возможных строк только вполне определенные являются правильными формулами языка.
Язык L есть подмножество множества конечных строк в алфавите Т
L Ì T*.
- Дискретная математика
- 6.050102 “Компьютерная инженерия” содержание
- 1 Теория множеств 7
- 2 Математическая логика 15
- 3 Формальные теории 35
- 4 Теория графов 47
- 5 Элементы теории чисел 80
- 6 Теория алгоритмов 121
- Введение
- 1 Теория множеств
- 1.1 Множества и подмножества
- 1.1.1 Элементы множества
- 1.2 Аксиомы теории множеств
- 1.3 Способы задания множеств
- 1.4 Операции над множествами
- 1.5 Элементы алгебры множеств
- 1.5.1 Определение алгебры множеств
- 1.5.2 Основные законы алгебры множеств
- 1.5.3 Принцип двойственности
- 2 Математическая логика
- 2.1 Функции алгебры логики (булевые функции)
- 2.1.1 Способы задания булевых функций
- 2.1.2 Логические функции одной переменной
- 2.1.3 Логические функции двух переменных
- 2.2.6 Функционально полные системы булевых функций
- 2.3 Алгебра буля
- 2.3.1 Определение алгебры. Теорема Стоуна
- 2.3.2 Законы алгебры логики
- 2.3.3 Разложения функций по переменным
- 2.3.4 Приведение логических функций
- 2.3.5 Импликанты и имплициенты булевых функций
- 2.3.6 Методы минимизации логических функций
- 2.4 Алгебра жегалкина
- 2.4.1 Преобразование функций в алгебре Жегалкина
- 2.4.2 Переход от булевой алгебры к алгебре Жегалкина
- 3 Формальные теории
- 3.1 Основные принципы построения формальных теорий исчисления
- 3.2 Определение исчисления высказываний
- 3.2.1 Метатеоремы исчисления высказываний
- 3.2.2 Схемы исчисления высказываний
- 3.3 Исчисление предикатов
- 3.3.1 Определение формальной теории pl
- 3.3.2 Принцип резолюции в исчислении предикатов
- 3.3.3 Схемы доказательств в исчислении предикатов
- 4 Теория графов
- 4.1 История теории графов
- 4.2 Основные определения
- 4.3 Способы представления графов
- 4.3.1 Матрицей смежности
- 4.3.2 Матрицей инцидентности
- 4.4 Пути в графах
- 4.4.1 Задача о кратчайшем пути
- 4.4.2 Алгоритм Дейкстры нахождения кратчайшего пути в графе
- 4.5 Транспортные сети
- 4.5.1 Потоки в транспортных сетях
- 4.5.2 Задача нахождения наибольшего потока в транспортной сети
- 4.5.3 Алгоритм Форда и Фалкерсона нахождения максимального потока транспортной сети
- 4.5.4 Транспортная задача
- 4.6 Обходы в графах
- 4.6.1 Эйлеровы графы
- 4.6.2 Алгоритм Флёри нахождения эйлерова цикла
- 4. Если получился цикл, но не ейлеров, то отбрасываем данную последнюю вершину и повторяем пункт 2.
- 4.6.3 Гамильтоновы циклы
- 4.6.4 Метод ветвей и границ.
- 4.6.5 Метод ветвей и границ в задаче о коммивояжёре
- 4.7 Деревья
- 4.7.1 Построение экономического дерева
- 4.7.2 Алгоритм Краскала
- 5 Элементы теории чисел
- 5.1 Модулярная арифметика
- 5.1.1 Алгоритм Евклида для нахождения наибольшего общего делителя
- 5.1.2 Вычисление обратных величин
- 5.1.3 Основные способы нахождения обратных величин
- 5.1.4 Китайская теорема об остатках
- 5.2 Кодирование
- 5.2.1 Оптимальное кодирование
- 5.3 Обнаружение и исправление ошибок
- 5.3.1 Общие понятия
- 5.3.2 Линейные групповые коды
- 5.3.2 Код Хэмминга
- 5.3.3 Циклические коды
- 5.3.4 Построение и декодирование конкретных циклических кодов
- 5.4 Сжатие информации
- 5.4.1 Исключение повторения строк в последующих строках
- 5.4.2 Алгоритм lzw
- 6 Теория алгоритмов
- 6.1. Основные понятия
- 6.1.1 Основные требования к алгоритмам
- 6.1.2 Блок–схемы алгоритмов
- 6.1.3 Представление данных
- 6.1.4 Виды алгоритмов
- 6.1.5 Правильность программ
- 6.1.6 Эффективность алгоритмов
- 6.1.7 Сходимость, сложность, надежность
- 6.2 Универсальные алгоритмы
- 6.2.1 Основные понятия
- 6.2.2 Машины Тьюринга
- 6.2.3 Рекурсивные функции
- 6.2.5 Тезис Черча-Тьюринга
- 6.2.6 Проблема самоприменимости
- 6.3 Языки и грамматики
- 6.3.1 Общие понятия
- 6.3.2 Формальные грамматики
- 6.3.3 Иерархия языков
- 6.4 Параллельные вычисления
- Рекомендованная литература