|
Упражнение 2.1.25 |
Математическая теория формальных языков: Информация
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 33 студентам
Уровень:
Профессионал
Длительность:
20:40:00
Студентов:
2513
Выпускников:
1028
Качество курса:
4.56 | 4.26
Курс посвящён классическому разделу математической лингвистики и теоретической информатики - теории формальных языков. Рассматриваются порождающие грамматики, регулярные выражения, конечные автоматы, автоматы с магазинной памятью.
Затронуты следующие классические темы математических основ информатики: праволинейные грамматики, конечные автоматы, регулярные выражения, контекстно-свободные грамматики, деревья разбора, нормальные формы грамматик, автоматы с магазинной памятью, детерминированные контекстно-свободные языки, синтаксический анализ, контекстные грамматики, линейно ограниченные автоматы, порождающие грамматики без ограничений, машины Тьюринга, алгоритмические проблемы, связанные с грамматиками и автоматами.
Особое внимание уделено практическим способам выяснения, к какому классу в иерархии Хомского принадлежит заданный язык, методам преобразования регулярных выражений и автоматов в грамматики соответствующего класса и наоборот, а также доказательству неразрешимости проблем, связанных с контекстно-свободными грамматиками.
Специальности: Математик
ISBN: 978-5-9556-0062-8
Теги: beta, finite, grammar, xml, автоматы, анализ, булева формула, дерево вывода, контекстно-свободная грамматика, контекстно-свободный язык, метка перехода, моноид, нетерминальный символ, протоколы, регулярные выражения, теория, шаг индукции, элементы
План занятий
Занятие
Заголовок <<
Дата изучения
Лекция 2
1 час 7 минут
Слова, языки и грамматики
В данной лекции определяются такие основные понятия, как алфавит, слово, язык над данным алфавитом - и вводятся обозначения для пустого слова, конкатенации слов, степени слова, длины слова, количества вхождений данного символа. Приведены практические примеры и упражнения для закрепления материала
Оглавление
-
Лекция 3
1 час 4 минуты
Конечные автоматы
В данной лекции рассматриваются два наиболее распространенных способа конечного задания формального языка: грамматики и автоматы. Рассматриваются конечные автоматы, соответствующие в иерархии Хомского праволинейным грамматикам, определяются понятия конечного автомата, недетерминированного конечного автомата и распознаваемого конечным автоматом языка. Приведены практические примеры и упражнения для закрепления материала
Оглавление
-
Лекция 4
35 минут
Основные свойства автоматных языков
В данной лекции доказываются свойства замкнутости класса всех автоматных языков относительно итерации, конкатенации, объединения, дополнения и пересечения, доказывается так называемая лемма о разрастании, которая во многих случаях позволяет установить неавтоматность формального языка. Приведены практические примеры и предоставлены упражнения для самостоятельного решения
Оглавление
-
Лекция 5
22 минуты
Дополнительные свойства автоматных языков
В данной лекции доказывается замкнутость класса всех автоматных языков относительно взятия гомоморфного образа и относительно взятия полного гомоморфного прообраза, определяются понятия побуквенного гомоморфизма и локального языка. Приведены практические примеры и предоставлены упражнения для самостоятельного решения
Оглавление
-
Лекция 6
36 минут
Регулярные выражения
В данной лекции рассматривается наиболее удобный и компактный способ конечного описания формального языка - регулярные выражения, - который находит практическое применение во многих компьютерных приложениях, таких как текстовые редакторы, интерпретаторы командной строки и автоматические генераторы лексических анализаторов. Приведены практические примеры и предоставлены упражнения для самостоятельного решения
Оглавление
-
Лекция 7
55 минут
Синтаксические моноиды
В данной лекции рассматривается понятие синтаксического моноида и приводится доказательство еще одного критерия автоматности формального языка, который можно сформулировать в терминах классов эквивалентности слов по взаимозаменяемости. Приведены примеры практической реализации критерия и предоставлены упражнения для самостоятельного решения
Оглавление
-
Лекция 8
30 минут
Неоднозначность в контекстно-свободных грамматиках
В данной лекции рассматривается класс контекстно-свободных языков, которые находят применение в разнообразных программных продуктах, таких как компиляторы, средства форматирования исходного кода, средства статического анализа программ, синтаксические редакторы, системы верстки, программы просмотра форматированного текста, поисковые системы. Приведены практические примеры и упражнения для самостоятельного решения
Оглавление
-
Лекция 9
43 минуты
Нормальные формы контекстно-свободных грамматик
В данной лекции рассматривается доказательство того, что каждая контекстно-свободная грамматика эквивалентна некоторой контекстно-свободной грамматике специального вида, а именно грамматике в нормальной форме Хомского. Этот факт используется в доказательствах многих теорем о контекстно-свободных языках и является очень важным. Приведены также практические примеры и самостоятельные упражнения
Оглавление
-
Лекция 10
1 час 2 минуты
Основные свойства контекстно-свободных языков
В данной лекции рассматриваются основные свойства контекстно-свободных языков, приведены некоторые теоремы для класса линейных языков, а также доказательство того, что пересечение контекстно-свободного языка с автоматным языком является контекстно-свободным. Также приводятся практические примеры и упражнения для самостоятельной проработки
Оглавление
-
Лекция 11
58 минут
Автоматы с магазинной памятью
В данной лекции рассматриваются автоматы с магазинной памятью, в которых помимо ограниченной памяти, хранящей текущее состояние, имеется потенциально бесконечная память, используемая как магазин. Даются необходимые определения, и доказывается, что автоматы с магазинной памятью распознают в точности контекстно-свободные языки. Приведены примеры практического использования автоматов с магазинной памятью и приведены упражнения для самостоятельной проработки
Оглавление
-
Лекция 12
41 минута
Дополнительные свойства контекстно-свободных языков
В данной лекции рассматриваются свойства контекстно-свободных языков, которые удобно доказывать с привлечением автоматов с магазинной памятью, а также формулируются два критерия контекстной свободности, интересных в основном с теоретической точки зрения. Приведены практические примеры и упражнения для самостоятельного решения
Оглавление
-
Лекция 13
36 минут
Детерминированные контекстно-свободные языки
В данной лекции рассматриваются детерминированные контекстно-свободные языки. Формулируется ряд свойств этого класса языков, рассматривается важность детерминированных контекстно-свободных языков для теоретической информатики, которая заключается в том, что для каждого такого языка можно указать быстрый алгоритм, распознающий принадлежность слова этому языку. Приведены практические примеры и упражнения для самостоятельного решения
Оглавление
-
Лекция 14
1 час 30 минут
Синтаксический разбор
В данной лекции рассматриваются формальные определения, связанные с прямыми синтаксическими анализаторами, определяется понятие синтаксического разбора и связанные с ним специфические определения. Приведены практические примеры и упражнения для самостоятельной проработки
Оглавление
-
Лекция 15
1 час 7 минут
Алгоритмические проблемы
В данной лекции рассматриваются понятия вычислимости, разрешимости, перечислимости и универсальных моделей вычислений. Рассмотрены алгоритмические проблемы, связанные с контекстно-свободными грамматиками, вводятся термины "массовая задача", "индивидуальная задача", "схема кодирования", "задача распознавания", "алгоритмическая проблема". Приведены практические примеры и задачи для самостоятельной проработки
Оглавление
-
Лекция 16
39 минут
Алгоритмически разрешимые проблемы
В данной лекции рассматриваются наиболее известные разрешимые проблемы, связанные с грамматиками, автоматами и регулярными выражениями. Сформулированы также теоремы о разрешимости для некоторых алгоритмических проблем. Приведены практические примеры и упражнения для самостоятельного решения
Оглавление
-
Лекция 17
54 минуты
Алгоритмически неразрешимые проблемы
В данной лекции рассматриваются оказавшиеся неразрешимыми алгоритмические проблемы, связанные с контекстно-свободными языками. Доказывается неразрешимость проблем пустоты пересечения, бесконечности пересечения, однозначности, равенства, автоматности, контекстной свободности дополнения и пересечения контекстно-свободного языка. Доказательства приведены на практических примерах, а также приведены упражнения для самостоятельной проработки
Оглавление
-