Биба, боба, абоба

Попробуйте посмотреть на схему автомата как на поле для настольной игры: встаньте в кружочек с надписью Start, читайте слово и ходите по стрелочкам. Каждый ход — это одна буква! Обратите внимание на то, куда вы приходите в итоге.

1. Итак, на схеме конечного автомата есть кружки, стрелки и буквы (явно разделённые на гласные и согласные). Из правого верхнего кружка выходит только одна стрелка — с гласными; из остальных двух — по две: с гласными и с согласными. Сама по себе схема действительно очень напоминает настольную игру: особенно на это намекает кружок Start. Соответственно, перед каждым ходом есть выбор: ходить по стрелке с гласными или с согласными. Но ходить нужно не как попало: на вход автомату подаётся слово, которое требуется проверить по какому-то критерию (например, возможно ли оно в ротокас), и ходы должны зависеть от этого слова. Теперь принцип работы понятен: давайте поставим воображаемую фишку в кружочек Start, а затем будем читать наше слово по буквам, каждый раз делая ход по стрелке с прочтённой буквой.

Попробуем прочитать слова из условия. Читая tauo, мы пойдём из Start направо, оттуда налево, а затем дважды пройдём по петле, оставшись в итоге в левом верхнем кружке (обведённом дважды). Теперь прочтём ouragaveva: из Start влево, затем по петле, затем четырежды направо и обратно — в итоге мы снова в двойном кружке. Читая таким же образом невозможные слова, видим, что после gataap фишка остановилась в правом кружке, а vonoka вообще не дочиталось до конца: ни на одной стрелке нет буквы n. Вывод: слово удовлетворяет заданному конечным автоматом условию тогда и только тогда, когда его чтение заканчивается в двойном кружке.

Введём терминологию: круги называются состояниями автомата; состояние со словом Start — начальное, а обведённые дважды состояния — конечные (в общем случае их может быть несколько). Начальное состояние может в то же время быть и конечным (как вы увидите в пункте 2). Стрелки — это переходы. Если чтение слова заканчивается в конечном состоянии, то автомат допускает это слово. Все слова, допускаемые КА, вместе образуют его язык.

Структуру слов можно описать и более интуитивно. Обозначим гласные a, e, i, o, u как V, а согласные p, t, k, v, r, g как C. Тогда каждое возможное слово начинается с V или CV, после чего фишка обязательно попадает в жирный кружок. Оттуда можно либо делать петлю, добавляя к слову V, либо ходить вправо-влево, добавляя к слову CV. То есть можно сказать, что все возможные в ротокас слова состоят из слогов вида V или CV. Или эквивалентное условие: нет двух согласных подряд, а также согласных на конце слов.

Теперь можно потренироваться на словах из задания:

2. У этого автомата единственное конечное состояние совпадает с начальным. Это значит, что фишка может ходить либо по верхнему переходу-петле, либо в какое-то из трех других состояний и обратно. В корректных словах такого вида ходы могут комбинироваться в любом количестве и порядке. Вспомнив, что в пункте 1 мы, по сути, описали два возможных типа слогов в ротокас, логично предположить, что теперь речь снова о слогах, но уже четырех типов. Скорее всего, петля из одного перехода сверху — самый простой тип: слоги из любой одной гласной. Значит, остальная часть автомата посвящена разным типам слогов из согласной (стрелка туда) и гласной (стрелка обратно): и действительно, справа осталось использовать три «таблички» с согласными и три — с гласными.

Судя по вынесенным справа подписям к стрелкам, согласные s и t и гласная i ведут себя не так, как остальные буквы: значит, из согласных t и s одна употребляется только перед i, а другая — только перед остальными гласными. Зная из условия, что s «встречается только в определённых ситуациях», можно вывести три типа слогов с согласными: si, tV’ и C’V, где V’ — любая гласная, кроме i, а C’ — любая согласная, кроме t и s. Итоговый автомат будет выглядеть так:

