Регулярное выражение - это язык поиска подстрок в тексте, основанный на использовании специальных символов и указателей. По сути это строка-образец, которая состоит из символов (статического текста) и спецсимволов (символов, обозначающих какие-то последовательности) и задаёт правило поиска подстроки в обрабатываемом тексте. Регулярное выражение однозначно определяет автомат-распознаватель. Для перехода к автомату используется т.н. разметка мест. Местом в регулярном выражении называется позиция до и после обрабатываемого автоматом символа. Разметка заключается в сопоставлении местам индивидуальных индексов, обозначающих состояние автомата. Разметка регулярных выражений проводится по правилам подчинения мест.
1. Индекс места перед любыми скобками распространяется на начальные места всех дизъюнктивных членов, записанных в этих скобках.
2. Индекс конечного места, любого дизъюнктивного члена, заключенного в любые скобки, распространяется на место, непосредственно следующее за этими скобками.
3. Индекс места перед итерационными скобками распространяется на место, непосредственно следующее за этими скобками.
4. Индекс конечного места любого дизъюнктивного члена, заключенного в итерационные скобки, распространяется на начальные места всех дизъюнктивных членов, заключенных в эти итерационные скобки.
5. Индексы мест, слева и справа от которых стоят буквы, никуда не распространяются.
6. В автоматах многократного действия индекс конечного места всего выражения распространяется на те же места, на которые распространяется индекс начального места. Это правило справедливо только в тех случаях, когда событие представлено регулярным выражением так, что оно не содержит многократно повторяющихся слов, входящих в заданное событие. И тогда организация автомата многократного действия осуществляется путем разметки.
Смысл приведенных правил подчинения мест сводится к следующему: основному месту с индексом i подчиняется место j, если автомат, находящийся в состоянии i, может принять букву входного алфавита, записанную непосредственно справа от места j.
Пример преобразования
Регулярное выражение:
( {b}* v a )* ( ab v {c}*a ) ( b v c )
По размеченному регулярному выражению теперь можно составить таблицу переходов автомата. Однако перед построением таблицы целесообразно уменьшить число индексов основных мест, следовательно, число внутренних состояний автомата.
Состояния q0, q1 и q2 получились одинаковые. Их можно сократить до одного состояния q0.
Ø – это переход автомата в тупиковое состояние qт. Для удобства эти переходы не будут отображены на графике.
Исходя из таблицы переходов уже можно построить детерминированный конечный автомат.