Конечные автоматы регулярных выражений. Модификация регулярного выражения

Базис . Автоматы для выражений длины 1: и показаны на следующем рисунке.

Заметим, что у каждого из этих трех автоматов множество заключительных состояний состоит из одного состояния.

Индукционный шаг . Предположим теперь, что для каждого регулярного выражения длины <= k построен соответствующий НКА, причем у него единственное заключительное состояние. Рассмотрим произвольное регулярное выражение r длины k+1 . В зависимости от последней операции оно может иметь один из трех видов: (r 1 + r 2), (r 1 r 2) или (r 1) * . Пусть и - это НКА, распознающие языки L r1 и L r2 , соответственно. Не ограничивая общности, мы будем предполагать, что у них разные состояния: .

Тогда НКА , диаграмма которого представлена на рис. 5.2 , распознает язык .

У этого автомата множество состояний , где q 0 - это новое начальное состояние, q f - новое (единственное!) заключительное состояние, а программа включает программы автоматов M 1 и M 2 и четыре новых команды -переходов: . Очевидно, что язык, распознаваемый НКА M , включает все слова из L { M 1 } и из L { M 2 } . С другой стороны, каждое слово переводит q 0 в q f , и после первого шага несущий его путь проходит через q 0 1 или q 0 2 . Так как состояния M 1 и M 2 не пересекаются, то в первом случае этот путь может попасть в q f только по -переходу из q f 1 и тогда . Аналогично, во втором случае .

Для выражения диаграмма НКА , распознающего язык L r , представлена на следующем рисунке.

У этого автомата множество состояний , начальное состояние q 0 = q 0 1 , заключительное состояние q f =q f 2 , а программа включает программы автоматов M 1 и M 2 и одну новую команду - -переход из заключительного состояния M 1 в начальное состояние M 2 , т.е. . Здесь также очевидно, что всякий путь из q 0 = q 0 1 в q f =q f 2 проходит через -переход из q f 1 в q 0 2 . Поэтому всякое слово , допускаемое M , представляет конкатенацию некоторого слова из L M1 } с некоторым словом из L M2 } , и любая конкатенация таких слов допускается. Следовательно, НКА M распознает язык .

Пусть r = r 1 * . Диаграмма НКА , распознающего язык L r =L r1* = L M1 * представлена на рис. 5.3 .

У этого автомата множество состояний , где q 0 - это новое начальное состояние, q f - новое (единственное!) заключительное состояние, а программа включает программу автомата M 1 и четыре новых команды -переходов: . Очевидно, . Для непустого слова w по определению итерации для некоторого k >= 1 слово w можно разбить на k подслов: w=w 1 w 2 ... w k и все . Для каждого i= 1,... ,k слово w i переводит q 0 1 в q f 1 . Тогда для слова w в диаграмме M имеется путь

Следовательно, . Обратно, если некоторое слово переводит q 0 в q f , то либо оно есть либо его несет путь , который, перейдя из q 0 в q 0 1 и затем пройдя несколько раз по пути из q 0 1 в q f 1 и вернувшись из q f 1 в q 0 1 по -переходу, в конце концов из q f 1 по -переходу завершается в q f . Поэтому такое слово .

Из теорем 4.2 и 5.1 непосредственно получаем

Следствие 5.1 . Для каждого регулярного выражения можно эффективно построить детерминированный конечный автомат , который распознает язык, представляемый этим выражением.

Это утверждение - один из примеров теорем синтеза : по описанию задания (языка как регулярного выражения ) эффективно строится программа (ДКА), его выполняющая. Справедливо и обратное утверждение - теорема анализа .

Теорема 5.2 . По каждому детерминированному (или недетерминированному) конечному автомату можно построить регулярное выражение , которое представляет язык, распознаваемый этим автоматом.

Доказательство этой теоремы достаточно техническое и выходит за рамки нашего курса.

Таким образом, можно сделать вывод , что класс конечно автоматных языков совпадает с классом регулярных языков . Далее мы будем называть его просто классом автоматных языков .

Автомат M r , который строится в доказательстве теоремы 5.1

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