3. Заметим, что при чтении слова на токипоне возможность добавления очередной буквы зависит только от двух предыдущих букв. Сделаем табличку: какие буквы могут быть следующими, если известны две предыдущие? Будем обозначать согласные как C, гласные как V, носовые как N.  обозначает исключение из множества: например, C{t, j} — все согласные, кроме t и j. 0 обозначает отсутствие буквы — то есть если пока прочтена только одна буква, будем ставить 0 вместо предпоследней прочтённой. 0 + 0 значит, что никаких букв пока не прочтено и мы находимся в начале слова.

Идея такова: раз всё зависит от двух предыдущих букв, то пускай разным типам этих двух букв будут соответствовать разные состояния конечного автомата. Для каждого из таких состояний точно известно, по каким буквам из него можно выйти. Кроме того, по предыдущему состоянию и букве перехода однозначно определяется следующее состояние! Обозначим эти состояния цифрами слева в таблице. Последние две строки объединены в одно состояние, потому что они эквиваленты: в обоих случаях доступны только переходы по гласным. Состояние 1 — начальное, потому что соответствует началу слова. Осталось определить, какие состояния — конечные: это состояния 2 и 3 в силу требований к концу слова. Получится вот такой автомат:

Идея смотреть на последние несколько символов полезна, но, разумеется, это не единственный способ решать задачу; можно, например, попробовать вывести слоговую структуру слов и работать с ней.

В общем случае КА используется так: пусть есть определённое множество слов X (здесь и далее под словами понимаются последовательности символов). Каким-то образом строится конечный автомат, допускающий только слова из X (иначе говоря, автомат с языком X). Теперь этому автомату можно давать на вход любые слова, и он будет определять, содержатся эти слова в X или нет. Например, в задаче в качестве X взято множество возможных в ротокас слов. Однако стоит заметить, что множество «возможных» слов устроено сильно проще, чем множество действительно существующих в ротокас слов: оно ограничено только слоговой структурой и контекстным использованием t/s и поэтому очень компактно описывается формально: в частности, можно построить небольшой и наглядный конечный автомат. При этом такой автомат допускает, например, слово aaaaaa...aaa (239239239 букв a подряд) — вряд ли его можно назвать реальным словом ротокас. Поэтому использовать такой КА для различения существующих и несуществующих слов нельзя: будет слишком много ложноположительных результатов; можно только отсекать слова, точно не подходящие фонетически. Забавно, что и тут автомат работает не совсем корректно. Само слово Rotokas даёт ложноотрицательный результат — попытки формалистского подхода к естественным языкам часто упираются в исключения.

Можно ли всё же построить автомат, определяющий реальные слова ротокас? Или более общо — для каких языков (то есть множеств слов) можно построить автомат, а для каких — нельзя?

Языки, для которых существует распознающий их конечный автомат, называются автоматными, или регулярными. Проверка языка на регулярность — задача довольно интересная. Мы уже знаем, что язык потенциальных слов ротокас регулярен, но может ли мы сказать то же самое про язык реальных слов? А что если речь идёт не о ротокас, а о произвольном естественном языке?

Тут важно понять, какие слова считаются «реальными». Если те, которые хоть раз письменно, устно или мысленно использовались говорящими на языке людьми, — задача проста: таких слов конечное число, а любой язык с конечным множеством слов и конечным алфавитом является регулярным. Показать это несложно: для каждого слова можно сделать отдельную цепочку букв. Такой автомат будет громоздким, но конечным. Например, автомат, распознающий все слова английского языка, мог бы выглядеть примерно так³:

Правда, есть проблема: пусть дано слово, начинающееся на a. Стрелок с буквой a из начального состояния много; по какой идти? Иными словами, перед нами недетерминированный конечный автомат (НКА или НДКА). Любой такой автомат можно сделать детерминированным (ДКА): таким, что все переходы при чтении слов определены однозначно. Например, наш автомат можно детерминировать вот так:

Здесь каждому существующему в языке началу слова (иначе говоря, префиксу) соответствует состояние автомата; начальное состояние соответствует пустой строке. Таким образом, что прочитать слово zyzzyva, нужно пройти через состояния Start, z, zy, zyz, zyzz, zyzzy, zyzzyv, zyzzyva; первые три из этих состояний проходятся и при чтении слова zythum. Такая структура данных называется префиксным деревом или бором и хороша тем, что каждому допускаемому слову в ней соответствует своё конечное состояние. Это значит, что в конечных состояниях можно хранить и обновлять информацию про слова: например, сколько раз слово встретилось в тексте.

Однако для основной задачи автомата — различения корректных и некорректных слов языка — бор зачастую использует слишком много компьютерной памяти. Поэтому существуют алгоритмы для построения минимального (то есть с минимальным возможным количеством состояний) ДКА на конечном наборе слов. Например, снизу слева — бор, а справа — минимальный ДКА для языка {biba, boba, aboba}. Как видим, минимизация конечных автоматов — задача важная и интересная.

С помощью таких автоматов можно, например, искать заданные слова в больших текстах: строим автомат по набору искомых слов, а затем подаём ему на вход слова текста по очереди. Таким образом можно написать, к примеру, поисковую систему или спам-фильтр.

Есть и более сложная задача, чем поиск слов в текстах: поиск паттернов (то есть произвольных последовательностей символов). Разница в том, что слова ограничены пробелами, и поэтому каждое слово текста можно проверять по отдельности; паттерны же могут перекрываться. Ни один из КА выше не найдёт в тексте abiba паттерн biba: после прочтения ab- автомат придёт в тупик, а при перезапуске останется только строка iba, где тоже ничего не найдётся. Для решения этой задачи нужен особый конечный автомат, строящийся алгоритмом Ахо — Корасик.

Итак, для конечных языков конечные автоматы строить можно — в том числе и для естественных, если под ними понимать конечные множества реально используемых слов. Как насчёт бесконечных?

Теоретически многие естественные языки можно считать бесконечными: к примеру, если учитывать сколь угодно много повторяющиеся суффиксы или приставки. Так, можно сказать, что в русском языке одних только терминов родства для предка мужского пола бесконечно много: есть дед, прадед, прапрадед, прапра...прадед (179179179 «пра») и так далее. Впрочем, для конечного автомата это не проблема:

Здесь для удобства длинные цепочки из однобуквенных переходов сжаты в переходы по трем буквам сразу

Автор послесловия попытался найти нерегулярный естественный язык — и не нашёл. Кажется, слова в естественных языках ведут себя довольно регулярно — особенно те, в которых морфемы добавляются линейно. Вполне возможно, что для поиска контрпримера имеет смысл обратить внимание на крупные составные числительные в разных языках; впрочем, это зависит от того, считать ли их словами. Над этой идеей читатель может подумать на досуге, а пока приведём пример нерегулярного языка в широком понимании этого слова.

Это язык правильных скобочных последовательностей (ПСП), алфавит которого в простейшем случае состоит только из двух символов: ) и (. Строка из открывающихся и закрывающихся скобок является ПСП (и, соответственно, словом нашего языка), если между скобками можно расставить числа и знаки арифметических действий так, чтобы получилось корректное арифметическое выражение. Например, строка «(()())» — это ПСП, потому что можно написать ((1+1)+(1+1)), а строки «)()(» и «(()))» — нет: первая начинается с закрывающейся скобки, а во второй скобок двух типов не поровну. Давайте докажем, что нельзя построить конечный автомат, определяющий, является строка из скобок ПСП или нет.

