В 2022 году Computer Science Center приостановил набор и обучение
Курсы
/
Алгоритмы и структуры данных, часть 2
/
весна 2018
/

Семинар 7. Контекстно-свободные грамматики (алгоритмы)

Суббота, 24 марта 2018
НГУ, ауд. 2128, НГУ, новый корпус
Список тем / 23 записи
    1.
    Строки. Z-функция
    2.
    Семинар 1. LCP, поиск палиндромов, ДКА
    3.
    Префикс-функция, поиск бора.
    4.
    Семинар 2. Поиск тандемных повторов, Ахо-Корасик
    5.
    Суффиксное дерево
    6.
    Семинар 3. Эквивалентность автоматов
    7.
    Суффиксный массив
    8.
    Семинар 4. Недетерминированные автоматы.
    9.
    Семинар 5. Регулярные выражения
    10.
    Семинар 6. Контекстно-свободные грамматики
    11.
    Суффиксный массив (продолжение)
    12.
    Преобразование Барроуза-Уилера
    13.
    Приближённый поиск подстроки
    14.
    Семинар 7. Контекстно-свободные грамматики (алгоритмы)
    15.
    Графы, обход в ширину, обход в глубину
    16.
    Семинар 8. Разбор КС-грамматики
    17.
    Обход в глубину (продолжение)
    18.
    Кратчайшие пути
    19.
    Семинар 10. Остовные деревья, сжатие компонент
    20.
    Кратчайшие пути (продолжение)
    21.
    Семинар 11. NP-задачи и игры на графах
    22.
    Потоки
    23.
    Семинар 12. Потоки минимальной стоимости

Описание

Достижимый (reachable) нетерминал. Определение, поиск обходом за O(G). Зануляющийся (nullable) нетерминал. Определение, реккурентное условие. Поиск за O(N G). Хранение для правил кол-ва нетерминалов, пока не отмеченных как nullable. Очередь nullable нетерминалов. Определение всех nullable нетерм. за O(G). Выводящий (generating) нетерминал. Определение, реккурентное условие. Аналогия с nullable нетерминалами (если стереть терминалы из правил). Поиск за O(G). Полезный (useful) нетерминал. Определение. Поиск: ищем и удаляем сначала все негенерирующие, потом все недостижимые нетерм.

Нормальная форма Хомского. Определение. Построение: удаление eps-правил, цепных правил, разбиение длинных правил, устранение терминалов. Дерево разбора слова, дерево разбора/вывода.

Не успели: Парсер CYK: R[l, r, A] - можно ли из нетерминала A вывести подстроку S[l:r). Динамика назад, переходы. Время работы O(G N^3).

Лемма о разрастании для КС-языков. Дерево разбора в НФХ. При длине слова > 2^|N| на каком-то пути вниз есть два одинаковых нетерминала. Формулировка леммы. Применение к {0^n 1^n 2^n}.