• Команда grep операционной системы Unix или аналогичные команды для поиска цепочек, которые можно встретить в Web-броузерах или системах форматирования текста. В таких системах РВ используются для описания шаблонов, которые пользователь ищет в файле. Различные поисковые системы преобразуют РВ либо в детерминированный конечный автомат (ДКА), либо недетерминированный конечный автомат (НКА) и применяют этот автомат к файлу, в котором производится поиск.
• Генераторы лексических анализаторов. Лексические анализаторы являются компонентом компилятора, они разбивают исходную программу на логические единицы (лексемы), которые могут состоять из одного или нескольких символов и имеют определенный смысл. Генератор лексических анализаторов получает формальные описания лексем, являющиеся по существу РВ, и создает ДКА, который распознает, какая из лексем появляется на его входе.
• РВ в языках программирования.

В данной статье мы сначала ознакомимся с конечными автоматами и их видами(ДКА и НКА), и далее рассмотрим пример построения минимального ДКА по регулярному выражению.

Конечные автоматы

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

Теперь рассмотрим, какими способами можно задать КА. Они могут задаваться в виде графов или в виде управляющих таблиц. В виде графа КА задается следующим способом:

• вершины графа, соответствуют состояниям КА.
• направленные ребра, соответствуют функциям переходов (возле каждого такое ребра указывается символ, по которому выполняется переход).
• вершина с входящим в него ребром, которое не выходит не из одного состояния, соответствует начальному состоянию.
• конечные состояния КА помечаются жирным контуром.

В виде управляющей таблицы, так:

• состояния КА располагаются в строках таблицы.
• символы распознаваемого языка - в столбцах.
• на пересечении указывается состояние в которое можно попасть из данного состояния по данному символу.

Пример КА в виде графа и в виде управляющей таблицы будет представлен ниже.

ДКА и НКА

Основное отличие ДКА и НКА состоит в том, что ДКА в процессе работы может находится только в одном состоянии, а НКА в нескольких состояниях одновременно. В качестве примера работы НКА можно привести идею американского физика Хью Эверетта от том, что любое событие разбивает мир на несколько миров, в каждом из которых это событие закончилось по-своему. Например, в одном мире Гитлер выиграл 2-ю Мир. войну, в другом – Ньютон вместо физики занялся бизнесом и открытие законов классической механики пришлось отложить лет на 50. Чтобы сделать какие-то выводы из работы автомата, следует изучить все «миры». После того как вся входная цепочка будет считана, мы полагаем, что НКА допускает данную цепочку, если он завершил работу в допускающем состоянии хотя бы в одном из множества «миров». Соответственно, автомат отвергает цепочку, если он завершил работу в недопускающем состоянии в каждом «мире». ДКА же принимает цепочку, это очевидно, если после считывания всей входной цепочки он оказывается в допускающем состоянии.

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

Построение минимального ДКА по регулярному выражению

Для начала приведем синтаксис РВ используемый в данной статье:

• конкатенация задается с помощью пробела или пустой строки(например: ab)
• объединение, с помощью символа "|"
• итерация(замыкание Клини), с помощью символа "*"

Рассмотрим пример, дано регулярное выражение:

xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)

Нужно построить минимальный ДКА по регулярному выражению и продемонстрировать распознавание корректной и некорректной цепочки.

Для начала упростим данное РВ, используя правосторонний дистрибутивный закон конкатенации относительно объединения получаем следующее РВ:

(xy* | ab | (x | a*)) (x | y*)

Теперь строим автомат по данному РВ:

По правилу преобразования конкатенации(не будем приводить правила преобразования РВ в КА, так как они довольно очевидные), получаем следующий автомат:

По правилу преобразования объединения:

По правилу преобразования конкатенации:

И в конце применяем правило преобразования замыкания и получаем εНКА:

Избавляемся от ε-переходов («звездочкой» обозначены конечные состояния):

В данном НКА состояния s3 и s5 эквивалентны, так как δ(s3, x) = δ(s5, x) = s1 и δ(s3, y) = δ(s5, y) = s5, s7. Переименовываем состояния s6 -> s5 и s7 -> s6:

Строим ДКА по НКА:

В данном ДКА состояния p1 и p5 эквивалентны, так как
δ(p1, x) = δ(p5, x) = p4 и δ(p1, y) = δ(p5, y) = p5. Переименовываем состояния p6 -> p5 и p7 -> p6:

Данный автомат является минимальным ДКА.

Пускай δ - функция переходов, то расширенная функция переходов, построенную по δ, обозначим δ’, и ω - входная цепочка.

Допустим на вход подается цепочка ω = aaax, мы ожидаем что автомат окажется в одном из допускающих состояний.