Допустим противное: пусть автомат построен. В нём может быть очень много состояний, но всё же конечное число — скажем, N. Автомат должен распознавать в том числе ПСП «(((...(())...)))» (обозначим эту ПСП как S), где сначала идёт N+1 открывающаяся скобка, а затем — столько же закрывающихся. Но поскольку состояний меньше, чем открывающихся скобок, то в какой-то момент чтения, ещё не дойдя до середины слова S, мы окажемся в состоянии, где уже были до этого. Это значит, что в автомате есть цикл, состоящий из переходов по открывающимся скобкам. А значит, можно построить другое слово S’ следующим образом: начнём читать S в нашем автомате, но, дойдя до цикла, пройдём его не один раз, а, скажем, 10. Нагулявшись по циклу, продолжим идти по тому же пути, по которому мы читали слово S. Полученное слово S’ — это слово S с вставленными где-то в первой половине дополнительными открывающимися скобками. Значит, в S’ открывающихся скобок больше, чем закрывающихся, то есть S’ — не ПСП и не слово нашего языка. Тем не менее автомат это слово допустил — значит, этот автомат на самом деле неправильный. Противоречие.

Этот автомат с шестью состояниями допускает слово «((((((()))))))» (по 7 скобок обоих типов), но засчёт четырёхугольного цикла допускает также, например, слово «((((((((((()))))))» (11 открывающихся, 7 закрывающихся скобок).

Гуляя кругами по циклу, мы как будто «накачали» слово S насосом в определённом месте, поэтому только что доказанный факт — это частный случай утверждения, называемого леммой о накачке (pumping lemma). Лемма о накачке бывает полезна для доказательства нерегулярности бесконечных языков палиндромной или рекурсивной структуры — или, если говорить грубо, таких языков, где конец слова зависит от начала. В какой-то степени это относится и к языку ПСП — количество закрывающихся скобок в конце зависит от количества открывающихся во всём слове. Можно сказать, что конечные автоматы «не умеют считать до бесконечности» — поэтому не могут гарантировать, что скобок двух типов будет поровну. Упражнение для заинтересованного читателя: а можно ли распознавать язык ПСП бесконечным (с бесконечным множеством состояний) автоматом?

Ответ

Можно! Построим автомат с бесконечным множеством состояний, пронумерованных числами 0, 1, 2, 3 и так далее. Для каждой пары состояний с соседними номерами добавим из меньшего в большее переход по символу (, а из большего в меньшее — по ). Начальным будет состояние 0; оно же будет и единственным конечным.

Можно заметить, что при чтении строки из скобок номер текущего состояния — это количество прочтённых открывающихся скобок, к которым пока не нашлось соответствующей закрывающейся. У корректной ПСП этот показатель должен быть равен 0. Если же в какой-то момент закрывающихся скобок будет прочтено больше, чем открывающихся (то есть строка заведомо не ПСП), то автомат попытается уйти в отрицательные числа, остановится и не допустит строку. Значит, этот автомат распознаёт язык ПСП.

Пример со скобочными последовательностям подсказывает идеи к вопросу про регулярность естественных языков. Во-первых, с задачей распознавания не корректных слов, а корректных, скажем, предложений автомат вряд ли справится: конечного числа состояний не хватит для обработки синтаксической рекурсии с вложенными опоясывающими конструкциями вроде «как ..., так и ...». Чтобы найти пример языка, слова которого не распознаются конечным автоматом, можно подумать о циркумфиксах (морфемах, состоящих из приставки и суффикса одновременно). Если существует естественный язык, в котором к словам можно добавлять сколь угодно много циркумфиксов подряд, то он, скорее всего, нерегулярен. А существует ли он?

Вывод: конечные автоматы — удобный инструмент, интересный теоретически и полезный на практике, в том числе в задачах компьютерной лингвистики вроде синтаксического и лексического анализа текста. Впрочем, естественный язык — слишком сложная структура, и полноценно описать её математическими моделями практически невозможно.

Задача использовалась на I туре Североамериканской олимпиады по компьютерной лингвистике (NACLO) в 2008 году.

Автор задачи — Патрик Литтелл.
Автор послесловия и перевода задачи на русский язык — Артём Борисов.

³ Здесь и далее конечные автоматы созданы с помощью сайта Finite State Machine Designer.