|
Упражнение 2.1.25 |
Инспектор
Вы можете этот курс.
Опубликован: 09.07.2007 | Уровень: профессионал | Доступ: свободно | ВУЗ: Московский государственный университет имени М.В.Ломоносова
Курс посвящён классическому разделу математической лингвистики и теоретической информатики - теории формальных языков. Рассматриваются порождающие грамматики, регулярные выражения, конечные автоматы, автоматы с магазинной памятью.
Затронуты следующие классические темы математических основ информатики: праволинейные грамматики, конечные автоматы, регулярные выражения, контекстно-свободные грамматики, деревья разбора, нормальные формы грамматик, автоматы с магазинной памятью, детерминированные контекстно-свободные языки, синтаксический анализ, контекстные грамматики, линейно ограниченные автоматы, порождающие грамматики без ограничений, машины Тьюринга, алгоритмические проблемы, связанные с грамматиками и автоматами.
Особое внимание уделено практическим способам выяснения, к какому классу в иерархии Хомского принадлежит заданный язык, методам преобразования регулярных выражений и автоматов в грамматики соответствующего класса и наоборот, а также доказательству неразрешимости проблем, связанных с контекстно-свободными грамматиками.
План занятий
| Занятие | Заголовок << | Дата изучения |
|---|---|---|
| - | ||
Лекция 19 минут | ПредисловиеОглавление | - |
Лекция 21 час 7 минут | Слова, языки и грамматики
В данной лекции определяются такие основные понятия, как алфавит, слово, язык над данным алфавитом - и вводятся обозначения для пустого слова, конкатенации слов, степени слова, длины слова, количества вхождений данного символа. Приведены практические примеры и упражнения для закрепления материала
Оглавление | - |
Тест 127 минут | - | |
Лекция 31 час 4 минуты | Конечные автоматы
В данной лекции рассматриваются два наиболее распространенных способа конечного задания формального языка: грамматики и автоматы. Рассматриваются конечные автоматы, соответствующие в иерархии Хомского праволинейным грамматикам, определяются понятия конечного автомата, недетерминированного конечного автомата и распознаваемого конечным автоматом языка. Приведены практические примеры и упражнения для закрепления материала
Оглавление | - |
Тест 227 минут | - | |
Лекция 435 минут | Основные свойства автоматных языков
В данной лекции доказываются свойства замкнутости класса всех автоматных языков относительно итерации, конкатенации, объединения, дополнения и пересечения, доказывается так называемая лемма о разрастании, которая во многих случаях позволяет установить неавтоматность формального языка. Приведены практические примеры и предоставлены упражнения для самостоятельного решения
Оглавление | - |
Тест 327 минут | - | |
Лекция 522 минуты | Дополнительные свойства автоматных языков
В данной лекции доказывается замкнутость класса всех автоматных языков относительно взятия гомоморфного образа и относительно взятия полного гомоморфного прообраза, определяются понятия побуквенного гомоморфизма и локального языка. Приведены практические примеры и предоставлены упражнения для самостоятельного решения
Оглавление | - |
Тест 427 минут | - | |
Лекция 636 минут | Регулярные выражения
В данной лекции рассматривается наиболее удобный и компактный способ конечного описания формального языка - регулярные выражения, - который находит практическое применение во многих компьютерных приложениях, таких как текстовые редакторы, интерпретаторы командной строки и автоматические генераторы лексических анализаторов. Приведены практические примеры и предоставлены упражнения для самостоятельного решения
Оглавление | - |
Тест 527 минут | - | |
Лекция 755 минут | Синтаксические моноиды
В данной лекции рассматривается понятие синтаксического моноида и приводится доказательство еще одного критерия автоматности формального языка, который можно сформулировать в терминах классов эквивалентности слов по взаимозаменяемости. Приведены примеры практической реализации критерия и предоставлены упражнения для самостоятельного решения
Оглавление | - |
Тест 627 минут | - | |
Лекция 830 минут | Неоднозначность в контекстно-свободных грамматиках
В данной лекции рассматривается класс контекстно-свободных языков, которые находят применение в разнообразных программных продуктах, таких как компиляторы, средства форматирования исходного кода, средства статического анализа программ, синтаксические редакторы, системы верстки, программы просмотра форматированного текста, поисковые системы. Приведены практические примеры и упражнения для самостоятельного решения
Оглавление | - |
Тест 727 минут | - | |
Лекция 943 минуты | Нормальные формы контекстно-свободных грамматик
В данной лекции рассматривается доказательство того, что каждая контекстно-свободная грамматика эквивалентна некоторой контекстно-свободной грамматике специального вида, а именно грамматике в нормальной форме Хомского. Этот факт используется в доказательствах многих теорем о контекстно-свободных языках и является очень важным. Приведены также практические примеры и самостоятельные упражнения
Оглавление | - |
Тест 827 минут | - | |
Лекция 101 час 2 минуты | Основные свойства контекстно-свободных языков
В данной лекции рассматриваются основные свойства контекстно-свободных языков, приведены некоторые теоремы для класса линейных языков, а также доказательство того, что пересечение контекстно-свободного языка с автоматным языком является контекстно-свободным. Также приводятся практические примеры и упражнения для самостоятельной проработки
Оглавление | - |
Тест 927 минут | - | |
Лекция 1158 минут | Автоматы с магазинной памятью
В данной лекции рассматриваются автоматы с магазинной памятью, в которых помимо ограниченной памяти, хранящей текущее состояние, имеется потенциально бесконечная память, используемая как магазин. Даются необходимые определения, и доказывается, что автоматы с магазинной памятью распознают в точности контекстно-свободные языки. Приведены примеры практического использования автоматов с магазинной памятью и приведены упражнения для самостоятельной проработки
Оглавление | - |
Тест 1027 минут | - | |
Лекция 1241 минута | Дополнительные свойства контекстно-свободных языков
В данной лекции рассматриваются свойства контекстно-свободных языков, которые удобно доказывать с привлечением автоматов с магазинной памятью, а также формулируются два критерия контекстной свободности, интересных в основном с теоретической точки зрения. Приведены практические примеры и упражнения для самостоятельного решения
Оглавление | - |
Тест 1127 минут | - | |
Лекция 1336 минут | Детерминированные контекстно-свободные языки
В данной лекции рассматриваются детерминированные контекстно-свободные языки. Формулируется ряд свойств этого класса языков, рассматривается важность детерминированных контекстно-свободных языков для теоретической информатики, которая заключается в том, что для каждого такого языка можно указать быстрый алгоритм, распознающий принадлежность слова этому языку. Приведены практические примеры и упражнения для самостоятельного решения
Оглавление | - |
Тест 1227 минут | - | |
Лекция 141 час 30 минут | Синтаксический разбор
В данной лекции рассматриваются формальные определения, связанные с прямыми синтаксическими анализаторами, определяется понятие синтаксического разбора и связанные с ним специфические определения. Приведены практические примеры и упражнения для самостоятельной проработки
Оглавление | - |
Тест 1327 минут | - | |
Лекция 151 час 7 минут | Алгоритмические проблемы
В данной лекции рассматриваются понятия вычислимости, разрешимости, перечислимости и универсальных моделей вычислений. Рассмотрены алгоритмические проблемы, связанные с контекстно-свободными грамматиками, вводятся термины "массовая задача", "индивидуальная задача", "схема кодирования", "задача распознавания", "алгоритмическая проблема". Приведены практические примеры и задачи для самостоятельной проработки
Оглавление | - |
Тест 1427 минут | - | |
Лекция 1639 минут | Алгоритмически разрешимые проблемы
В данной лекции рассматриваются наиболее известные разрешимые проблемы, связанные с грамматиками, автоматами и регулярными выражениями. Сформулированы также теоремы о разрешимости для некоторых алгоритмических проблем. Приведены практические примеры и упражнения для самостоятельного решения
Оглавление | - |
Тест 1527 минут | - | |
Лекция 1754 минуты | Алгоритмически неразрешимые проблемы
В данной лекции рассматриваются оказавшиеся неразрешимыми алгоритмические проблемы, связанные с контекстно-свободными языками. Доказывается неразрешимость проблем пустоты пересечения, бесконечности пересечения, однозначности, равенства, автоматности, контекстной свободности дополнения и пересечения контекстно-свободного языка. Доказательства приведены на практических примерах, а также приведены упражнения для самостоятельной проработки
Оглавление | - |
Тест 1627 минут | - | |
5 часов | - |