δ’(p0, ε) = p0
δ’(p0, a) = δ(δ’(p0, ε), a) = δ(p0, a) = p3
δ’(p0, aa) = δ(δ’(p0, a), a) = δ(p3, a) = p5
δ’(p0, aaa) = δ(δ’(p0, aa), a) = δ(p5, a) = p5
δ’(p0, aaax) = δ(δ’(p0, aaa), a) = δ(p5, a) = p4

p4 - допустимое конечное состояние, таким образом цепочка aaax, является корректной для данного автомата.

Теперь допустим, что ω = xyyb:

δ’(p0, ε) = p0
δ’(p0, x) = δ(δ’(p0, ε), x) = δ(p0, x) = p1
δ’(p0, xy) = δ(δ’(p0, x), y) = δ(p1, y) = p1
δ’(p0, xyy) = δ(δ’(p0, xy), y) = δ(p1, y) = p1
δ’(p0, xyyb) = δ(δ’(p0, xyy), b) = δ(p1, b) = ∅

Здесь мы видим, что если подать на вход автомату символ b, когда он находится в состоянии p1, то данный автомат умрет, следовательно цепочка xyyb - некорректна.

P. S. В данной статье был рассмотрен алгоритм построение ДКА по РВ, но существуют более удобные алгоритмы, в частности для программирования, но это уже тема для другой статьи…

Для дальнейшего изучения свойств конечных автоматов и, в частности, для решения задачи синтеза важное значение имеет следующая теорема.

Теорема 7.7 (теорема о детерминизации). Для любого конечного автомата может быть построен эквивалентный ему детерминированный конечный автомат.

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

Преобразование произвольного конечного автомата к эквивалентному детерминированному осуществляется в два этапа: сначала удаляются дуги с меткой \lambda , затем проводится собственно детерминизация.

1. Удаление λ-переходов (дуг с меткой \lambda ).

Чтобы перейти от исходного конечного автомата M=(V,Q,q_0,F,\delta) к эквивалентному конечному автомату M"=(V,Q",q_0,F",\delta") без λ-переходов, достаточно в исходном графе M проделать следующие преобразования.

а. Все состояния, кроме начального, в которые заходят только дуги с меткой \lambda , удаляются; тем самым определяется множество Q" конечного автомата M" . Понятно, что Q"\subseteq Q . При этом полагаем, что начальное состояние остается прежним.

б. Множество дуг конечного автомата M" и их меток (тем самым и функция переходов M" ) определяется так: для любых двух состояний p,r\in Q",~ p\to_{a}r имеет место тогда и только тогда, когда a\in V , а в графе M имеет место одно из двух: либо существует дуга из p в r , метка которой содержит символ a , либо существует такое состояние q , что p\Rightarrow_{\lambda}^{+}q и q\to_{a}r . При этом вершина q , вообще говоря, может и не принадлежать множеству Q" , т.е. она может и исчезнуть при переходе к автомату M" (рис. 7.11). Если же q\in Q" , то, естественно, в M" сохранится дуга (q,r) и символ a будет одним из символов, принадлежащих метке этой дуги (рис. 7.12).

Таким образом, в M" сохраняются все дуги M , метки которых отличны от \lambda и которые соединяют пару (вершин) состояний из множества Q" (не удаляемых согласно п. а). Кроме этого, для любой тройки состояний p,q,r (не обязательно различных!), такой, что p,r\in Q" и существует путь ненулевой длины из p в q , метка которого равна \lambda (т.е. путь по λ-переходам), а из q в r ведет дуга, метка которой содержит символ a входного алфавита, в M" строится дуга из p в r , метка которой содержит символ a (см. рис. 7.11).

в. Множество заключительных состояний F" конечного автомата M" содержит все состояния q\in Q" , т.е. состояния конечного автомата M , не удаляемые согласно п. а, для которых имеет место q\Rightarrow_{\lambda}^{\ast}q_f для некоторого q_f\in F (т.е. либо состояние q само является заключительным состоянием конечного автомата M , либо из него ведет путь ненулевой длины по дугам с меткой \lambda в одно из заключительных состояний конечного автомата M ) (рис. 7.13).

2. Собственно детерминизация.

Пусть M=(Q,V,q_0,F,\delta) - конечный автомат без λ-переходов. Построим эквивалентный M детерминированный конечный автомат M_1 .

