Язык регулярных выражений

Язык регулярных выражений предложен американским ученым С. К. Клини в 1956 г. и усовершенствован советским ученым В. М. Глуш­ковым. Подробно язык регулярных выражений рассмотрен в [3, 4].

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

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

Пусть на вход автомата S, предварительно установленного в начальное состояние a₀ Î A, поступает слово, составленное из символов входного алфавита X, которое вызывает на выходе автомата появление символа y_i Î Y (рис. 6.1).

Рис. 6.1. Поступление на вход автомата слов входного алфавита

Алфавиты автомата определены следующим образом:

A = {a₀, a₁, … , a_{n – 1}}

X = {x₁, x₂, … , x_k} . (6.1)

Y = {y₁, y₂, … , y_p}

Входные слова, на которые автомат откликается выходным символом y_i, можно объединить во множество H_i (x₁, x₂, … , x_k). Это множество называется событием, представленным в автомате S выходным символом (буквой) y_i.

Слово – конечная последовательность символов, принадлежащих некоторому множеству символов (алфавиту автомата). Если, например, алфавит Y содержит три символа y₁, y₂, y₃, т. е.

Y = {y₁, y₂, y₃}, (6.2)

то возможны слова y₁, y₁y₁y₁, y₂y₁, y₃y₃y₂y₁y₂, y₃, y₃y₁y₂y₁ и т. д.

Пустое слово – слово нулевой длины. Пустое слово принято обозначать буквой e. Для любого слова d выполняется соотношение ed = de = d. Считается, что пустое слово принадлежит любому алфавиту символов. Наличие пустого слова на входе автомата означает отсутствие входных сигналов.

Событие – произвольное множество слов конечной длины, составленных из букв входного алфавита X. В дальнейшем событие будем обозначать буквой H.

Элементарное событие во входном алфавите X – это какое-либо из (k + 1)-го элементарных событий x₁, x₂, … , x_k, e, где e – пустое слово

X = {x₁, x₂, … , x_k}. (6.3)

События называют пересекающимися, если они имеют общие слова, и непересекающимися, если таких слов нет. При абстрактном синтезе цифровых автоматов рассматриваются только непересекающиеся события, для которых выполняется условие однозначности выходной функции автомата.

Полностью определенный автомат можно задать таблицей, устанавливающей соответствие между попарно непересекающимися событиями
H_i(x₁, x₂, … , x_k) и выходными символами y₁, … , y_i, … , y_p (табл. 6.1). Аналогичную таблицу для частичного (не полностью определенного) автомата необходимо дополнить событием H_запрзапрещенных входных слов (табл. 6.2).

Конкатенацией (склеиванием) двух слов H₁ и H₂ называется слово H, которое получается в результате непосредственного слияния слова H₁, стоящего слева, и слова H₂, стоящего справа. Например, если

H₁ = x₁x₂x₅; (6.4)

H₂ = x₄x₃x₄, (6.5)

то конкатенация H₁ и H₂ – это слово:

H = x₁x₂x₅x₄x₃x₄, (6.6)

а конкатенация H₂ и H₁– это слово:

H = x₄x₃x₄x₁x₂x₅. (6.7)

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

Итерацией события H называется событие [H], состоящее из пустого слова e и всех слов вида H, HH, HHH и т. д. до бесконечности. Итерация пустого события равна пустому событию: [e] = e. Итерация события H определяется так:

[H] = [e] Ú H Ú HH Ú HHH Ú ¼ (6.8)

Регулярное событие может быть задано регулярным выражением, т. е. формулой, содержащей символы e, символы входного алфавита и знаки регулярных операций над ними. Одно и то же регулярное событие может быть представлено разными эквивалентными регулярными выражениями. Для этого используются тождественные соотношения алгебры событий, которыми можно пользоваться при преобразованиях и упрощениях формул [4].

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

Регулярные выражения позволяют построить отмеченную таблицу состояний автомата Мура по методике, изложенной в [4]. В общих чертах идею перехода от регулярных выражений к табличному заданию автомата можно пояснить следующим образом. Множество событий связано с множеством выходных сигналов. Выходные сигналы автомата Мура зависят только от состояний автомата. Поэтому каждому выходному сигналу из множества выходных сигналов Y в автомате Мура можно поставить в соответствие конкретное состояние автомата Мура. Различные подмножества множества событий, которые не представляют ни одно из событий, можно считать пустым множеством событий. Если множество событий пусто, то автомат выдает пустое выходное слово e. Таким образом, если ни одно событие не наступило, автомат не выдает ни одного сигнала из множества выходных сигналов Y.

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