Суффіксний автомат
[Ред] Опис
Розглянемо кінцевий алфавіт. Нехай - набір слів в алфавіті. Суффіксний автомат - це набір, де
- - кінцевий набір станів,
- - початковий стан,
- - набір термінальних станів,
- - функція переходу.
Для і, визначена, якщо стан досяжно з переходом по символу. Функція переходу поширюється на слова і позначає, що якщо вона існує, то стан досягнуто після читання слова зі стану. Автомат розпізнає мову.
Суффіксний автомат для рядка являє собою ациклічний орієнтований граф. з початковою вершиною і безліччю термінальних вершин, ребра якого позначені символами:
- вершини цього графа - стану автомата, а ребра - переходи,
- кожен перехід в автоматі - ребро в графі, позначене деяким символом і всі ребра, що виходять з однієї вершини мають різні мітки,
- один зі станів називається початковим, з нього досяжні всі інші стану,
- одне або кілька станів позначені як термінальні - якщо пройти від початкового стану до термінального з якого-небудь шляху і виписувати при цьому символи на переходах, то отримаємо один з суфіксів рядки.
Приклад суффіксного автомата для рядка.
Стан приймає рядок, якщо існує шлях з початкового стану в, такий, що якщо послідовно виписати букви на ребрах на шляху, отримаємо рядок.
Автомат приймає рядок, якщо її приймає хоча б одне з фінальних станів.
Так як автомат детермінований, то кожній колії відповідає рядок.
Якщо два рядки і приймаються одним станом довільного автомата, то для будь-якого рядка рядка і приймаються або не приймаються автоматом одночасно. Дійсно, незалежно від того, як ми прийшли в стан, якщо ми пройдемо з нього по шляху, відповідному рядку, ми зможемо точно сказати, в який стан ми потрапимо (зокрема, чи буде воно фінальним). Значить, будь-якого стану відповідає безліч рядків, які переводять його в одне з кінцевих станів.
Безліч називають правим контекстом стану.
Правий контекст визначений не тільки для стану, але і для рядків, узятих нею - правий контекст рядків збігається з правим контекстом стану.
Станів в автоматі не менше, аніж різних правих контекстів у подстрок рядки, для якої він побудований, причому в мінімальному автоматі досягається нижня оцінка.
Припустимо, що в автоматі є два стани і такі що. Ми можемо видалити стан і перевести переходи, що ведуть в нього в стан. Безліч прийнятих рядків від цього не зміниться, отже, ми можемо продовжувати, поки кількість статків не буде дорівнює числу попарно різних правих контекстів.
Таким чином, ДКА є мінімальним тоді і тільки тоді, коли праві контексти всіх його станів попарно різні. У разі суффіксного автомата правий контекст рядки взаимнооднозначное відповідає безлічі правих позицій входжень рядка в рядок. Таким чином, кожне стан автомата приймає рядки з однаковим безліччю правих позицій їх входжень і назад, все рядки з таким безліччю позицій приймається цим станом.