Этот конечный автомат определяется таким образом, что его множество состояний есть множество всех подмножеств множества состояний конечного автомата M . Это значит, что каждое отдельное состояние конечного автомата M_1 определено как некоторое подмножество множества состояний конечного автомата M . При этом начальным состоянием нового конечного автомата (т.е. M_1 ) является одноэлементное подмножество, содержащее начальное состояние старого конечного автомата (т.е. M ), а заключительными состояниями нового конечного автомата являются все такие подмножества Q , которые содержат хотя бы одну заключительную вершину исходного конечного автомата M .

Впредь, допуская некоторую вольность речи, мы будем иногда называть состояния конечного автомата M_1 состояниями-множествами. Важно, однако, четко усвоить, что каждое такое состояние-множество есть отдельное состояние нового конечного автомата, но никак не множество его состояний. В то же время для исходного ("старого") конечного автомата M это именно множество его состояний. Образно говоря, каждое подмножество состояний старого конечного автомата "свертывается" в одно состояние нового конечного автомата*.

*Формально следовало бы определить множество Q_1 как множество, находящееся во взаимно однозначном соответствии с множеством 2^Q , но нам все-таки удобнее считать, что Q_1 совпадает с 2^Q , - ведь множеством состояний конечного автомата может быть любое непустое конечное множество.

Функция переходов нового конечного автомата определена так, что из состояния-множества S по входному символу а конечный автомат M_1 переходит в состояние-множество, представляющее собой объединение всех множеств состояний старого конечного автомата, в которые этот старый конечный автомат переходит по символу а из каждого состояния множества S . Таким образом, конечный автомат M_1 является детерминированным по построению.

Приведенное выше словесное описание можно перевести в формулы следующим образом: строим конечный автомат M_1 так, что

M_1=(Q_1,V,\{q_0\},F_1,\delta_1) , где

\begin{cases}Q_1=2^Q,\quad F_1=\{T\colon\, T\cap F\ne\varnothing,~T\in2^Q\},\\ (\forall S\subseteq Q)(\forall a\in V)\Bigl(\delta_1(S,a)= \bigcup\limits_{q\in S}\delta(q,a)\Bigr). \end{cases}

Обратим внимание на то, что среди состояний нового конечного автомата есть состояние \varnothing , причем, согласно (7.8), \delta_1(\varnothing,a)=\varnothing для любого входного символа a . Это значит, что, попав в такое состояние, конечный автомат M_1 уже его не покинет. Вообще же любое состояние q конечного автомата, такое, что для любого входного символа a имеем \delta(q,a)=q , называют поглощающим состоянием конечного автомата. Таким образом, состояние \varnothing детерминированного конечного автомата M_1 является поглощающим. Полезно заметить также, что \delta_1(S,a)=\varnothing тогда и только тогда, когда для каждого q\in S (состояния старого конечного автомата из множества состояний S ) \delta(q,a)=\varnothing , т.е. в графе M из каждого такого состояния q не выходит ни одна дуга, помеченная символом a .

Можно доказать, что полученный по такому алгоритму конечный автомат эквивалентен исходному.

Пример 7.9. Детерминизируем конечный автомат, изображенный на рис. 7.14.

Эквивалентный конечный автомат без λ-переходов изображен на рис. 7.15. Заметим, что вершина q_2 исчезает, так как в нее заходят только "пустые" дуги.

Чтобы детерминизировать полученный автомат, совершенно не обязательно выписывать все его 2^3=8 состояний, среди которых многие могут оказаться не достижимыми из начального состояния \{q_0\} . Чтобы получить достижимые из \{q_0\} состояния, и только их, воспользуемся так называемым методом вытягивания.

Этот метод в общем случае можно описать так.

В исходном конечном автомате (без пустых дуг) определяем все множества состояний, достижимых из начального, т.е. для каждого входного символа a находим множество \delta(q_0,a) . Каждое такое множество в новом автомате является состоянием, непосредственно достижимым из начального.

Для каждого из определенных состояний-множеств S и каждого входного символа a находим множество \textstyle{\mathop{\bigcup\limits_{q\in S} \delta(q,a)}\limits^{\phantom{A}^{.}}} . Все полученные на этом шаге состояния будут состояниями нового (детерминированного) автомата, достижимыми из начальной вершины по пути длины 2. Описанную процедуру повторяем до тех пор, пока не перестанут появляться новые состояния-множества (включая пустое!). Можно показать, что при этом получаются все такие состояния конечного автомата M_1 , которые достижимы из начального состояния \{q_0\} .

Для конечного автомата на рис. 7.15 имеем:

\begin{aligned}& \delta_1(\{q_0\},a)=\{q_1\};\qquad \delta_1(\{q_0\},b)=\{q_1,q_3\};\\ & \delta_1(\{q_1\},a)=\{q_1\};\qquad \delta_1(\{q_1\},b)=\{q_1\};\\ & \delta_1(\{q_1,q_3\},a)= \delta(q_1,a)\cup \delta(q_3,a)= \{q_1\}\cup\{q_1\}=\{q_1\};\\ & \delta_1(\{q_1,q_3\},b)= \delta(q_1,b)\cup \delta(q_3,b)= \{q_1\}\cup\{q_1\}=\{q_1\}. \end{aligned}

Так как новых состояний-множеств больше не появилось, процедура "вытягивания" на этом заканчивается, и мы получаем граф, изображенный на рис. 7.16.

Дополнение регулярного языка

Одним из важных теоретических следствий теоремы о детерминизации является следующая теорема.

Теорема 7.8. Дополнение регулярного языка есть регулярный язык.

Пусть L - регулярный язык в алфавите V . Тогда дополнение языка L (как множества слов) есть язык \overline{L}=V^{\ast}\setminus L .

Согласно теореме 7.7, для регулярного языка L может быть построен детерминированный конечный автомат M , допускающий L . Поскольку в детерминированном автомате из каждой вершины по каждому входному символу определен переход в точности в одну вершину, то, какова бы ни была цепочка x в алфавите V , для нее найдется единственный путь в M , начинающийся в начальном состоянии, на котором читается цепочка x . Ясно, что цепочка x допускается автоматом M , то есть x\in L(M) , тогда и только тогда, когда последнее состояние указанного пути является заключительным. Отсюда следует, что цепочка x\notin L(M) тогда и только тогда, когда последнее состояние указанного пути не заключительное. Но нам как раз и нужен конечный автомат M" , который допускает цепочку x тогда и только тогда, когда ее не допускает исходный конечный автомат M . Следовательно, превращая каждое заключительное состояние M в не заключительное и наоборот, получим детерминированный автомат, допускающий дополнение языка L .

Доказанная теорема позволяет строить конечный автомат, не допускающий определенное множество цепочек, следующим методом: строим сначала автомат, допускающий данное множество цепочек, затем детерминизируем его и переходим к автомату для дополнения так, как это указано в доказательстве теоремы 7.8.

Пример 7.10. а. Построим конечный автомат, допускающий все цепочки в алфавите \{0;1\} , кроме цепочки 101.

Сначала построим конечный автомат, допускающий единственную цепочку 101. Этот автомат приведен на рис. 7.17.

Этот автомат квазидетерминированный, но не детерминированный, так как он не полностью определен. Проведем его детерминизацию и получим детерминированный эквивалентный конечный автомат, изображенный на рис. 7.18.

И наконец, переходя к дополнению (и переименовывая состояния), получим автомат, изображенный на рис. 7.19.

Обратим внимание, что в полученном автомате все вершины, кроме вершины s_3 , являются заключительными.

Заметим также, что переход к дополнению, о котором идет речь в доказательстве теоремы 7.8, может быть проведен только в детерминированном автомате. Если бы мы поменяли ролями заключительные и незаключительные вершины в автомате, изображенном на рис. 7.17, то получили бы автомат, допускающий язык \{\lambda,1,10\} , который не является - как нетрудно сообразить - множеством всех цепочек, отличных от цепочки 101.

Отметим также, что конечный автомат на рис. 7.19 допускает все цепочки, содержащие вхождение цепочки 101, но не совпадающие с самой этой цепочкой. Вот, например, путь, несущий цепочку 1011: s_0,s_1,s_2,s_3,t .

б. Построим конечный автомат, допускающий все цепочки в алфавите \{0;1\} , кроме тех, которые содержат вхождение цепочки 101. Рассмотрим язык L , каждая цепочка которого содержит вхождение цепочки 101. Его можно задать так:

L=(0+1)^{\ast}101(0+1)^{\ast}.

Нам нужно построить автомат для дополнения языка L .

Непосредственно по регулярному выражению в этом случае легко построить конечный автомат, допускающий язык L (рис. 7.20).

Затем методом "вытягивания" проведем детерминизацию. Результат детерминизации представлен на рис. 7.21.

Для полного решения задачи осталось только на рис. 7.21 поменять ролями заключительные и не заключительные вершины (рис. 7.22).

