Теория вычислительных систем — это то, что позволяет нам программировать. Однако, можно писать программы и без представление о концепциях, скрывающихся за вычислительными процессами. Не то, чтобы это было плохо — когда мы программируем, то работаем на намного более высоком уровне абстракции. В конце концов, когда мы ведём машину, то концентрируемся только на двух или трёх педалях, переключателе передач и руле. Для повседневной неспешной езды этого более чем достаточно. Однако, если мы хотим управлять автомобилем на пределе его возможностей, то тут нужно знать гораздо больше, чем просто три педали, КПП и руль.
Такой подход справедлив и в программировании. Большая часть повседневной мирской работы может быть выполнена при минимальном знании теории вычислительных систем или даже вообще без него. Не нужно понимать теорию категорий, чтобы накидать форму «Контакты» в PHP. Тем не менее, если вы планируете писать код, требующий серьёзных вычислений, то тут уж придётся разобраться с тем, что у этих самых вычислений под капотом.
Цель этой статьи — представить некоторые фундаментальные основы вычислений. Если это окажется интересным, то в дальнейшем я могу написать более продвинутый топик на эту тему, но прямо сейчас я хочу просто рассмотреть логику простейшего абстрактного вычислительного устройства — машины конечных состояний (finite state machine).
Машина конечных состояний
Машина конечных состояний (finite state machine, FST), или конечный автомат (finite automaton) — это математическая абстракция, используемая при проектировании алгоритмов. Говоря простым языком, машина состояний умеет считывать последовательности входных данных. Когда она считывает входной сигнал, то переключается в новое состояние. Куда именно переключится, получив данный сигнал, — заложено в её текущем состоянии. Звучит запутанно, но на самом деле всё очень просто.
Представим устройство, которое читает длинную бумажную ленту. На каждом дюйме этой ленты напечатана буква — a или b.
Как только устройство считывает букву, оно меняет своё состояние. Вот очень простой граф переходов для такой машины:
Кружки — это состояния, в которых машина может быть. Стрелочки — переходы между ними. Так что, если вы в находитесь в состоянии s и считываете a, то вам необходимо перейти в состояние q. А если b, то просто остаётесь на месте.
Итак, если изначально мы находимся в состоянии s и начинаем читать ленту из первого рисунка слева направо, то сначала будет прочитана a, и мы переместимся в состояние q, затем b — вернёмся обратно в s. Следующая b оставит нас на месте, а a вновь переместит в q. Элементарно, но какой в этом смысл?
Оказывается, если пропустить ленту с буквами через FST, то по её итоговому состоянию можно сделать некоторые выводы о последовательности букв. Для приведённой выше простой машины состояний конечное состояние s означает, что лента закончилась буквой b. Если же мы закончили в состоянии q, то последней на ленте была буква a.
Это может показаться бессмысленным, но существует масса задач, которые можно решить с помощью такого подхода. Простейший пример: определить, содержит ли HTML-страница следующие теги в заданном порядке:
<html>
<head>
</head>
<body>
</body>
</html>
Машина состояний может перейти в новой состояние, считав <html>, потом зациклиться до считывания <head>, зациклиться до считывания </head> и т.д. Если она успешно придёт к финальному состоянию, то заданные тэги стоят в правильном порядке.
Также машина конечных состояний может использоваться для представления механизмов парковочного счётчика, автомата с газировкой, автоматизированного газового насоса и тому подобных штук.
Детерминированная машина конечных состояний (Deterministic Finite State Machine)
Машины состояний, которые мы рассматривали выше, являются детерминированными. У них из любого состояния существует только один переход для любого разрешённого входного сигнала. Другими словами, не существует двух различных путей из данного состояния, когда вы считываете, допустим, букву a. На первый взгляд такое ограничение кажется глупым.
Что хорошего в наборе решений, если один и тот же сигнал на входе может переместить вас более, чем в одно состояние? Вы же не можете сказать компьютеру: если x == true, то выполни doSomethingBig() или doSomethingSmall(), не так ли?
Ну, вообще-то, с помощью машины состояний можно провернуть что-то в этом роде. Выход конечного автомата — его финальное состояние. Сначала он проведёт все вычисления, затем прочтёт последнее состояние, и только тогда совершится какое-то действие. А в процессе переходов от состояния к состоянию не будет делаться ровным счётом ничего. FST обрабатывает поступившие данные, и только дойдя до конца и считав конечное состояние, совершает ожидаемое от неё действие (например, наливает газировку). Этот принцип особенно важен, когда дело доходит до недетерминированных машин конечных состояний.
Недетерминированная машина конечных состояний (Nondeterministic Finite State Machine)
Недетерминированные машины конечных состояний, или недетерминированные конечные автоматы (nondeterministic finite automaton, NFA) — это машины конечных состояний, у которых входной сигнал для данного состояния может вести более чем в одно последующее состояние. Допустим, например, что мы хотим построить машину конечных состояний, которая способна распознавать строки букв, начинающиеся с буквы a, за которой следует нуль или более букв b или нуль или более букв c. Условие останова — следующая буква алфавита на входе. Допустимыми строками будут:
- abbbbbbbbbc
- abbbc
- acccd
- acccccd
- ac (нуль повторений b)
- ad (нуль повторений c)
Итак, надо распознать букву a с последующим нулём или более одинаковых букв b или c и с замыкающей следующей буквой алфавита. Самый простой способ отобразить этот алгоритм с помощью машины состояний представлен ниже. Конечное состояние t означает, что строка была принята целиком и соответствует шаблону.
Видите проблему? Находясь в начальной точке s мы понятия не имеем, какой из путей выбрать. Если мы прочли только букву a, то мы ещё не знаем, идти нам в q или в r. Существует несколько способов решить эту задачу. Первый из них — откат. Вы просто перебираете все возможные пути и игнорируете или возвращаетесь назад по тем из них, где решение заходит в тупик.
На этом принципе основан алгоритм большинства шахматных программ. Они просматривают все возможности всех возможных ходов на данном этапе и выбирают ту стратегию, которая в данный момент даёт максимальное преимущество над противником.
Другой путь — это преобразовать недетерминированную машину состояний в детерминированную. Существование алгоритма преобразования любой недетерминированной машины в детерминированную является одним из интереснейших атрибутов NFA. Однако, часто это весьма сложный процесс. К счастью для нас, пример выше достаточно прост. Фактически, всё преобразование можно провести в уме, не прибегая к помощи формального алгоритма.
Машина ниже — детерминированная версия недетерминированной машины на предыдущем рисунке. Здесь конечные состояния t или v достижимы для любой принятой машиной строки.
Недетерминированная модель имеет четыре состояния и шесть переходов. Детерминированная модель — шесть состояний, десять переходов и два возможных завершения. Разница невелика, однако мы знаем, что сложность имеет свойство расти по экспоненте. И адекватных размеров недетерминированная машина способна вырасти в просто огромную детерминированную.
Регулярные выражения
Если вы когда-нибудь занимались любым видом программирования, то вы почти наверняка сталкивались с регулярными выражениями (regular expressions). Регулярные выражения и машины конечных состояний функционально эквивалентны. Всё, что можно допустить для (или связать с) регулярным выражением, можно допустить для (или связать с) машиной состояний. Например, шаблон, который мы разбирали выше, можно связать с
a(b*c|c*d)
Регулярные выражения и машины конечных состояний также имеют и одинаковые ограничения. Конкретнее, то они могут принимать или связывать шаблоны, для обработки которых требуется конечный размер памяти. Так какие же типы шаблонов для них недопустимы? Предположим, что мы хотим найти только строки, состоящие из a и b, где за каким-то количеством букв a следует такое же число букв b. Другими словами, за n a следует n b, где n — какое-то число. Примером могут послужить строки:
- ab
- aabb
- aaaaaabbbbbb
- aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb
На первый взгляд это выглядит детской задачей для машины конечных состояний. Проблема в том, что вы или быстро выйдете за пределы заданного числа состояний, или вам придётся допустить бесконечное их количество — и в этот момент ваше устройство перестаёт быть машиной конечных состояний. Допустим, вы создаёте конечный автомат, который может принять двадцать a и следующие за ними двадцать b. Он будет прекрасно работать до те пор, пока на вход не придёт строка из двадцати одной a и двадцати одной b. И тогда вам придётся переписывать вашу машину для обработки более длинных строк. Для любой строки, которую вы можете распознать, всегда есть ещё одна, которая будет лишь немного длиннее, но которую ваша машина уже не способна обработать, не выходя за пределы памяти.
Это положение известно как лемма о накачке для регулярных языков. Её основная мысль: если ваш шаблон имеет блок, который может быть повторён более, чем один раз, то этот шаблон не является регулярным. Другими словами, ни регулярные выражения, ни машины конечных состояний не могут быть сконструированы так, чтобы распознавать все строки, которые можно связать с шаблоном.
Если вы посмотрите внимательнее, то заметите, что тип шаблона, в котором каждая a связана с b, выглядит очень похоже на HTML, где внутри любой пары тэгов можно заключить произвольное количество других пар тэгов. Вот почему вы можете использовать регулярное выражение или машину конечных состояний для распознавания, содержит ли HTML-страница конкретные html, head и body элементы в правильном порядке, но не можете использовать регулярное выражение, чтобы сказать, является ли HTML-страница целиком корректной или нет. HTML — не регулярный шаблон.
Машина Тьюринга
Так как же нам распознавать нерегулярные шаблоны? Существует теоретическое устройство, подобное машине состояний и называемое машиной Тьюринга (Turing Machine). Как и у машины конечных состояний, у него имеется бумажная лента, с которой оно считывает информацию. Однако, машина Тьюринга также способна записывать и стирать данные на ленте. Полное объяснение принципов этого устройства займёт больше места, чем у нас здесь имеется, поэтому я обозначу лишь несколько важных моментов, относящихся к нашей дискуссии о машинах конечных состояний и регулярных выражениях.
Машина Тьюринга вычислительно полна, и всё, что в принципе может быть вычислено, может быть вычислено с помощью машины Тьюринга. А благодаря способности записывать данные на ленту с такой же лёгкостью, как и считывать их с ленты, она не ограничена конечным числом состояний. Бумажную ленту можно представить, как имеющую бесконечную длину. Очевидно, что современные компьютеры не обладают бесконечным количеством памяти, однако, они имеют её достаточно, чтобы вы не вышли за предел для тех типов задач, которые они способны обработать.
Машина Тьюринга предоставляет нам воображаемое механическое устройство, позволяющее визуализировать и понять, как работает вычислительный процесс. Это особенно полезно для понимания пределов вычислений. Если это интересно, то в будущем я могу написать отдельную статью о машине Тьюринга.
Почему это имеет значение?
Так какой во всём этом смысл? Как вышесказанное способно помочь вам при создании очередной PHP-формы? Несмотря на все их ограничения, машины конечных состояний — одна из центральных концепций теории вычислений. В частности, тот факт, что из любого недетермированного конечного автомата, который вы можете спроектировать, возможно получить детерминированный конечный автомат, делающий то же самое. Это ключевой момент, потому что подразумевает, что вы можете спроектировать свой алгоритм, в котором каждый шаг будет наиболее очевидным. А уже имея надлежащий алгоритм, вы сможете легко конвертировать его в ту форму, в которой он будет наиболее эффективен.
Понимание, что машины конечных состояний и регулярные выражения функционально эквивалентны, открывает невероятно интересные способы применения движков регэкспов. Особенно, когда дело доходит до создания бизнес-правил, которые могут быть изменены без перекомпиляции всей системы.
Знание основ теории вычислительных систем позволяет вам брать проблему X, которую вы понятия не имеете как решать, и применять к ней подход: «Я не знаю, как решить X, но я знаю, как решить Y и как привести решение для Y к решению для X. Вот почему теперь я знаю, как решить X».
Автор: AveNat
