Министерство общего и профессионального образования Российской Федерации
Ярославский государственный университет имени П.Г. Демидова
курс
лекций
Учебное пособие
В.А. Соколов
Формальныеязыки играмматики
Рекомендовано Министерством общего и профессионального образования России в качестве учебного пособия для студентов университетов
по специальности 010200 «Прикладная математика»
и по направлению 510200 «Прикладная математика и информатика»
ЯРОСЛАВЛЬ 1998
ББК В185.2 С 59
УДК 519.682
Соколов В.А.
Формальные языки и грамматики. Курс лекций: Учеб.
пособие / Яросл. гос. ун-т. Ярославль, 1998. 152 с.
ISBN 5-8397-0025-8
Данное пособие является вводным курсом в теорию формальных языков и грамматик. В нем представлен материал, составляющий теоретическую основу для разработки языков программирования и конструирования компиляторов и являющийся классическим элементом системы подготовки специалистов в области информатики.
Пособие предназначено для студентов университетов, обучающихся по специальности «Прикладная математика» и направлению «Прикладная математика и информатика».
Ил. 19.
Рецензенты: кафедра алгебры и математической логики Ивановского государственного университета; профессор Д.О. Бытев
ISBN 5-8397-0025-8 |
Ярославский |
|
государственный |
|
университет, 1998 |
|
В.А. Соколов, 1998 |
Оглавление
Предисловие_____________________________________________ 5
Лекция 1. Языки и грамматики
Языки___________________________________________________ 7 Грамматики_____________________________________________ 11
Лекция 2. Конечные автоматы
Автоматы ______________________________________________ 15
Детерминированные конечные автоматы (распознаватели) _____ 18 Языки и детерминированные конечные автоматы_____________ 21
Лекция 3. Конечные автоматы
Недетерминированные конечные автоматы (распознаватели) ___ 24
Эквивалентность ДКА и НКА _____________________________ 28
Лекция 4. Конечные автоматы
Минимизация конечных автоматов _________________________ 32
Лекция 5. Регулярные выражения и регулярные грамматики
Регулярные выражения ___________________________________ 39
Связь между регулярными выражениями и автоматными языками __________________________________ 43
Лекция 6. Регулярные выражения и регулярные грамматики
Регулярные грамматики __________________________________ 50
Лекция 7. Свойства регулярных языков
Замкнутость класса регулярных языков _____________________ 57 Алгоритмические проблемы регулярных языков______________ 60
Оглавление |
3 |
Лемма о расширении регулярных языков ____________________ 63
Лекция 8. Контекстно-свободные языки
Контекстно-свободные грамматики_________________________ 68
Лекция 9. Контекстно-свободные языки
Грамматический разбор___________________________________ 75
Неоднозначность грамматик и языков_______________________ 80
Лекция 10. Преобразования КС-грамматик и нормальные формы
Методы преобразования грамматик_________________________ 87
Лекция 11. Преобразования КС-грамматик и нормальные формы
Нормальные формы КС-грамматик ________________________ 102
Лекция 12. Магазинные автоматы
Магазинные автоматы___________________________________ 109
Недетерминированные магазинные автоматы _______________ 110
Лекция 13. Магазинные автоматы
Магазинные автоматы и КС-языки ________________________ 118
Лекция 14. Магазинные автоматы
Детерминированные магазинные автоматы и детерминированные КС-языки __________________________ 129
Лекция 15. Свойства контекстно-свободных языков
Лемма о расширении ____________________________________ 135
Свойства замкнутости класса контекстно-свободных языков __ 139
Лекция 16. Свойства контекстно-свободных языков
Некоторые алгоритмические проблемы для КС-языков _______ 145
4 |
Оглавление |
Предисловие
Данное пособие предназначено для студентов университетов, обучающихся по специальности "Прикладная математика" и направлению "Прикладная математика и информатика". В нем
представлен материал, составляющий теоретическую основу для разработки языков программирования и конструирования компиляторов и ставший уже классическим элементом системы подготовки студентов в области прикладной математики и информатики. В пособии рассматриваются детерминированные и недетерминированные конечные автоматы, регулярные и контекстно-свободные языки, регулярные выражения, формальные грамматики и выводимость в них, свойства замкнутости различных классов языков, их структурные свойства, магазинные автоматы и их связь с контекстно-свободными языками. Объем материала соответствует семестровому лекционному курсу, который автор в течение ряда лет читал на факультете информатики и вычислительной техники Ярославского государственного университета. При выборе способа подачи материала предпочтение отдавалось простым, наглядным, но строгим рассуждениям. Доказательства теорем, как правило, опираются на алгоритмические конструкции. В основу критерия отбора материала был положен принцип "минимальной достаточности", при этом имелось в виду существование изданий энциклопедического характера, таких, как двухтомная монография А. Ахо и Дж. Ульмана "Теория синтаксического анализа, перевода и компиляции" (М.: Мир, 1978), которые могут служить источником дополнительных сведений.
Цель нашего пособия – дать студентам возможность быстро войти в круг идей, понятий и основных результатов теории формальных языков и подготовиться к изучению методов разработки и трансляции языков программирования. Дополнением к данному курсу лекций может служить задачник (см.: Соколов В.А.,
Предисловие |
5 |
Кушнаренко О.Б., Бадин Н.М. Формальные языки и грамматики: Задачи и упражнения. Ярославль, 1993).
Автор выражает глубокую признательность Н.С. Сидоровой и А.Н. Бадиной за большую помощь при подготовке рукописи к печати.
6 |
Предисловие |