в. Обсудим идею построения конечного автомата, допускающего те и только те цепочки в алфавите \{0;1\} , которые не начинаются цепочкой 01 и не заканчиваются цепочкой 11 (т.е. не разрешаются цепочки вида 01x и цепочки вида y11 , каковы бы ни были цепочки x,y\in\{0;1\} ).

В этом случае дополнением языка, для которого нужно построить конечный автомат, является множество всех таких цепочек нулей и единиц, которые начинаются цепочкой 01 или заканчиваются цепочкой 11. Допускающий это множество цепочек автомат строится как автомат для объединения 01(0+1)^{\ast}+(0+1)^{\ast}11 тем способом, который изложен при доказательстве теоремы Клини (см. теорему 7.6).

Из свойства замкнутости класса регулярных языков относительно дополнения (см. теорему 7.8) немедленно вытекает замкнутость этого класса относительно пересечения, теоретико-множественной и симметрической разности.

Следствие 7.3. Для любых двух регулярных языков L_1 и L_2 справедливы следующие утверждения:

1) пересечение L_1\cap L_2 регулярно;
2) разность L_1\setminus L_2 регулярна;
3) симметрическая разность L_1\vartriangle L_2 регулярна.

Справедливость утверждений вытекает из тождеств:

\begin{aligned} &{\scriptstyle{\mathsf{1)}}}\quad L_1\cap L_2= \overline{\overline{L_1} \cup\overline{L_2}}\,;\\ &{\scriptstyle{\mathsf{2)}}}\quad L_1\setminus L_2= L_1\cap \overline{L_2}\,;\\ &{\scriptstyle{\mathsf{3)}}}\quad L_1\,\triangle\,L_2 = (L_1\cup L_2)\setminus (L_1\cap L_2).\end{aligned}

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

Согласно определению 7.10, конечные автоматы эквивалентны, если допускаемые ими языки совпадают. Поэтому, чтобы убедиться в эквивалентности автоматов M_1 и M_2 , достаточно доказать, что симметрическая разность языков L(M_1) и L(M_2) пуста. Для этого, в свою очередь, достаточно построить автомат, допускающий эту разность, и убедиться в том, что допускаемый им язык пуст. В общем случае проблему распознавания того, что язык конечного автомата пуст, называют проблемой пустоты для конечного автомата. Чтобы решить эту проблему, достаточно найти множество заключительных состояний автомата, достижимых из начального состояния. Так как конечный автомат - это ориентированный граф, то решить такую проблему можно, например, с помощью, поиска в ширину. Язык, допускаемый конечным автоматом, пуст тогда и только тогда, когда множество заключительных состояний, достижимых из начального состояния, пусто. Практически эквивалентность конечных автоматов предпочтительнее распознавать, используя алгоритм минимизации, но сейчас нам важно подчеркнуть, что принципиальная возможность решить проблему эквивалентности вытекает из теоремы 7.7 и ее алгебраических следствий.

В этом разделе мы сформируем важные вопросы, связанные с регулярными языками. Сначала нужно разобраться, что значит задать вопрос о некотором языке. Типичный язык бесконечен, поэтому бессмысленно предъявлять кому-нибудь цепочки этого языка и задавать вопрос, требующий проверки бесконечного множества цепочек. Гораздо разумнее использовать одно из конечных представлений языка, а именно: ДКА, НКА, ε- НКА или регулярное выражение.

Очевидно, что представленные таким образом языки будут регулярными. В действительности не существует способа представления абсолютно произвольных языков. В следующих главах предлагаются конечные методы описания более широких классов, чем класс регулярных языков, и можно будет рассматривать вопросы о языках из них. Однако алгоритмы разрешения многих вопросов о языках существуют только для класса регулярных языков. Эти же вопросы становятся “неразрешимыми” (не существует алгоритмов ответов на эти вопросы), если они поставлены с помощью более “выразительных” обозначений (используемых для выражения более широкого множества языков), чем представления, разработанные для регулярных языков.

Начнем изучение алгоритмов для вопросов о регулярных языках, рассмотрев способы, которыми одно представление языка преобразуется в другое. В частности, рассмотрим временную сложность алгоритмов, выполняющих преобразования. Затем рассмотрим три основных вопроса о языках.

1. Является ли описываемый язык пустым множеством?

2. Принадлежит ли некоторая цепочка w представленному языку?

3. Действительно ли два разных описания представляют один и тот же язык? (Этот вопрос часто называют “эквивалентностью” языков.)

