Компьютерные науки
Математика и логика

Математическая теория формальных языков

Программа посвящена классическим разделам математической лингвистики и теоретической информатики, включая теорию формальных языков и грамматик.
Студентов 2922 Выпускников 1038 Для специалистов
690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
Темы:
Алгоритмы и сложность, Математика
Объем
36 час.
Длительность
30 дней
Нагрузка в неделю
9 час.
Формат обучения
Дистанционно (самостоятельно)
Описание В учебной программе изучаются порождающие грамматики, регулярные выражения, конечные автоматы и автоматы с магазинной памятью. Учебная программа рассматривает классические темы основ информатики, такие как деревья разбора, нормальные формы грамматик и синтаксический анализ. Обучение строится на разборе свойств автоматных и контекстно-свободных языков и решении алгоритмических проблем.
Цели
  • Познакомить с классическими разделами математической лингвистики
  • Сформировать навыки работы с формальными языками и грамматиками
  • Раскрыть методы преобразования регулярных выражений и конечных автоматов
Чему я научусь?
  • Определять классы языков в иерархии Хомского
  • Преобразовывать регулярные выражения в грамматики и наоборот
  • Анализировать синтаксис и доказывать неразрешимость проблем

Авторы

Пентус Анна Евгеньевна
Пентус Анна Евгеньевна
Кандидат физико-математических наук, сотрудник Центра новых информационных технологий МГУ и лаборатории вычислительных методов кафедры вычислительной математики механико-математического факультета МГУ.
Пентус Мати Рейнович
Пентус Мати Рейнович
Доктор физико-математических наук, профессор кафедры математической логики и теории алгоритмов механико-математического факультета МГУ.
Чему я научусь?
  • Определять классы языков в иерархии Хомского
  • Преобразовывать регулярные выражения в грамматики и наоборот
  • Анализировать синтаксис и доказывать неразрешимость проблем

Учебный план

