10.7. Більш складні зразки і автомати

Ми можемо шукати не конкретне слово, а подслова заданого виду. Наприклад, можна шукати слова виду a? B, де замість? може стояти будь-яка буква (іншими словами, нас цікавить буква b на відстані після літери a).

10.7.1. Вказати кінцевий автомат, перевіряючий, чи є у вхідному слові фрагмент виду a? B.

Рішення. Читаючи слово, слід пам'ятати, чи є буква a на останньому місці і на передостанньому - поки не зустрінемо шуканий фрагмент. Автомат має стану 00, 01, 10, 11, їхній зміст такий:

Таблиця переходів автомата:

Інший стандартний знак в зразку - це зірочка (*), на місце якої може бути підставлений будь-яке слово. Наприклад, зразок ab * cd означає, що ми шукаємо подсловом ab, за яким слід що завгодно, а потім (на будь-якій відстані) йде cd.

10.7.2. Вказати кінцевий автомат, перевіряючий, чи є у вхідному слові зразок ab * cd (в описаному тільки що сенсі).

Рішення.

Ще один вид пошуку - це пошук будь-якого з слів деякого списку.

10.7.3. Дан список слів і слово . Визначити, чи входить хоча б одне зі слів в слово (Як подсловом). Кількість дій не повинно перевищувати константи, помноженої на сумарну довжину всіх слів (зі списку і того, в якому відбувається пошук).

Рішення. Очевидний спосіб полягає в тому, щоб кожне слово зі списку перевіряти окремо (за допомогою одного з розглянутих алгоритмів). Однак при цьому ми не вкладаємося в заданий число дій (через множення на довжину слова ).

Подивимося на справу з іншого боку. Кожному зразку зі списку відповідає кінцевий автомат з деяким безліччю станів. Ці автомати можна об'єднати в один, безліччю станів якого буде твір множин станів всіх тих автоматів. Це - дуже велика кількість. Однак насправді більшість його елементів недоступні (не можуть з'явитися при читанні вхідного слова) і за рахунок цього виходить економія. Приблизно цю ідею (але в зміненому вигляді) ми і будемо використовувати.

Згадаймо алгоритм Кнута-Морріса-Пратта. У ньому, читаючи вхідний слово, ми зберігали найбільшу початок зразка, що є кінцем прочитаної частини. Тепер нам слід зберігати для кожного із зразків найбільше його початок, що є кінцем прочитаної частини. Вирішальним виявляється таке зауваження: досить зберігати найдовше з них - всі інші по ньому відновлюються (як найбільші початку зразків, які є його кінцями).

Склеїмо всі зразки в дерево, об'єднавши їх збігаються початкові ділянки. Наприклад, набору зразків

Формально кажучи, вершинами дерева є все початку всіх зразків, а сини вершини виходять приписуванням букви.

Читаючи вхідний слово, ми рухаємося по цьому дереву: поточна вершина - це найбільша (сама права) з вершин, що є кінцем прочитаної частини ( найбільший кінець прочитаної частини, що є початком одного із зразків).

визначимо функцію , Аргументами і значеннями якої є вершини дерева. Саме, найбільша вершина дерева, що є кінцем . (Нагадаємо, вершини дерева - це слова.) Нам знадобиться таке твердження:

10.7.4. нехай - вершина дерева. Довести, що множина всіх вершин, які є кінцями , так само

Рішення. Див. Доказ аналогічного твердження для алгоритму Кнута-Морріса-Пратта.

Тепер ясно, що потрібно робити, перебуваючи в вершині і читаючи букву z вхідного слова. Треба переглядати послідовно вершини , , ., Поки не виявиться така, з якої виходить стрілка з буквою z. Та вершина, в яку ця стрілка веде, і буде нашим наступним положенням.

