Читать онлайн «Задачник по курсу "Математическая лингвистика и теория автоматов": учебное пособие для вузов»

Министерство образования и науки Российской Федерации Национальный исследовательский ядерный университет «МИФИ» М. А. Короткова, Е. Е. Трифонова Задачник по курсу «МАТЕМАТИЧЕСКАЯ ЛИНГВИСТИКА И ТЕОРИЯ АВТОМАТОВ» Рекомендовано УМО «Ядерные физика и технологии» в качестве учебного пособия для студентов высших учебных заведений Москва 2012 УДК 519. 713(075)+ 519. 76(075) ББК 22. 18я7 К 68 Короткова М. А. , Трифонова Е. Е. Задачник по курсу «Ма- тематическая лингвистика и теория автоматов». Учебное пособие. М. : НИЯУ МИФИ, 2012. 92 с. В пособие включены задачи по лингвистике, теории автоматов и кодированию. Задачи разделены по темам, каждый раздел содержит крат- кое изложение базовой теории. Для ряда задач даны ответы или указания. Данное пособие предназначено для студентов факультета кибер- нетики и информационной безопасности, изучающих математическую лингвистику и теорию автоматов, и может быть также рекомендовано всем интересующимся математической лингвистикой и теорией автома- тов. Пособие подготовлено в рамках Программы создания и развития НИЯУ МИФИ. Рецензент: канд. физ. -мат. наук А. Д. Яшунский ISBN 978-5-7262-1702-4 © Национальный исследовательский ядерный университет «МИФИ», 2012  Содержание Предисловие ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 4 Задачи ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 5 Тема 1. Языки, способы задания, операции над языками ... ... ... ... ... ... ... . . 5 Тема 2. Порождающие грамматики ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 10 Тема 3. А‐грамматики, конечные автоматы ... ... ... ... ... ... ... ... ... ... ... ... ... 15 Тема 4. Бекусовы (бекусовские) нормальные формы... ... ... ... ... ... ... ... ... . . 29 Тема 5. Структура цепочек. СУ‐схемы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 34 Тема 6. Эквивалентные преобразования КС‐грамматик ... ... ... ... ... ... ... . 41 Тема 7. LL(k), строго LL(k)‐грамматики ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 46 Тема 8. Грамматики простого предшествования (ГПП), восходящий анализ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 51 Тема 9. Конечные автоматы Мили и Мура ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 54 Тема 10. Элементы теории кодирования ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 64 Ответы и указания ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 71 Тема 1. Языки, способы задания, операции над языками ... ... ... ... ... ... ... 71 Тема 2. Порождающие грамматики ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 71 Тема 3. А‐грамматики, конечные автоматы ... ... ... ... ... ... ... ... ... ... ... ... ... 73 Тема 4. Бекусовы (бекусовские) нормальные формы... ... ... ... ... ... ... ... ... . . 78 Тема 5.