Определение автомата 0:04 Автомат - это граф с ребрами и метками, где на каждом ребре написана буква. Автомат детерминированный, если из вершины ведет только одно ребро с определенной меткой.
Определение принимаемых слов 2:21 Принимаемые слова - это слова, которые можно прочитать на пути от старта до терминальной вершины. Отвергаемые слова - это те, которые нельзя прочитать или которые заканчиваются в не терминальной вершине.
Определение языка 5:55 Язык - это множество всех слов, которые принимает автомат. Правый контекст - это все возможные способы дополнить слово справа, чтобы оно лежало в языке.
Отношение эквивалентности 8:30 Два слова эквивалентны, если они имеют одинаковые правые контексты. Теорема Мохла Нероуда утверждает, что отношение эквивалентности, порожденное правыми контекстами, является отношением эквивалентности.
Минимальные автоматы и классы эквивалентности 10:10 Вводится понятие минимального автомата, принимающего только определенные слова из языка. Доказывается теорема, что минимальное число вершин достигается в том случае, когда состояниями автомата являются классы эквивалентности по введенному отношению.
Суффиксные автоматы 17:04 Рассматривается случай, когда нужно строить автомат, принимающий только суффиксы строки. Строится суффиксный автомат строки, где вершины соответствуют классам эквивалентности. Вводится понятие пустого класса эквивалентности, который соответствует словам, не являющимся подстроками строки. В общем случае, для всех слов, теорема не работает, но в случае суффиксных автоматов она работает.
Определение классов валентности 22:20 Рассматриваются подстроки с одинаковым правым контекстом. Доказывается, что если у двух строк одинаковый класс валентности, то одна является суффиксом другой.
Структура классов валентности 24:47 Утверждается, что в классе валентности существует самая длинная строка и несколько ее суффиксов. Доказывается, что все суффиксы длины хотя бы такой лежат в классе.
Определение ребер автомата 30:43 Ребра автомата определяются как тройки классов и символов алфавита. Доказывается, что если существует у и ц1 такое, что уд лежит в ц2, то и все другие пути из ц1 можно продолжить буквой д.
Определение ребер автомата 34:02 Доказательство того, что правый контекст строки "уд" вложен в правый контекст строки "вд". Определение ребер автомата на примере строки "абц аб".
Терминальные вершины и классы эквивалентности 43:30 Терминальные вершины - это вершины, содержащие суффиксы. Обозначение классов эквивалентности через квадратные скобки. Определение лонгеста и суффиксной ссылки класса. Утверждение о том, что строка является лонгестом в своем классе, если она является префиксом или строкой, продлевающейся налево разными буквами.
Определение лонгистов 49:01 Вводится понятие лонгиста - строки, которая является префиксом другой строки и имеет два различных продолжения слева. Доказывается, что любая строка, которая является лонгистом относительно другой строки, остается лонгистом при добавлении новой буквы.
Суффиксный автомат 55:58 Рассматривается алгоритм построения суффиксного автомата по строке с. Используется понятие лонгиста для определения классов эквивалентности. При переходе от строки с к строке сц, одна строка становится новым лонгистом. Определяется класс эквивалентности, который содержит все суффиксы сц, которые не являются подстроками с.
Определение лонгеста 1:05:26 Рассматривается самый длинный суффикс, который ранее входил в строку, и определяется его длина. Если новый лонгест появился, он обязательно равен нулю.
Доказательство 1:10:10 Доказывается, что если новый лонгест появился, то он равен нулю. Рассматривается произвольный новый лонгест и доказывается, что он равен нулю.
Вывод 1:13:36 Вывод: всегда появляется новый лонгест сц, возможно, с ноль. Максимальное количество вершин и классов равно двум.
