Опубликован: 09.07.2007 | Уровень: профессионал | Доступ: свободно
Математическая теория формальных языков Курс посвящён классическому разделу математической лингвистики и теоретической информатики - теории формальных языков. Рассматриваются порождающие грамматики, регулярные выражения, конечные автоматы, автоматы с магазинной памятью.
Затронуты следующие классические темы математических основ информатики: праволинейные грамматики, конечные автоматы, регулярные выражения, контекстно-свободные грамматики, деревья разбора, нормальные формы грамматик, автоматы с магазинной памятью, детерминированные контекстно-свободные языки, синтаксический анализ, контекстные грамматики, линейно ограниченные автоматы, порождающие грамматики без ограничений, машины Тьюринга, алгоритмические проблемы, связанные с грамматиками и автоматами. Особое внимание уделено практическим способам выяснения, к какому классу в иерархии Хомского принадлежит заданный язык, методам преобразования регулярных выражений и автоматов в грамматики соответствующего класса и наоборот, а также доказательству неразрешимости проблем, связанных с контекстно-свободными грамматиками.

План занятий

ЗанятиеЗаголовок <<Дата изучения
-
Лекция 1
9 минут
Предисловие
Оглавление
    -
    Лекция 2
    1 час 7 минут
    Слова, языки и грамматики
    В данной лекции определяются такие основные понятия, как алфавит, слово, язык над данным алфавитом - и вводятся обозначения для пустого слова, конкатенации слов, степени слова, длины слова, количества вхождений данного символа. Приведены практические примеры и упражнения для закрепления материала
    Оглавление
      -
      Тест 1
      27 минут
      -
      Лекция 3
      1 час 4 минуты
      Конечные автоматы
      В данной лекции рассматриваются два наиболее распространенных способа конечного задания формального языка: грамматики и автоматы. Рассматриваются конечные автоматы, соответствующие в иерархии Хомского праволинейным грамматикам, определяются понятия конечного автомата, недетерминированного конечного автомата и распознаваемого конечным автоматом языка. Приведены практические примеры и упражнения для закрепления материала
      Оглавление
        -
        Тест 2
        27 минут
        -
        Лекция 4
        35 минут
        Основные свойства автоматных языков
        В данной лекции доказываются свойства замкнутости класса всех автоматных языков относительно итерации, конкатенации, объединения, дополнения и пересечения, доказывается так называемая лемма о разрастании, которая во многих случаях позволяет установить неавтоматность формального языка. Приведены практические примеры и предоставлены упражнения для самостоятельного решения
        Оглавление
          -
          Тест 3
          27 минут
          -
          Лекция 5
          22 минуты
          Дополнительные свойства автоматных языков
          В данной лекции доказывается замкнутость класса всех автоматных языков относительно взятия гомоморфного образа и относительно взятия полного гомоморфного прообраза, определяются понятия побуквенного гомоморфизма и локального языка. Приведены практические примеры и предоставлены упражнения для самостоятельного решения
          Оглавление
            -
            Тест 4
            27 минут
            -
            Лекция 6
            36 минут
            Регулярные выражения
            В данной лекции рассматривается наиболее удобный и компактный способ конечного описания формального языка - регулярные выражения, - который находит практическое применение во многих компьютерных приложениях, таких как текстовые редакторы, интерпретаторы командной строки и автоматические генераторы лексических анализаторов. Приведены практические примеры и предоставлены упражнения для самостоятельного решения
            Оглавление
              -
              Тест 5
              27 минут
              -
              Лекция 7
              55 минут
              Синтаксические моноиды
              В данной лекции рассматривается понятие синтаксического моноида и приводится доказательство еще одного критерия автоматности формального языка, который можно сформулировать в терминах классов эквивалентности слов по взаимозаменяемости. Приведены примеры практической реализации критерия и предоставлены упражнения для самостоятельного решения
              Оглавление
                -
                Тест 6
                27 минут
                -
                Лекция 8
                30 минут
                Неоднозначность в контекстно-свободных грамматиках
                В данной лекции рассматривается класс контекстно-свободных языков, которые находят применение в разнообразных программных продуктах, таких как компиляторы, средства форматирования исходного кода, средства статического анализа программ, синтаксические редакторы, системы верстки, программы просмотра форматированного текста, поисковые системы. Приведены практические примеры и упражнения для самостоятельного решения
                Оглавление
                  -
                  Тест 7
                  27 минут
                  -
                  Лекция 9
                  43 минуты
                  Нормальные формы контекстно-свободных грамматик
                  В данной лекции рассматривается доказательство того, что каждая контекстно-свободная грамматика эквивалентна некоторой контекстно-свободной грамматике специального вида, а именно грамматике в нормальной форме Хомского. Этот факт используется в доказательствах многих теорем о контекстно-свободных языках и является очень важным. Приведены также практические примеры и самостоятельные упражнения
                  Оглавление
                    -
                    Тест 8
                    27 минут
                    -
                    Лекция 10
                    1 час 2 минуты
                    Основные свойства контекстно-свободных языков
                    В данной лекции рассматриваются основные свойства контекстно-свободных языков, приведены некоторые теоремы для класса линейных языков, а также доказательство того, что пересечение контекстно-свободного языка с автоматным языком является контекстно-свободным. Также приводятся практические примеры и упражнения для самостоятельной проработки
                    Оглавление
                      -
                      Тест 9
                      27 минут
                      -
                      Лекция 11
                      58 минут
                      Автоматы с магазинной памятью
                      В данной лекции рассматриваются автоматы с магазинной памятью, в которых помимо ограниченной памяти, хранящей текущее состояние, имеется потенциально бесконечная память, используемая как магазин. Даются необходимые определения, и доказывается, что автоматы с магазинной памятью распознают в точности контекстно-свободные языки. Приведены примеры практического использования автоматов с магазинной памятью и приведены упражнения для самостоятельной проработки
                      Оглавление
                        -
                        Тест 10
                        27 минут
                        -
                        Лекция 12
                        41 минута
                        Дополнительные свойства контекстно-свободных языков
                        В данной лекции рассматриваются свойства контекстно-свободных языков, которые удобно доказывать с привлечением автоматов с магазинной памятью, а также формулируются два критерия контекстной свободности, интересных в основном с теоретической точки зрения. Приведены практические примеры и упражнения для самостоятельного решения
                        Оглавление
                          -
                          Тест 11
                          27 минут
                          -
                          Лекция 13
                          36 минут
                          Детерминированные контекстно-свободные языки
                          В данной лекции рассматриваются детерминированные контекстно-свободные языки. Формулируется ряд свойств этого класса языков, рассматривается важность детерминированных контекстно-свободных языков для теоретической информатики, которая заключается в том, что для каждого такого языка можно указать быстрый алгоритм, распознающий принадлежность слова этому языку. Приведены практические примеры и упражнения для самостоятельного решения
                          Оглавление
                            -
                            Тест 12
                            27 минут
                            -
                            Лекция 14
                            1 час 30 минут
                            Синтаксический разбор
                            В данной лекции рассматриваются формальные определения, связанные с прямыми синтаксическими анализаторами, определяется понятие синтаксического разбора и связанные с ним специфические определения. Приведены практические примеры и упражнения для самостоятельной проработки
                            Оглавление
                              -
                              Тест 13
                              27 минут
                              -
                              Лекция 15
                              1 час 7 минут
                              Алгоритмические проблемы
                              В данной лекции рассматриваются понятия вычислимости, разрешимости, перечислимости и универсальных моделей вычислений. Рассмотрены алгоритмические проблемы, связанные с контекстно-свободными грамматиками, вводятся термины "массовая задача", "индивидуальная задача", "схема кодирования", "задача распознавания", "алгоритмическая проблема". Приведены практические примеры и задачи для самостоятельной проработки
                              Оглавление
                                -
                                Тест 14
                                27 минут
                                -
                                Лекция 16
                                39 минут
                                Алгоритмически разрешимые проблемы
                                В данной лекции рассматриваются наиболее известные разрешимые проблемы, связанные с грамматиками, автоматами и регулярными выражениями. Сформулированы также теоремы о разрешимости для некоторых алгоритмических проблем. Приведены практические примеры и упражнения для самостоятельного решения
                                Оглавление
                                  -
                                  Тест 15
                                  27 минут
                                  -
                                  Лекция 17
                                  54 минуты
                                  Алгоритмически неразрешимые проблемы
                                  В данной лекции рассматриваются оказавшиеся неразрешимыми алгоритмические проблемы, связанные с контекстно-свободными языками. Доказывается неразрешимость проблем пустоты пересечения, бесконечности пересечения, однозначности, равенства, автоматности, контекстной свободности дополнения и пересечения контекстно-свободного языка. Доказательства приведены на практических примерах, а также приведены упражнения для самостоятельной проработки
                                  Оглавление
                                    -
                                    Тест 16
                                    27 минут
                                    -
                                    5 часов
                                    -
                                    Юлия Маковецкая
                                    Юлия Маковецкая
                                    Помогите решить задание лекции 3 курс Математическая теория формальных языков
                                    Евгения Гунченко
                                    Евгения Гунченко
                                    При каких результатах сдачи экзамена экстерном по дисциплине, в последствии будет выдано удостоверение о повышении квалификации?
                                    Наталья Алмаева
                                    Наталья Алмаева
                                    Россия
                                    Николай Щербаков
                                    Николай Щербаков
                                    Россия, Москва