М.А. Короткова
МАТЕМАТИЧЕСКАЯ ТЕОРИЯ АВТОМАТОВ
Учебное пособие
Рекомендовано УМО «Ядерные физика и технологии» в качестве учебного пособия для студентов высших учебных заведений
УДК 519.713+ 519.725
ББК 22.18
К 687
Короткова М.А. Математическая теория автоматов. Учебное пособие. М.: МИФИ, 2008. – 116 с.
Рассматриваются вопросы представления детерминированных функций k-значных логик, способы задания, анализа и синтеза автоматов. Рассмотрены также базовые понятия теории кодирования, включая вопросы распознавания кодов автоматами. Пособие предназначено для студентов, обучаемых по специальности «Прикладная математика и информатика» и
изучающих курс «Математическая теория автоматов». Предлагаемое пособие будет полезно также студентам третьего курса факультета Кибернетики, изучающим математическую лингвистику и теорию автоматов. Пособие может быть рекомендовано всем интересующимся теорией автоматов.
Пособие подготовлено в рамках Инновационной образовательной программы
Рецензент канд. техн. наук, доц. Г.М. Сергиевский
ISBN 978-5-7262-1005-6
© Московский инженерно-физический институт (государственный университет), 2008
Редактор Шумакова Н.В.
Оригинал-макет изготовлен Коротковой М.А.
Подписано в печать 20.11.2008 Формат 60×84 1/16
Печ.л. 6,25 Уч.-изд.л. 6,25 Тираж 150 экз.
Изд. № 4/32 Заказ №
Московский инженерно-физический институт
(государственный университет).
115409, Москва, Каширское ш., 31
Типография издательства «Тровант».
г. Троицк Московской обл.
СодержаниеОшибка! Закладка не определена.
ПРЕДИСЛОВИЕ ................................................................................... 5
ГЛАВА 1. ДЕТЕРМИНИРОВАННЫЕ ФУНКЦИИ И СПОСОБЫ
ИХ ЗАДАНИЯ....................................................................................... 6
Функции k-значной логики. Формулы и реализация функций
формулами ............................................................................................. 6
Полнота системы функций................................................................. 12
Ограниченно-детерминированные (автоматные) функции с
операциями .......................................................................................... 12
Детерминированные функции ........................................................... 13
Задание детерминированных функций с помощью деревьев ......... 17
Вес детерминированной функции ..................................................... 20
Ограниченно-детерминированные функции и способы их задания
............................................................................................................... 23
Диаграммы для детерминированных функций ................................ 23
Вопросы и упражнения....................................................................... 25
ГЛАВА 2. ОСНОВНЫЕ ТИПЫ ПРЕОБРАЗУЮЩИХ
АВТОМАТОВ ..................................................................................... 26
Автомат Мили ..................................................................................... 26
Метод Хафмена минимизации числа состояний автомата ......... 31
Автоматы Мура ................................................................................... 34
Частичные автоматы........................................................................... 40
Вопросы и упражнения....................................................................... 44
ГЛАВА 3. СИНТЕЗ АВТОМАТОВ................................................... 45
Последовательные автоматные вычисления .................................... 45
Синхронные сети автоматов .............................................................. 47
Правильно построенные логические сети ........................................ 53
Вопросы и упражнения....................................................................... 56
ГЛАВА 4. ЯЗЫКИ И ГРАММАТИКИ ............................................. 58
Алфавит, слова, операции над словами ............................................ 58
4
Языки. Операции над языками .......................................................... 59
Регулярные множества и регулярные выражения ........................... 61
Задание языков системами уравнений .............................................. 64
Грамматики и их классификация....................................................... 67
Вопросы и упражнения....................................................................... 71
ГЛАВА 5. А-ЯЗЫКИ И КОНЕЧНЫЕ
ЛИНГВИСТИЧЕСКИЕ АВТОМАТЫ .............................................. 73
Диаграмма грамматики....................................................................... 73
Порождение и распознавание цепочек ............................................. 75
Детерминизация недетерминированных автоматов ........................ 78
Автоматы с λ-переходами .................................................................. 82
Соответствие между А-языками и регулярными............................. 85
выражениями ....................................................................................... 85
Минимизация числа состояний автомата ......................................... 92
Разрешимые проблемы для А-грамматик......................................... 97
Вопросы и упражнения....................................................................... 99
ГЛАВА 6. ЭЛЕМЕНТЫ ТЕОРИИ КОДИРОВАНИЯ.................... 100
Основные понятия теории................................................................ 101
Критерий однозначности кодирования........................................... 103
Коды с минимальной избыточностью............................................. 107
Самокорректирующиеся коды......................................................... 110
Построение автоматов, распознающих префиксные коды ........... 112
Вопросы и упражнения..................................................................... 115
СПИСОК ЛИТЕРАТУРЫ ................................................................ 116
5
Предисловие
Существуют различные традиции в изложении теории автоматов. В данном пособии сделана попытка совмещения описания математического базиса разработки автоматных моделей – k- значных логик и таких технических аспектов, как построение функций выхода и перехода при заданном кодировании состояний и сигналов.
Рассматриваются также общие вопросы кодирования сигналов в автоматах, что позволяет пояснить вопросы синтеза автоматов и объяснить принцип построения декодирующего автомата для префиксного кодирования, выявляя взаимосвязь различных аспектов рассматриваемой теории. Изложение теории сопровождается многочисленными иллюстрациями и примерами.
Настоящее пособие предполагает, что читатель знаком с основными понятиями теории множеств и математической логики, в частности, алгебры высказываний.
Для лучшего понимания излагаемого материала в каждой главе приведены вопросы и упражнения. Значительная доля их требует только внимательного изучения текста главы или применения описанных алгоритмов, тем не менее ответы на некоторые вопросы требуют сопоставления изложенного в разных главах.
В конце пособия приводится список использованной и рекомендуемой литературы.
ГЛАВА 1. ДЕТЕРМИНИРОВАННЫЕ ФУНКЦИИ И СПОСОБЫ ИХ ЗАДАНИЯ
В данной главе рассматриваются логики, при условии, что k ≥3. Предполагается, что читатели знакомы с функциями обычной булевой логики (k=2) и их свойствами [1,2].
k- значные логики вводятся как обобщение двузначной логики. С одной стороны, для k-значных логик сохраняются некоторые важные свойства двузначных логик, также сохраняются многие
важные результаты, полученные для двузначных логик. С другой стороны, в k-значных логиках наблюдаются явления, отличающие их от двузначной логики. Последнее обстоятельство обусловливает необходимость рассмотрения этих логик в данном пособии. Рассматриваются не все особенности k-значных логик, а только те базовые свойства, знание которых необходимо для изучения остальных разделов курса.
(Для ознайомлення з повним текстом статті необхідно залогінитись)