Теория формальных языков: Вводный курс.
Год издания: 1988
Автор: Рейуорд-Смит В. Дж.
Переводчик: Неизвестен
Жанр или тематика: Учебное пособие
Издательство: M.: Радио и связь
ISBN: 5-256-00159-0
Язык: Русский
Формат: PDF/DjVu
Качество: Отсканированные страницы + слой распознанного текста
Интерактивное оглавление: Да
Количество страниц: 131
Тираж: 30 000 экз.
Описание:
В книге автора из Великобритании изложены основы теории формальных языков. Использован математический аппарат теории множеств, теории графов и математической логики. Все сведения, необходимыедля понимания рассмотренных в книге вопросов, приведены в соответствующих главах. Удачно подобранные упражнения в конце каждой главы не только поясняют, но и дополняют основной материал книги.
Для разработчиков программного обеспечения ЭВМ.
Примечание
OCR включает в себя весь текст и, частично, формулы. В указанных границах текст вычитан.
Оглавление
Предисловие редактора перевода 5
Предисловие 6
Введение 8
Глава 1. Математическое предисловие 12
Множества 12
Мощность и счетность множества 15
Произведения множеств 17
Графы и деревья 20
Строки 22
Упражнения 24
Глава 2. Введение в грамматики 25
Контекстная грамматика 27
Контекстно свободные грамматики 30
Грамматический раэбор арифметических выражений 33
Пустая строка в определении контекстно свободной грамматики 35
Упражнения 37
Глава 3. Регулярные языки, I 39
Регулярные грамматики 40
Конечный автомат 43
Конечный автомат с ε-переходами 51
Упражнения 53
Глава 4. Регулярные языки, II 54
Регулярные выражения 54
Минимизация 57
Алгоритмы определения регулярности грамматики 62
Упражнения 63
Глава 5. Контекстно свободные языки 64
Нормальная форма Хомского 66
Нормальная форма Грейбаха 71
Контекстно свободный язык как решение уравнения 76
Упражнения 78
Глава 6. Магазинный автомат 79
Недетерминированный магазинный автомат 80
Недетерминированные магазинные автоматы и контекстно свободные языки 84
Детерминированные магазинные автоматы 88
Упраженения 93
Глава 7. Синтаксический анализ "сверху вниз" 94
LL(k)-грамматики 96
Рекурсивный спуск 103
Упражнения 109
Глава 8. Синтаксический разбор "снизу вверх" 110
Грамматика простого предшествования 112
LR(0)-грамматики 115
LR(1)-грамматики 123
Теоретические рассуждения 127
Упражнения 127
