- •Курс лекций
- •Оглавление
- •Лекция 1 Языки и грамматики Языки
- •ГГрамматики
- •Лекция 2 Конечные автоматы Автоматы
- •Детерминированные конечные автоматы (распознаватели)
- •Языки и детерминированные конечные автоматы
- •Лекция 3 Конечные автоматы Недетерминированные конечные автоматы (распознаватели)
- •Эквивалентность дка и нка
- •Лекция 4 Конечные автоматы Минимизация конечных автоматов
- •Лекция 5 Регулярные выражения и регулярные грамматики
- •Регулярные выражения
- •Связь между регулярными выражениями и автоматными языками
- •Лекция 6 Регулярные выражения и регулярные грамматики Регулярные грамматики
- •Лекция 7 Свойства регулярных языков
- •Замкнутость класса регулярных языков
- •Алгоритмические проблемы регулярных языков
- •Лемма о расширении регулярных языков
- •Лекция 8 Контекстно-свободные языки
- •Контекстно-свободные грамматики
- •Лекция 9 Контекстно-свободные языки
- •Грамматический разбор
- •Неоднозначность грамматик и языков
- •Лекция 10 Преобразования кс‑грамматик и нормальные формы
- •Методы преобразования грамматик
- •Лекция 11 Преобразования кс‑грамматик и нормальные формы
- •Нормальные формы кс-грамматик
- •Лекция 12 Магазинные автоматы Магазинные автоматы
- •Недетерминированные магазинные автоматы
- •Лекция 13 Магазинные автоматы Магазинные автоматы и кс-языки
- •Лекция 14 Магазинные автоматы Детерминированные магазинные автоматы и детерминированные кс-языки
- •Лекция 15 Свойства контекстно-свободных языков
- •Лемма о расширении
- •Свойства замкнутости класса контекстно-свободных языков
- •Лекция 16 Свойства контекстно-свободных языков Некоторые алгоритмические проблемы для кс-языков
- •Предметный указатель
- •Формальные языки и грамматики Курс лекций
Министерство образования Российской Федерации
Курс лекций
Учебное пособие
В.А. Соколов
Формальные языки и грамматики
Рекомендовано Министерством образования России
в качестве учебного пособия для студентов университетов
по специальности 010200 «Прикладная математика»
и по направлению 510200 «Прикладная математика и информатика»
Ярославль 2003
ББК В185.2
С 59
УДК 519.682
Соколов В.А.
Формальные языки и грамматики. Курс лекций / Яросл. гос. ун-т, 2-е изд., испр. - Ярославль, 2003. -152 с.
ISBN 5-8397-0306-0
Данное пособие является вводным курсом в теорию формальных языков и грамматик. В нем представлен материал, составляющий теоретическую основу для разработки языков программирования и конструирования компиляторов и являющийся классическим элементом системы подготовки специалистов в области информатики.
Пособие предназначено для студентов университетов, обучающихся по специальности «Прикладная математика» и направлению «Прикладная математика и информатика».
Ил. 19.
Рецензенты: кафедра алгебры и математической логики Ивановского государственного университета; профессор Д.О. Бытев
ISBN 5-8397-0306-0 |
ã Ярославский государственный университет, 2003 ã В.А. Соколов, 1998, 2003 |
Оглавление
Языки и грамматики 6
Языки 6
ГГрамматики 10
Конечные автоматы 14
Автоматы 14
Детерминированные конечные автоматы (распознаватели) 17
Языки и детерминированные конечные автоматы 19
Конечные автоматы 23
Недетерминированные конечные автоматы (распознаватели) 23
Эквивалентность ДКА и НКА 27
Конечные автоматы 31
Минимизация конечных автоматов 31
Регулярные выражения и регулярные грамматики 38
Регулярные выражения 39
Связь между регулярными выражениями и автоматными языками 43
Регулярные выражения и регулярные грамматики 49
Регулярные грамматики 50
Свойства регулярных языков 56
Замкнутость класса регулярных языков 57
Алгоритмические проблемы регулярных языков 60
Лемма о расширении регулярных языков 63
Контекстно-свободные 66
языки 66
Контекстно-свободные грамматики 67
Контекстно-свободные 74
языки 74
Грамматический разбор 74
Неоднозначность грамматик и языков 79
Преобразования КС‑грамматик 83
и нормальные формы 83
Методы преобразования грамматик 84
Преобразования КС‑грамматик и нормальные формы 98
Нормальные формы КС-грамматик 98
Магазинные автоматы 104
Магазинные автоматы 104
Недетерминированные магазинные автоматы 105
Магазинные автоматы 113
Магазинные автоматы и КС-языки 113
Магазинные автоматы 123
Детерминированные магазинные автоматы и детерминированные КС-языки 124
Свойства контекстно-свободных языков 129
Лемма о расширении 129
Свойства замкнутости класса контекстно-свободных языков 133
Свойства контекстно-свободных языков 138
Некоторые алгоритмические проблемы для КС-языков 139
Предисловие
данное пособие предназначено для студентов университетов, обучающихся по специальности "Прикладная математика" и направлению "Прикладная математика и информатика". В нем представлен материал, составляющий теоретическую основу для разработки языков программирования и конструирования компиляторов и ставший уже классическим элементом системы подготовки студентов в области прикладной математики и информатики. В пособии рассматриваются детерминированные и недетерминированные конечные автоматы, регулярные и контекстно-свободные языки, регулярные выражения, формальные грамматики и выводимость в них, свойства замкнутости различных классов языков, их структурные свойства, магазинные автоматы и их связь с контекстно-свободными языками. Объем материала соответствует семестровому лекционному курсу, который автор в течение ряда лет читал на факультете информатики и вычислительной техники Ярославского государственного университета. При выборе способа подачи материала предпочтение отдавалось простым, наглядным, но строгим рассуждениям. Доказательства теорем, как правило, опираются на алгоритмические конструкции. В основу критерия отбора материала был положен принцип "минимальной достаточности", при этом имелось в виду существование изданий энциклопедического характера, таких, как двухтомная монография А. Ахо и Дж. Ульмана "Теория синтаксического анализа, перевода и компиляции" (М.: Мир, 1978), которые могут служить источником дополнительных сведений.
Цель нашего пособия – дать студентам возможность быстро войти в круг идей, понятий и основных результатов теории формальных языков и подготовиться к изучению методов разработки и трансляции языков программирования. Дополнением к данному курсу лекций может служить задачник (см.: Соколов В.А., Кушнаренко О.Б., Бадин Н.М. Формальные языки и грамматики: Задачи и упражнения. Ярославль, 1993).
Автор выражает глубокую признательность Н.С. Сидоровой и А.Н. Бадиной за большую помощь при подготовке рукописи к печати.