Check string against a regular expression
В рамках практики по программированию на матмехе СПБГУ возникла следующая задача:
Проверять, принадлежит ли строка языку, задаваемому регулярным выражением.
На вход подается регулярное выражение (например, (a|b)*c|(pq) ) и набор строк (abpq, c, aaaaa, ababaaabbbbaaac, apq).
Для каждой из этих строк в зависимости от результата принадлежности необходимо вывести Yes или NO
Условие вполне ясно. Но как же решить эту задачку????
Выражаясь словами " классиков" - "Как, как.. Ну очень просто!!"
1) Для начала, тривиальным образом построим по регулярному выражению конечный автомат( Разумеется, он может быть недетерминированным и содержать эпсилон-переходы. Ну да ладно, и не такое видали)
Это сделать довольно легко и, на данном этапе своего программистого развития, мы можем придумать аж несколько способов сделать наше дело.
К примеру, давайте придумаем КС грамматику, которая однозначно опишет наше выражение, напишем лексер, парсер и бинго. Но, подобный подход, для нашей задачи, несколько избыточен. Применение подобных методов в столь тривиальных задачах подобны выстрелам из пушки по воробьям....
Лучше применим алгоритм, известный нам с пеленок. Так называемый алгоритм сортировочной станции Дейкстры.
Внимательный читатель заметит, что наши входные данные не позволяют напрямую применить сей способ, так как регулярное выражение aaaaa на самом деле значит a.a.a.a.a, где '.' - бинарная левоассоциативная операция конкатенации. К счастью, для нас это не проблема. Просто преобразуем входную строку, вставив . в нужных местах.
2) Достаточно легко, но невероятно полезно, избавиться от эпсилон-переходов.
Для самых маленьких читателей, уточним, что есть эпсилон переход.
Определение: Эпсилон-переходом называется такой переход, который автомат может совершить без чтения входного символа("просто так"). На рисунке эпсилон-переходы, как несложно догадаться, обозначаются значком ε
Как мы будем это делать?
Необходимо всего лишь впустить в голову мысль, о том, что множество состояний одного автомата - может быть (и будет) состоянием какого-то другого автомата. Действительно, у нас есть состояние q, давайте назовем множество состояний, которые связаны эпсилон-переходами с q - замыканием q. (Разумеется, замыкание содержит и q тоже)
Тогда мы получим недетерминированный конечный автомат, в котором в качестве состояний выступают замыкания состояний предыдущего автомата. Ну, то есть получаем некоторую конденсацию автомата.
Что мы сделали с не эпсилон-переходами из элементов замыкания? Это конечно, довольно очевидно, но они сохранились.
<наша функция переходов просто напросто теперь действует из замыкания в замыкание)
- Недетерминированный автомат, это конечно замечательная структура, которая во многом нагляднее и привлекательнее детерминированного на бумаге.
Но увы, комьютер довольно глупая машина, которая предпочитает точно знать, что она будет делать в следующий момент времени. (я не говорю о том, что нельзя остановиться на этапе недетерминированного конечного автомата, но нельзя отрицать, что если преобразовать его в детерминированный, то работать с ним станет легче. Хотя преобразование конечно тоже процесс не мгновенный и требует некоторых интеллектуальных и машинных усилий)
Вполне исчерпывающее, на мой взгляд, объяснение сути этого процесса содержится <a href = http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE_%D0%9D%D0%9A%D0%90_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D0%94%D0%9A%D0%90,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A2%D0%BE%D0%BC%D0%BF%D1%81%D0%BE%D0%BD%D0%B0> здесь - Ура, у нас есть ДКН. Казалось бы наш компьютер должен быть счастлив, но нет.
На сей раз нам жалко памяти и нужно минимизировать количество состояний в ДКН.
На наше счастье
британскиеученые доказали, что для каждого ДКН, найдется эквивалентный ему, но содержащий меньше или равно(в случае если перед нами уже минимизированная версия) состояний.
<a href = http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%94%D0%9A%D0%90,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B7%D0%B0_O(n%5E2)_%D1%81_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D0%B5%D0%BC_%D0%BF%D0%B0%D1%80_%D1%80%D0%B0%D0%B7%D0%BB%D0%B8%D1%87%D0%B8%D0%BC%D1%8B%D1%85_%D1%81%D0%BE%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B9> А вот и алгоритм
5) Ну, теперь мы удовлетворены полностью и можем беззаботно бегать по автомату и проверять, не ругается ли он на очередную строку.