Изменения

Рассмотрим конечный алфавит <tex>A</tex>. Пусть <tex>A^*</tex> {{---}} набор слов в алфавите <tex>A</tex>. Суффиксный автомат <tex>\mathcal{A}</tex> {{---}} это набор <tex>\langle Q, A, i, T, \delta \rangle</tex>, где* <tex>Q</tex> {{---}} конечный набор состояний,* <tex>i</tex> {{---}} начальное состояние,* <tex>T</tex> {{---}} набор терминальных состояний,* <tex>\delta</tex> {{---}} функция перехода. Для <tex>q \in Q</tex> и <tex>a \in A</tex>, <tex>\delta(q, a)</tex> определена, если состояние достижимо из <tex>q</tex> переходом по символу <tex>a</tex>. Функция перехода распространяется на слова и <tex>\delta(q, x)</tex> обозначает, что если она существует, то состояние достигнуто после чтения слова <tex>x</tex> из состояния <tex>q</tex>.Автомат <tex>\mathcal{A}</tex> распознает язык <tex>\{x \in A^* / \delta(q, x) \in T \}</tex>. Суффиксный автомат <tex>\mathcal{A}</tex> для строки <tex>s</tex> представляет собой [[Основные_определения_теории_графов|ациклический ориентированный граф]], с начальной вершиной и множеством терминальных вершин, рёбра которого помечены символами <tex>s</tex>:

* Каждый каждый переход в автомате {{---}} ребро в графе, помеченное некоторым символам. Все символом и все рёбра, исходящие из одной вершины имеют разные метки,* Одно одно из состояний называется начальным, из него достижимы все остальные состояния,* Одно одно или несколько состояний помечены как терминальные {{---}} если пройти от начального состояния до терминального по какому-либо пути и выписывать при этом символы на переходах, то получим один из суффиксов строки <tex>s</tex>.