Семинар 6. Контекстно-свободные грамматики

Задача поиск подстроки, являющейся k-повтором для макс. k. Есть k-повтор с i позиции длины j-i <=> trunc(LCP(i, j) / (j-i)) = k. Решение за O(N^2). Нужно максимизировать отношение. Суффиксное дерево, перебор всех вершин в качестве LCP. В каждом поддереве нужно найти пару листьев с мин. разницей номеров. Динамика по дереву: ответ + множество всех номеров. Слияние результатов. Хранение множества в дереве поиска, добавление меньшего к большему, слияние за O(A log B), где A <= B. Оценка времени работы алгоритма: O(N log^2 N).

Контекстно-свободные грамматики. Формальное определение. Вывод слова. Язык КС-грамматики. Праволинейные грамматики и регулярные языки.

Не контекстно-свободный язык {0^n 1^n 2^n} (без док-ва). Замкнутость КС-языков относительно объединения, конкатенации, замыкания Клини, замены. Незамкнутость относительно пересечения, дополнения. Подкласс детерминированных КС-языков (кратко).