УДК 519.178
Обобщённые недетерминированные конечные автоматы
,
Аннотация
В статье рассматривается формализм, предназначенный для представления специального расширения класса конечных автоматов – т. н. обобщённых недетерминированных конечных автоматов. Из изложенных в статье алгоритмов эквивалентного преобразования определяемых нами автоматов и аналога теоремы Клини для них вытекает не столько эквивалентность их и обычных конечных автоматов (эта эквивалентность очевидна априори), сколько возможность определения операции дополнения (и вообще обобщённых регулярных выражений) обычными «автоматными» методами.
Ключевые слова
Недетерминированные конечные автоматы, обобщённые регулярные выражения, алгоритмы эквивалентного преобразования, аналог теоремы Клини.
Abstract
The paper deals with the formalism used for representing a special class of extensions of finite automata, so-called generalized nondeterministic finite automata. Considered algorithms of equivalent transformations of such automata and also their analogue of Kleene theorem gives not only the equivalence between such and usual finite automata (such equivalence is obvious a priori), but also the possibility of defining the complement operation (and, generally, the generalized regular expressions) by usual “automata” methods.
Key words
Nondeterministic finite automaton, generalized regular expressions, algorithms of equivalent transformation, analogue of Kleene theorem.
1. ВВЕДЕНИЕ
В данной статье рассматривается формализм, предназначенный для представления специального расширения класса недетерминированных конечных автоматов. Статья является обобщением нескольких предыдущих публикаций авторов – в первую очередь [1,2,3]. При этом кроме более подробного изложения рассмотренных в [1,2,3] понятий и доказанных фактов, в настоящей статье также описывается метод построения конкретного обобщённого автомата, который определяет (среди прочих) заданное обобщённое регулярное выражение. Этот метод построения фактически завершает описание рассматриваемого нами формализма.
Итак, мы будем рассматривать формализм для задания автоматов, применяемых для описания обобщённых регулярных выражений (generalized regular expressions), определяемых нами близко к [4]. С помощью предложенного формализма автоматы могут описывать не только операции, обычные для регулярных выражений, но и применяемую для обобщённых регулярных выражений операцию дополнения. Очевидно, что при этом мы описываем регулярные языки.
Такие расширенные возможности для описания регулярных языков (иными словами – расширение класса недетерминированных конечных автоматов) могут быть полезны в некоторых приложениях, в частности, в контекстном поиске. С помощью обобщённых конечных автоматов и обобщённых регулярных выражений можно, например, с помощью небольшого числа примитивов определить язык, который содержит все слова над рассматриваемым алфавитом – за исключением некоторого множества, определённого пользователем.
В данной статье сформулированы основные определения рассматриваемых формализмов, а также изложены алгоритмы преобразования для них. Из этих действий вытекает не столько их эквивалентность (она очевидна с самого начала), сколько возможность быстрого определения одного и того же класса регулярных языков; в первую очередь – определения операции дополнения «обычными автоматными методами».
2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПРИМЕРЫ
Обобщёнными регулярными выражениями (ОРВ), согласно [4], будем называть регулярные выражения, для которых дополнительно определена операция дополнения ~. Подробнее. Пусть задан алфавит Σ. Тогда:
1) ОРВ 
определяет регулярный язык ;
2) для каждой буквы 
ОРВ a определяет регулярный язык {a}.
Далее, пусть p и q – обобщённые регулярные выражения, определяющие регулярные языки P и Q соответственно. Тогда:
3) ОРВ (p+q) определяет регулярный язык 
;
4) ОРВ (p·q) определяет регулярный язык PQ;
5) ОРВ (p*) определяет регулярный язык P*;
6) ОРВ (~p) определяет регулярный язык 
.
Определение 2.1. Обобщённое регулярное выражение – это то и только то, что может быть образовано с помощью применения в каком-либо порядке перечисленных шести правил; при этом каждое из этих правил может быть применено любое (конечное) число раз.
Далее определим один из возможных вариантов обобщённого недетерминированного конечного автомата (ОНКА).
Определение 2.2. Назовём обобщённым недетерминированным конечным автоматом кортеж
, (2.1)
где:
· Q – конечное множество состояний автомата;
· Σ – рассматриваемый алфавит;
· δ – функция переходов 
;
· 
– множество стартовых состояний;
· 
– множество финальных состояний;
· 
– конечное множество, где 
– множество натуральных чисел;
· 
и 
– функции вида 
, для которых выполняются условия:
и
.
Множество T и функции 
определяют языки-дополнения; ниже будет дано определение самих соответствующих языков.
Как и обычный конечный автомат, обобщённый конечный автомат может быть задан в виде помеченного орграфа. Определим граф переходов для автомата (2.1) следующим образом. Множества Q, S, F и функция переходов δ задаются аналогично графу переходов для обычного конечного автомата. Если 
, то в графе переходов имеется дуга из вершины q в вершину p, помеченная –i. Если 
, то в графе имеется дуга из вершины q в вершину p, помеченная +i. Пример графа переходов обобщённого конечного автомата приведён на рисунке 2.1:
Рисунок 2.1. Пример графа переходов обобщённого конечного автомата.
Определим язык, задаваемый ОНКА. 
рассмотрим состояния 
множества Q, такие что
(2.2)
Определение 2.3. Пусть G – обобщённый конечный автомат (2.1). Для некоторых 
обозначим
; (2.3)
Определение 2.4. Пусть G – ОНКА (2.1). Тогда 
будет соответствовать обычному конечному автомату.
Определение 2.5. Пусть G – обобщённый конечный автомат (2.1). Для 
обозначим 
, где:
; (2.4)
;
Определение 2.6. Язык 
автомата (2.1) определяется следующим образом:
(2.5)
Согласно определению 2.6 очевидно, что для любого обобщённого автомата G, определяемого согласно (2.1), задаваемый им язык 
регулярен.
Продолжим рассмотрения примера автомата, приведённого на рис. 2.1. Подробности построения соответствующего ОРВ согласно определению 2.6 опускаем; кратко скажем лишь, что язык этого ОНКА описывает множество слов над алфавитом {a,b}, в которых нет двух стоящих подряд букв b.
3. ПОСТРОЕНИЕ ОБОБЩЁННОГО КОНЕЧНОГО АВТОМАТА ПО ЗАДАННОМУ ОБОБЩЁННОМУ РЕГУЛЯРНОМУ ВЫРАЖЕНИЮ
Для «классических» регулярных выражений и конечных автоматов давно известно, что эти варианты представления регулярного языка эквивалентны. Т. е. для каждого конечного автомата существует регулярное выражение, задающее тот же язык, и наоборот.
Эквивалентность ОНКА и ОРВ следует просто из регулярности языка, определяемого согласно (2.5). Однако в этом и следующем разделах мы опишем конкретные алгоритмы построения ОНКА по заданному ОРВ (и наоборот, ОРВ по заданному ОНКА). Таким образом мы получим возможность определения операции дополнения (и вообще обобщённых регулярных выражений) «обычными автоматными методами». При этом, как было отмечено выше, с помощью небольшого числа примитивов можно, например, определить язык, который содержит все слова над рассматриваемым алфавитом – за исключением некоторого множества (возможно, бесконечного, но обязательно регулярного), определённого пользователем.
Итак, сначала построим ОНКА, эквивалентный заданному ОРВ. Автомат будем строить по индукции. Обозначим через 
автомат, эквивалентный выражению r. Поскольку любой автомат можно легко привести к эквивалентному автомату с одним входом и одним выходом, будем считать, что все построенные автоматы имеют ровно один вход и один выход.
Графы переходов для ОНКА 
и 
показаны на рис. 3.1.
|
|
Рисунок 3.1. Графы переходов автоматов 
и 
Далее, пусть r и p – некоторые ОРВ, для которых уже построены эквивалентные автоматы
, 
. Эти автоматы изображены на рис. 3.2.
Рисунок 3.2. Графы переходов автоматов 
и 
Тогда автоматы 
и 
построим согласно рис. 3.3.
, где
, где 
При этом будем считать, что 
, т. к. этого условия легко добиться с помощью элементарных преобразований.
Рисунок 3.3. Графы переходов автоматов 
и 
Автоматы 
и 
построим согласно рис. 3.4.
Рисунок 3.4. Графы переходов автоматов 
и 
, где
, где 
, 
, 
Корректность проведённых построений очевидна. Итак, мы привели индуктивный алгоритм построения эквивалентного ОНКА для заданного ОРВ.
4. ПОСТРОЕНИЕ ОБОБЩЁННОГО РЕГУЛЯРНОГО ВЫРАЖЕНИЯ ПО ЗАДАННОМУ ОБОБЩЁННОМУ КОНЕЧНОМУ АВТОМАТУ
Теперь докажем возможность построения ОРВ по заданному ОНКА – т. е. фактически рассмотрим аналог теоремы Клини «в обобщённом случае». При этом необходимы несколько следующих замечаний.
Во-первых, сама возможность построения следует из определения 2.6; здесь же мы покажем возможность построения разных ОРВ (т. е. фактически ОРВ, соответствующих заданному ОНКА, но с другими функциями 
и 
) – что аналогично обычным доказательствам теоремы Клини ([4] и мн. др.).
Во-вторых, аналогия здесь далеко не полная: «в классическом случае» теорема Клини доказывает регулярность языка автомата – мы же, зная эту регулярность заранее, доказываем более простой факт, а именно – корректность построения конкретных ОРВ.
Также отметим, что согласно материалу предыдущего раздела построенный ОНКА определяет, вообще говоря, несколько ОРВ – и при этом одно из них совпадает с заданным.
Как известно, в различных вариантах доказательства «обычной» теоремы Клини содержится не только доказательство регулярности языка, определяемого автоматом, но и алгоритм построения регулярного выражения по заданному автомату. Регулярное выражение при этом строится в соответствие с инъективной функцией, определяющей порядок состояний автомата. Для различных вариантов инъективной функции в результате получаются различные регулярные выражения, но все они определяют один и тот же регулярный язык – язык, задаваемый исходным конечным автоматом.
Аналогичные построения производятся и в нашем, «обобщённом» случае. При этом мы доказываем ещё и то, что при разном порядке выбора вершин (для построения ОРВ по заданному ОНКА) мы получаем различные описания одного и того же регулярного языка. Значит, все построенные таким для данного ОНКА выражения эквивалентны и определяют тот же язык, что и автомат.
Итак, опишем аналогичный алгоритм построения обобщённых регулярных выражений по обобщённому конечному автомату в соответствии с инъективной функцией и докажем, что все построенные выражения определяют тот же регулярный язык, что и автомат. Будем обозначать такие выражения 
, где G – исходный автомат (2.1). При фиксированном 
будем писать 
.
Для заданного автомата G рассмотрим произвольную инъективную функцию 
. Будем считать q < r, если 
. Зафиксируем на данном этапе автомат G и функцию
.
Для каждой пары состояний 
(возможно s = f), рассмотрим автомат 
, где
, 
.
Функция переходов 
строится следующим образом:
тогда и только тогда, когда 
.
Рассмотрим язык
(4.1)
Если s = f , будем кратко обозначать 
и 
соответственно. Тогда язык автомата G можно записать в виде
(4.2)
Далее построим регулярные выражения 
, 
, определяющие языки 
и . Сделаем это по индукции по 
. Для этого сначала для каждой пары состояний 
и 
определим обобщённое регулярное выражение 
:
1. Если 
, то 
, где 
– автомат (2.4).
2. Иначе 
.
При этих обозначениях определяем
Теперь запишем выражения , .
Если 
, то
(4.3)
Если 
, то
(4.4)
Если s = f, то:
(4.5)
Чтобы построить выражения 
, построим выражения 
по индукции по 
.
Пусть i = 1. Тогда 
. Выражение 
строится по алгоритму из «обычной» теоремы Клини.
Теперь предположим, что выражения 
уже построены для всех значений j < i. Тогда
(4.6)
Здесь выражения 
и 
построены по теореме Клини, а 
– по предположению индукции.
Таким образом, у нас есть алгоритм построения выражений 
. Пусть теперь известно, что все выражения из правых частей (4.4) и (4.5) уже построены. Тогда регулярное выражение, определяющее язык автомата (4.2), можно записать в виде
(4.7)
Из этого следует, что мы определили алгоритм построения обобщённого регулярного выражения по заданному автомату G в соответствии с некоторой инъективной функцией , и полученные описанным образом все такие возможные выражения всегда определяют тот же язык, что и автомат G согласно определению 2.6. Итак, мы сформулировали алгоритм построения ОНКА по ОРВ, а также алгоритм построения ОРВ по ОНКА. В результате было доказано, что данные формализмы для описания регулярного языка эквивалентны.
5. ЗАКЛЮЧЕНИЕ.
Итак, мы привели возможный подход к описанию обобщённых регулярных выражений с помощью расширения класса недетерминированных конечных автоматов. Отметим, что хотя определение обобщения автоматов мало похоже на рассматривавшееся в [5] – но, в то же время многие языки могут быть определены этими двумя обобщениями с помощью практически одних и тех же последовательностей примитивов.
СПИСОК ЛИТЕРАТУРЫ
1. С. Баумгертнер, Б. Мельников. Мультиэвристический подход к проблеме звёздно-высотной минимизации недетерминированных конечных автоматов. – Вестник Воронежского государственного университета. Серия: Cистемный анализ и информационные технологии, 2010. – №1. – C.5–7.
2. С. Баумгертнер, Б. Мельников. Математическая модель автоматов для обобщённых регулярных выражений. – В кн.: «Эвристические алгоритмы и распределённые вычисления в прикладных задачах» (колл. монография), Тольятти, изд-во ТГУ, 2012, ISBN -077-8. – С.16–23.
3. С. Баумгертнер. Аналог теоремы Клини для обобщённых недетерминированных конечных автоматов. – Вектор науки Тольяттинского государственного университета, 2012. – №4 (22) . – С.23–25.
4. А. Саломаа. Жемчужины теории формальных языков. – М.: Мир, 1986. – 159 с.
5. B. Melnikov. Extended nondeterministic finite automata. – Fundamenta Informaticae, 104:3 (2010), 255–265.
6. B. Melnikov, A. Vakhitova. Some more on the finite automata. – J. of Applied Math. and Comp. (The Korean J. of Comp. Appl. Math.), 5:3 (1998), 495–506.
7. B. Melnikov. Once more on the edge-minimization of nondeterministic finite automata and the connected problems. – Fundamenta Informaticae, 104:3 (2010), 267–283.
REFERENCES
1. S. Baumgärtner, B. Melnikov. Multiheuristics approach to the problem of the star-height minimization of nondeterministic finite automata. – Vestnik (Voronezh State Univ Ed.). Ser.: Systems analysis and information technologies, 2010. – No.1. – P.5–7 (in Russian).
2. S. Baumgärtner, B. Melnikov. A mathematical model of automata for generalized regular expressions. – In: “Heuristic algorithms and distributed computing in applied problems” (collective monograph), Togliatti State Univ. Ed., 2012, ISBN -077-8. – P.16–23 (in Russian).
3. S. Baumgärtner. Analogue of Kleene theorem for generalized nondeterministic finite automata. – Vektor Nauki (Togliatti State Univ Ed.), 2012, No. 4 (in Russian, in printing).
4. A. Salomaa. Jewels of Formal Language Theory. – Computer Sci. Press, 1981. – 144 p.
5. B. Melnikov. Extended nondeterministic finite automata. – Fundamenta Informaticae, 104:3 (2010), 255–265.
6. B. Melnikov, A. Vakhitova. Some more on the finite automata. – J. of Applied Math. and Comp. (The Korean J. of Comp. Appl. Math.), 5:3 (1998), 495–506.
7. B. Melnikov. Once more on the edge-minimization of nondeterministic finite automata and the connected problems. – Fundamenta Informaticae, 104:3 (2010), 267–283.