№ Занятия
Экзамен экстерном Внимание! Экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите подтвердить свои знания по данному курсу без его изучения или поверить свои знания по нему. Экзамен экстерном можно сдать только один раз. 90 мин
1 Предисловие
2 Слова, языки и грамматики В данной лекции определяются такие основные понятия, как алфавит, слово, язык над данным алфавитом - и... В данной лекции определяются такие основные понятия, как алфавит, слово, язык над данным алфавитом - и вводятся обозначения для пустого слова, конкатенации слов, степени слова, длины слова, количества вхождений данного символа. Приведены практические примеры и упражнения для закрепления материала ещё
Слова, языки и грамматики тест для курса Математическая теория формальных языков 45 мин
3 Конечные автоматы В данной лекции рассматриваются два наиболее распространенных способа конечного задания формального языка: грамматики и автоматы. Рассматриваются... В данной лекции рассматриваются два наиболее распространенных способа конечного задания формального языка: грамматики и автоматы. Рассматриваются конечные автоматы, соответствующие в иерархии Хомского праволинейным грамматикам, определяются понятия конечного автомата, недетерминированного конечного автомата и распознаваемого конечным автоматом языка. Приведены практические примеры и упражнения для закрепления материала ещё
Конечные автоматы тест для курса Математическая теория формальных языков 45 мин
4 Основные свойства автоматных языков В данной лекции доказываются свойства замкнутости класса всех автоматных языков относительно итерации, конкатенации, объединения, дополнения и... В данной лекции доказываются свойства замкнутости класса всех автоматных языков относительно итерации, конкатенации, объединения, дополнения и пересечения, доказывается так называемая лемма о разрастании, которая во многих случаях позволяет установить неавтоматность формального языка. Приведены практические примеры и предоставлены упражнения для самостоятельного решения ещё
Основные свойства автоматных языков тест для курса Математическая теория формальных языков 45 мин
5 Дополнительные свойства автоматных языков В данной лекции доказывается замкнутость класса всех автоматных языков относительно взятия гомоморфного образа и относительно взятия... В данной лекции доказывается замкнутость класса всех автоматных языков относительно взятия гомоморфного образа и относительно взятия полного гомоморфного прообраза, определяются понятия побуквенного гомоморфизма и локального языка. Приведены практические примеры и предоставлены упражнения для самостоятельного решения ещё
Дополнительные свойства автоматных языков тест для курса Математическая теория формальных языков 45 мин
6 Регулярные выражения В данной лекции рассматривается наиболее удобный и компактный способ конечного описания формального языка - регулярные выражения,... В данной лекции рассматривается наиболее удобный и компактный способ конечного описания формального языка - регулярные выражения, - который находит практическое применение во многих компьютерных приложениях, таких как текстовые редакторы, интерпретаторы командной строки и автоматические генераторы лексических анализаторов. Приведены практические примеры и предоставлены упражнения для самостоятельного решения ещё
Регулярные выражения тест для курса Математическая теория формальных языков 45 мин
7 Синтаксические моноиды В данной лекции рассматривается понятие синтаксического моноида и приводится доказательство еще одного критерия автоматности формального языка,... В данной лекции рассматривается понятие синтаксического моноида и приводится доказательство еще одного критерия автоматности формального языка, который можно сформулировать в терминах классов эквивалентности слов по взаимозаменяемости. Приведены примеры практической реализации критерия и предоставлены упражнения для самостоятельного решения ещё
Синтаксические моноиды тест для курса Математическая теория формальных языков 45 мин
8 Неоднозначность в контекстно-свободных грамматиках В данной лекции рассматривается класс контекстно-свободных языков, которые находят применение в разнообразных программных продуктах, таких как... В данной лекции рассматривается класс контекстно-свободных языков, которые находят применение в разнообразных программных продуктах, таких как компиляторы, средства форматирования исходного кода, средства статического анализа программ, синтаксические редакторы, системы верстки, программы просмотра форматированного текста, поисковые системы. Приведены практические примеры и упражнения для самостоятельного решения ещё
Неоднозначность в контекстно-свободных грамматиках тест для курса Математическая теория формальных языков 45 мин
9 Нормальные формы контекстно-свободных грамматик В данной лекции рассматривается доказательство того, что каждая контекстно-свободная грамматика эквивалентна некоторой контекстно-свободной грамматике специального вида,... В данной лекции рассматривается доказательство того, что каждая контекстно-свободная грамматика эквивалентна некоторой контекстно-свободной грамматике специального вида, а именно грамматике в нормальной форме Хомского. Этот факт используется в доказательствах многих теорем о контекстно-свободных языках и является очень важным. Приведены также практические примеры и самостоятельные упражнения ещё
Нормальные формы контекстно-свободных грамматик тест для курса Математическая теория формальных языков 45 мин
10 Основные свойства контекстно-свободных языков В данной лекции рассматриваются основные свойства контекстно-свободных языков, приведены некоторые теоремы для класса линейных языков, а... В данной лекции рассматриваются основные свойства контекстно-свободных языков, приведены некоторые теоремы для класса линейных языков, а также доказательство того, что пересечение контекстно-свободного языка с автоматным языком является контекстно-свободным. Также приводятся практические примеры и упражнения для самостоятельной проработки ещё
Основные свойства контекстно-свободных языков тест для курса Математическая теория формальных языков 45 мин
11 Автоматы с магазинной памятью В данной лекции рассматриваются автоматы с магазинной памятью, в которых помимо ограниченной памяти, хранящей текущее состояние,... В данной лекции рассматриваются автоматы с магазинной памятью, в которых помимо ограниченной памяти, хранящей текущее состояние, имеется потенциально бесконечная память, используемая как магазин. Даются необходимые определения, и доказывается, что автоматы с магазинной памятью распознают в точности контекстно-свободные языки. Приведены примеры практического использования автоматов с магазинной памятью и приведены упражнения для самостоятельной проработки ещё
Автоматы с магазинной памятью тест для курса Математическая теория формальных языков 45 мин
12 Дополнительные свойства контекстно-свободных языков В данной лекции рассматриваются свойства контекстно-свободных языков, которые удобно доказывать с привлечением автоматов с магазинной памятью,... В данной лекции рассматриваются свойства контекстно-свободных языков, которые удобно доказывать с привлечением автоматов с магазинной памятью, а также формулируются два критерия контекстной свободности, интересных в основном с теоретической точки зрения. Приведены практические примеры и упражнения для самостоятельного решения ещё
Дополнительные свойства контекстно-свободных языков тест для курса Математическая теория формальных языков 45 мин
13 Детерминированные контекстно-свободные языки В данной лекции рассматриваются детерминированные контекстно-свободные языки. Формулируется ряд свойств этого класса языков, рассматривается важность детерминированных... В данной лекции рассматриваются детерминированные контекстно-свободные языки. Формулируется ряд свойств этого класса языков, рассматривается важность детерминированных контекстно-свободных языков для теоретической информатики, которая заключается в том, что для каждого такого языка можно указать быстрый алгоритм, распознающий принадлежность слова этому языку. Приведены практические примеры и упражнения для самостоятельного решения ещё
Детерминированные контекстно-свободные языки тест для курса Математическая теория формальных языков 45 мин
14 Синтаксический разбор В данной лекции рассматриваются формальные определения, связанные с прямыми синтаксическими анализаторами, определяется понятие синтаксического разбора и... В данной лекции рассматриваются формальные определения, связанные с прямыми синтаксическими анализаторами, определяется понятие синтаксического разбора и связанные с ним специфические определения. Приведены практические примеры и упражнения для самостоятельной проработки ещё
Синтаксический разбор тест для курса Математическая теория формальных языков 45 мин
15 Алгоритмические проблемы "В данной лекции рассматриваются понятия вычислимости, разрешимости, перечислимости и универсальных моделей вычислений. Рассмотрены алгоритмические проблемы, связанные... "В данной лекции рассматриваются понятия вычислимости, разрешимости, перечислимости и универсальных моделей вычислений. Рассмотрены алгоритмические проблемы, связанные с контекстно-свободными грамматиками, вводятся термины ""массовая задача"", ""индивидуальная задача"", ""схема кодирования"", ""задача распознавания"", ""алгоритмическая проблема"". Приведены практические примеры и задачи для самостоятельной проработки" ещё
Алгоритмические проблемы тест для курса Математическая теория формальных языков 45 мин
16 Алгоритмически разрешимые проблемы В данной лекции рассматриваются наиболее известные разрешимые проблемы, связанные с грамматиками, автоматами и регулярными выражениями. Сформулированы... В данной лекции рассматриваются наиболее известные разрешимые проблемы, связанные с грамматиками, автоматами и регулярными выражениями. Сформулированы также теоремы о разрешимости для некоторых алгоритмических проблем. Приведены практические примеры и упражнения для самостоятельного решения ещё
Алгоритмически разрешимые проблемы тест для курса Математическая теория формальных языков 45 мин
17 Алгоритмически неразрешимые проблемы В данной лекции рассматриваются оказавшиеся неразрешимыми алгоритмические проблемы, связанные с контекстно-свободными языками. Доказывается неразрешимость проблем пустоты... В данной лекции рассматриваются оказавшиеся неразрешимыми алгоритмические проблемы, связанные с контекстно-свободными языками. Доказывается неразрешимость проблем пустоты пересечения, бесконечности пересечения, однозначности, равенства, автоматности, контекстной свободности дополнения и пересечения контекстно-свободного языка. Доказательства приведены на практических примерах, а также приведены упражнения для самостоятельной проработки ещё
Алгоритмически неразрешимые проблемы тест для курса Математическая теория формальных языков 45 мин
Тренировочный экзамен Внимание! Тренировочный экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите проверить свои знания курса перед сдачей экзамена. Тренировочный экзамен можно сдавать сколько угодно один раз. 90 мин
Экзамен 60 мин

Какой документ я получу?

Сертификат

Выдаётся автоматически после успешного завершения программы.

Удостоверение о повышении квалификации

Выдается при наличии среднего специального или высшего образования (необходимые документы).

Стоимость программы

690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
^