2.1 Преобразования различных представлений языков

Каждое из четырех представлений регулярных языков можно преобразовать в любое из остальных трех. На рис. 3.1 представлены переходы от одного представления к другому. Хотя существуют алгоритмы для любого из этих преобразований, иногда нас интересует не только осуществимость некоторого преобразования, но и время, необходимое для его выполнения. В частности, важно отличать алгоритмы, которые занимают экспоненциальное время (время как функция от размера входных данных) и, следовательно, могут быть выполнены только для входных данных сравнительно небольших размеров, от тех алгоритмов, время выполнения которых является линейной, квадратичной или полиномиальной с малой степенью функцией от размера входных данных. Последние алгоритмы “реалистичны”, так как их можно выполнить для гораздо более широкого класса экземпляров задачи. Рассмотрим временную сложность каждого из обсуждавшихся преобразований.

Преобразование НКА в ДКА

Время выполнения преобразования НКА или ε-НКА в ДКА может быть экспоненциальной функцией от количества состояний НКА. Начнем с того, что вычисление ε-замыкания n состояний занимает время O(n3). Необходимо найти все дуги с меткой ε, ведущие от каждого из n состояний. Если есть n состояний, то может быть не более n2 дуг. Разумное использование системных ресурсов и хорошо спроектированные структуры данных гарантируют, что время исследования каждого состояния не превысит O(n2). В действительности для однократного вычисления всего ε-замыкания можно использовать такой алгоритм транзитивного замыкания, как алгоритм Уоршалла (Warshall)5.

После вычисления ε-замыкания можно перейти к синтезу ДКА с помощью конструкции подмножеств. Основное влияние на расход времени оказывает количество состояний ДКА, которое может равняться 2n. Для каждого состояния можно вычислить переходы за время O(n3), используя ε-замыкание и таблицу переходов НКА для каждого входного символа. Предположим, нужно вычислить δ({q1, q2, …, qk}, a) для ДКА. Из каждого состояния qi можно достичь не более n состояний вдоль путей с меткой ε, и каждое из этих состояний может иметь не более, чем n дуг с меткой a. Создав массив, проиндексированный состояниями, можно вычислить объединение не более n множеств, состоящих из не более, чем n состояний, за время, пропорциональное n2.

Таким способом для каждого состояния qi можно вычислить множество состояний, достижимых из qi вдоль пути с меткой a (возможно, включая дуги, отмеченные ε). Поскольку k ≤ n, то существует не более n таких состояний qi, и для каждого из них вычис-ление достижимых состояний занимает время O(n2). Таким образом, общее время вычисления достижимых состояний равно O(n3). Для объединения множеств достижимых состояний потребуется только O(n2) дополнительного времени, следовательно, вычисление одного перехода ДКА занимает время O(n3).

Заметим, что количество входных символов считается постоянным и не зависит от n. Таким образом, как в этой, так и в других оценках времени работы количество входных символов не рассматривается. Размер входного алфавита влияет только на постоянный коэффициент, скрытый в обозначении “О большого”.

Итак, время преобразования НКА в ДКА, включая ситуацию, когда НКА содержит ε-переходы, равно O(n32n). Конечно, на практике обычно число состояний, которые строятся, намного меньше 2n. Иногда их всего лишь n. Поэтому можно установить оценку времени работы равной O(n3s), где s - это число состояний, которые в действительности есть у ДКА.

Преобразование ДКА в НКА

Это простое преобразование, занимающее время O(n) для ДКА с n состояниями. Все, что необходимо сделать, - изменить таблицу переходов для ДКА, заключив в скобки {} состояния, а также добавить столбец для ε, если нужно получить ε-НКА. Поскольку число входных символов (т.е. ширина таблицы переходов) считается постоянным, копирование и обработка таблицы занимает время O(n).

Преобразование автомата в регулярное выражение

Каждом из n этапов (где n - число состояний ДКА) размер конструируемого регулярного выражения может увеличиться в четыре раза, так как каждое выражение строится из четырех выражений предыдущего цикла. Таким образом, простая запись n3 выражений может занять время O(n34n). Улучшенная конструкция из раздела 3.2.2 уменьшает постоянный коэффициент, но не влияет на экспоненциальность этой задачи (в наихудшем случае).