Залишається зрозуміти, як для кожної вершини дерева обчислити покажчик на значення функції в цій вершині. Це робиться як раніше, при цьому значення для більш коротких слів використовуються при обчисленні чергового значення функції . Це означає, що вершини дерева слід переглядати в порядку зростання їх довжини. Неважко зрозуміти, що все це можна укласти в необхідне число дій (хоча константа залежить від числа букв в алфавіті). Положення стосовно цього подробиці див. В "Різні алгоритми на графах" .

Можна поцікавитися, які властивості слів розпізнаються за допомогою кінцевих автоматів. Виявляється, що існує просто описуваний клас зразків, що задає всі такі властивості - клас регулярних виразів.

Нехай фіксований кінцевий алфавіт , Який не містить символів , , (,), * І | (Вони будуть використовуватися для побудови регулярних виразів і не повинні перемішуватися з буквами). Регулярні вирази будуються за такими правилами:

1. буква алфавіту Г - регулярний вираз;
2. символи - Регулярні вирази
3. якщо A, B, C, ..., E - регулярні вирази, то (ABC ... E) - регулярний вираз;
4. якщо A, B, C, ..., E - регулярні вирази, то (A | B | C | ... | E) - регулярний вираз;
5. якщо A - регулярний вираз, то A * - регулярний вираз.

Кожне регулярний вираз задає безліч слів в алфавіті за такими правилами:

1. букві відповідає одноелементні безліч, що складається з однобуквеним слова, що складається з цієї букви;
2. символу відповідає порожня множина, а символу - одноелементні безліч, єдиним елементом якого є пусте слово;
3. регулярному виразу (ABC ... E) відповідає безліч всіх слів, які можна отримати, якщо до слова з A приписати слово з B, потім з C, ..., потім з E
4. регулярному виразу (A | B | C | ... | E) відповідає об'єднання множин, що відповідають виразами A, B, C, ..., E;
5. регулярному виразу A {*} відповідає ітерація множини, відповідного виразу A, тобто безліч всіх слів, які можна так розрізати на шматки, що кожен шматок належить множині, відповідному висловом A. (Зокрема, пусте слово завжди міститься в A *.)

Безлічі, відповідні регулярними виразами, Називаються регулярними. Ось кілька прикладів:

10.7.5. Написати регулярний вираз, якому відповідає безліч всіх слів з букв a і b, в яких число букв a парне.

Рішення. Вираз b * задає все слова без букви a, а вираз - всі слова рівно з двома буквами a. Залишається об'єднати ці безлічі, а потім застосувати ітерацію:

Інший варіант відповіді:

10.7.6. Написати регулярний вираз, яке задає безліч всіх слів з букв , В яких слово bac є подсловом.

Рішення.

10.7.7. Написати регулярний вираз, яке задає безліч всіх слів з букв , В яких слово bac не є подсловом.

Вказівка. Це завдання складніше попередньої; мабуть, найпростіший спосіб її вирішити - перейти до кінцевих автоматів і повернутися назад (див. нижче завдання 10.7.14.).

Тепер завдання про пошук зразка в слові можна переформулювати так: перевірити, чи належить слово безлічі, відповідного даному регулярному виразу.

10.7.8. Які вирази відповідають зразкам a? B і ab * cd, розглянутим раніше? (В зразку символ * використовується не в тому сенсі, що в регулярних виразах!) Передбачається, що алфавіт містить букви .

Рішення.

((A | b | c | d | e) * a (a | b | c | d | e) b (a | b | c | d | e) *) ((a | b | c | d | e ) * ab (a | b | c | d | e) * cd (a | b | c | d | e) *)

10.7.9. Довести, що для будь-якого регулярного виразу можна побудувати кінцевий автомат, який розпізнає відповідне цього виразу безліч слів.

Рішення. Нам буде потрібно нове поняття - поняття джерела, або недетермінірованного кінцевого автомата. Уявімо собі орієнтований граф - картинку з декількох точок (вершин) і деяких стрілок, що з'єднують ці точки (ребер). Нехай на деяких ребрах написані літери (не обов'язково на всіх). Нехай також серед вершин обрані дві - початкова Н і кінцева К. Така картинка називається джерелом.

Будемо рухатися різними способами з Н в До, читаючи літери по дорозі (на тих стрілках, де вони є). Кожному шляху з Н в К, таким чином, відповідає деякий слово. А джерела в цілому відповідає безліч слів - тих слів, які можна прочитати на шляхах з Н в К.

Зауваження. Якщо намалювати стану кінцевого автомата у вигляді точок, а переходи при читанні букв зобразити у вигляді стрілок, то стане ясно, що кінцевий автомат - це окремий випадок джерела. (З додатковими вимогами: (а) на всіх стрілках, за винятком провідних в До, є літери; (б) для будь-якої точки на виходять з неї стрілках кожна буква зустрічається рівно один раз.)

Ми будемо будувати кінцевий автомат по регулярному виразу в два прийоми. Спочатку ми побудуємо джерело, якому відповідав би те ж саме безліч слів. Потім для довільного джерела побудуємо автомат, який перевіряє, чи належить слово відповідного безлічі.

10.7.10. За регулярним виразом побудувати джерело, що задає той же безліч.

Рішення. Індукція по побудові регулярного виразу. Буквах відповідають графи з однієї стрілки. Об'єднання реалізується так:

Намальована картинка для об'єднання трьох множин, прямокутники - це джерела, їм відповідні; вказані початкові і кінцеві вершини. На нових стрілках (їх ) Букв не написано.

Конкатенації відповідає картинка

Нарешті, ітерації відповідає картинка

10.7.11. Дан джерело. Побудувати кінцевий автомат, перевіряючий, чи належить вхідний слово відповідного безлічі (тобто чи можна прочитати це слово, йдучи з Н в К).

Рішення. Станами автомата будуть безлічі вершин джерела. Саме, прочитавши деякий початок вхідного слова, ми будемо пам'ятати безліч всіх вершин джерела, в які можна пройти з початкової, прочитавши на шляху слово .

Тим самим задача вирішена.

Виявляється, що регулярні вирази, автомати і джерела розпізнають одні і ті ж множини. Щоб переконатися в цьому, нам залишилося вирішити таке завдання:

10.7.12. Дан джерело. Побудувати регулярний вираз, що задає той же безліч, що і це джерело.

Рішення. Нехай джерело має вершини . Будемо вважати, що - це початок, а - кінець. через позначимо безліч всіх слів, які можна прочитати на шляху з в , Якщо в якості проміжних пунктів дозволяється використовувати тільки вершини . Згідно з визначенням, джерела відповідає безліч .

індукцією по будемо доводити регулярність всіх множин при всіх і . при це очевидно (проміжні вершини заборонені, тому кожне з множин складається тільки з букв).

З чого складається безліч ? Відзначимо на шляху моменти, в яких він заходить в -у вершину. При цьому шлях розбивається на частини, кожна з яких вже не заходить в неї. Тому легко зрозуміти, що

(Вільність записи: ми використовуємо для операцій над множинами позначення як для регулярних виразів). Залишається скористатися припущенням індукції.

10.7.13. Де ще використовується те ж саме міркування?

Відповідь. В алгоритмі Флойда обчислення ціни найкоротшого шляху, см. "Різні алгоритми на графах" (Різні алгоритми на графах).

10.7.14. Довести, що клас множин, що задаються регулярними виразами, не змінився б, якби ми дозволили використовувати не тільки об'єднання, а й заперечення (а отже, і перетин - воно виражається через об'єднання і заперечення).

Рішення. Для автоматів перехід до заперечення очевидний.

Зауваження. На практиці важливу роль відіграє число станів автомата. Виявляється, що тут все не так просто, і перехід від джерела до автомата вимагає експоненціального зростання числа станів. Детальний розгляд пов'язаних з цим теоретичних і практичних питань - справа особлива (див. Книгу Ахо, Ульмана і Мережі про компіляторах).