Аналогичная конструкция требует такого же времени работы, если преобразуется НКА, или даже ε-НКА, но это здесь не доказывается. Однако использование конструкции для НКА имеет большое значение. Если сначала преобразовать НКА в ДКА, а затем ДКА - в регулярное выражение, то на это потребуется время O(n34n32n), которое является дважды экспоненциальным.

Преобразование регулярного выражения в автомат

Для преобразования регулярного выражения в ε-НКА потребуется линейное время. Необходимо эффективно проанализировать регулярное выражение, используя метод, занимающий время O(n) для регулярного выражения длины n6. В результате получим дерево с одним узлом для каждого символа регулярного выражения (хотя скобки в этом дереве не встречаются, поскольку они только управляют разбором выражения).

Полученное дерево заданного регулярного выражения можно обработать, конструируя ε-НКА для каждого узла. Правила преобразования регулярного выражения, представленные в разделе 3.2.3, никогда не добавляют более двух состояний и четырех дуг для каждого узла дерева выражения. Следовательно, как число состояний, так и число дуг результирующего ε-НКА равны O(n). Кроме того, работа по созданию этих элементов в каждом узле дерева анализа является постоянной при условии, что функция, обрабатывающая каждое поддерево, возвращает указатели в начальное и допускающие состояния этого автомата.

Приходим к выводу, что построение ε-НКА по регулярному выражению занимает время, линейно зависящее от размера выражения. Можно исключить ε-переходы из ε- НКА с n состояниями, преобразовав его в обычный НКА за время O(n3) и не увеличив числа состояний. Однако преобразование в ДКА может занять экспоненциальное время.

Рассмотрим алгоритм построения по регулярному выражению недетерминированного конечного автомата, допускающего тот же язык.

Алгоритм 3.1 . Построение недетерминированного конечного автомата по регулярному выражению.

Вход . Регулярное выражение r в алфавите T .

Выход . НКА M , такой что L(M) = L(r) .

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

Построение детерминированного конечного автомата по недетерминированному

Рассмотрим алгоритм построения по недетерминированному конечному автомату детерминированного конечного автомата, допускающего тот же язык.

Алгоритм 3.2 . Построение детерминированного конечного автомата по недетерминированному.

Вход . НКА M = (Q, T, D, q 0 , F) .

Выход . ДКА .

Метод . Каждое состояние результирующего ДКА - это некоторое множество состояний исходного НКА.

В алгоритме будут использоваться следующие функции: - множество состояний НКА, достижимых из состояний, входящих в R , посредством только переходов по e , то есть множество

Множество состояний НКА, в которые есть переход на входе a для состояний из R , то есть множество

Вначале Q" и D" пусты. Выполнить шаги 1-4:

(1) Определить .

(2) Добавить в Q" как непомеченное состояние

(3) Выполнить следующую процедуру:

(4) Определить .

Пример 3.6 . Результат применения алгоритма 3.2 приведен на рис. 3.10 .

Построение детерминированного конечного автомата по регулярному выражению

Приведем теперь алгоритм построения по регулярному выражению детерминированного конечного автомата, допускающего тот же язык [?] .

Пусть дано регулярное выражение r в алфавите T . К регулярному выражению r добавим маркер конца: (r)# . Такое регулярное выражение будем называть пополненным. В процессе своей работы алгоритм будет использовать пополненное регулярное выражение.

Алгоритм будет оперировать с синтаксическим деревом для пополненного регулярного выражения (r)#, каждый лист которого помечен символом , а каждая внутренняя вершина помечена знаком одной из операций: (конкатенация), | (объединение), * (итерация).

Каждому листу дерева (кроме e -листьев) присвоим уникальный номер, называемый позицией, и будем использовать его, с одной стороны, для ссылки на лист в дереве, и, с другой стороны, для ссылки на символ, соответствующий этому листу. Заметим, что если некоторый символ используется в регулярном выражении несколько раз, он имеет несколько позиций.

Обойдем дерево T снизу-вверх слева-направо и вычислим четыре функции: nullable,firstpos, lastpos и followpos . Три первые функции - nullable, firstpos и lastpos - определены на узлах дерева, а followpos - на множестве позиций. Значением всех функций, кроме nullable , является множество позиций. Функция followpos вычисляется через три остальные функции.

Функция firstpos(n) для каждого узла n синтаксического дерева регулярного выражения дает множество позиций, которые соответствуют первым символам в подцепочках , генерируемых подвыражением с вершиной в n . Аналогично, lastpos(n) дает множество позиций, которым соответствуют последние символы в