close

Вход

Забыли?

вход по аккаунту

?

Обобщенные недетерминированные конечные автоматы.

код для вставкиСкачать
Известия высших учебных заведений. Поволжский регион
УДК 519.178
С. В. Баумгертнер, Б. Ф. Мельников
ОБОБЩЕННЫЕ НЕДЕТЕРМИНИРОВАННЫЕ
КОНЕЧНЫЕ АВТОМАТЫ
Аннотация. Рассматривается формализм, предназначенный для представления
специального расширения класса конечных автоматов – так называемых
обобщенных недетерминированных конечных автоматов. Из изложенных
в статье алгоритмов эквивалентного преобразования определяемых нами автоматов и аналога теоремы Клини для них вытекает не столько эквивалентность их и обычных конечных автоматов (эта эквивалентность очевидна априори), сколько возможность определения операции дополнения (и вообще
обобщенных регулярных выражений) обычными «автоматными» методами.
Также в статье описан метод построения конкретного обобщенного автомата,
который определяет заданное обобщенное регулярное выражение. Данный
метод вытекает из доказательства аналога теоремы Клини. Представленные
расширенные возможности для описания регулярных языков могут быть полезны в некоторых приложениях, например, в контекстном поиске.
Ключевые слова: недетерминированные конечные автоматы, обобщенные регулярные выражения, алгоритмы эквивалентного преобразования, аналог теоремы Клини.
S. V. Baumgertner, B. F. Mel'nikov
GENERALIZED INDETERMINISTIC FINITE AUTOMATA
Abstract. The article considers the formalism used for representing a special class of
extensions of finite automata, so-called generalized indeterministic finite automata.
The described algorithms of equivalent transformations of such automata and also
their analogue of Kleene theorem result in not only the equivalence between such
and usual finite automata (such equivalence is obvious a priori), but also in the possibility of defining the complement operation (and, generally, the generalized regular expressions) by usual “automata” methods. The work also describes the construction method of the specific generalized automaton, which determines the given
generalized regular expression. The given method results from the Kleene theorem
analogue proving. Extended opportunities for regular languages description introduced in the article may be of use in several applications, e.g. in contextual search.
Key words: indeterministic finite automaton, generalized regular expressions, algorithms of equivalent transformation, analogue of Kleene theorem.
Введение
В данной статье рассматривается формализм, предназначенный для
представления специального расширения класса недетерминированных конечных автоматов. Статья является обобщением нескольких предыдущих
публикаций авторов [1–3]. При этом, кроме более подробного изложения рассмотренных в [1–3] понятий и доказанных фактов, в настоящей статье также
описывается метод построения конкретного обобщенного автомата, который
определяет (среди прочих) заданное обобщенное регулярное выражение.
Этот метод построения фактически завершает описание рассматриваемого
нами формализма.
64
University proceedings. Volga region
№ 2 (26), 2013
Физико-математические науки. Математика
Итак, мы будем рассматривать формализм для задания автоматов, применяемых для описания обобщенных регулярных выражений (generalized
regular expressions), определяемых нами близко к [4]. С помощью предложенного формализма автоматы могут описывать не только операции, обычные
для регулярных выражений, но и применяемую для обобщенных регулярных
выражений операцию дополнения. Очевидно, что при этом мы описываем регулярные языки.
Такие расширенные возможности для описания регулярных языков
(иными словами – расширение класса недетерминированных конечных автоматов) могут быть полезны в некоторых приложениях, в частности, в контекстном поиске. Посредством обобщенных конечных автоматов и обобщенных регулярных выражений можно, например, с помощью небольшого числа
примитивов определить язык, который содержит все слова над рассматриваемым алфавитом – за исключением некоторого множества, определенного
пользователем.
В данной статье сформулированы основные определения рассматриваемых формализмов, а также изложены алгоритмы преобразования для них. Из
этих действий вытекает не столько их эквивалентность (она очевидна с самого начала), сколько возможность быстрого определения одного и того же
класса регулярных языков; в первую очередь – определения операции дополнения «обычными автоматными методами».
1. Основные определения и примеры
Обобщенными регулярными выражениями (ОРВ) согласно [4] будем
называть регулярные выражения, для которых дополнительно определена
операция дополнения ~. Подробнее: пусть задан алфавит Σ, тогда:
1) ОРВ ∅ определяет регулярный язык ∅ ;
2) для каждой буквы a ∈Σ ОРВ a определяет регулярный язык {a}.
Далее, пусть p и q – обобщенные регулярные выражения, определяющие регулярные языки P и Q соответственно, тогда:
3) ОРВ (p+q) определяет регулярный язык P ∪ Q ;
4) ОРВ (p·q) определяет регулярный язык PQ;
5) ОРВ (p*) определяет регулярный язык P*;
6) ОРВ (~p) определяет регулярный язык P = Σ* \P .
Определение 1. Обобщенное регулярное выражение – это то и только
то, что может быть образовано с помощью применения в каком-либо порядке
перечисленных шести правил; при этом каждое из этих правил может быть
применено любое (конечное) число раз.
Далее определим один из возможных вариантов обобщенного недетерминированного конечного автомата (ОНКА).
Определение 2. Назовем обобщенным недетерминированным конечным автоматом кортеж
G = (Q, Σ, δ, S , F ,T , ςin , ςout ) ,
(1)
где Q – конечное множество состояний автомата; Σ – рассматриваемый алфавит; δ – функция переходов δ : Q × (Σ ∪ {ε}) →  (Q ) ; S ⊆ Q – множество
стартовых состояний; F ⊆ Q – множество финальных состояний; T ⊆  –
Physics and mathematics sciences. Mathematics
65
Известия высших учебных заведений. Поволжский регион
конечное множество,  – множество натуральных чисел; ςin и ςout – функции вида ςin , ςout : Q × T → Q , для которых выполняются условия:
( ∀i ∈ T )( ∃! q, p ∈ Q, q ≠ p ) (ςin ( q, i ) = p)
и
( ∀i ∈ T )( ∃!q, p ∈ Q, q ≠ p ) (ςout ( q, i ) = p) .
Множество T и функции ςin , ςout определяют языки-дополнения; ниже
будет дано определение самих соответствующих языков.
Как и обычный конечный автомат, обобщенный конечный автомат может быть задан в виде помеченного орграфа. Определим граф переходов для
автомата (1) следующим образом. Множества Q, S, F и функция переходов δ
задаются аналогично графу переходов для обычного конечного автомата. Если ςin ( q, i ) = p, где q, p ∈ Q, i ∈ T , то в графе переходов имеется дуга из вершины q в вершину p, помеченная –i. Если ςout ( q, i ) = p, где q, p ∈ Q, i ∈ T , то
в графе имеется дуга из вершины q в вершину p, помеченная +i. Пример графа переходов обобщенного конечного автомата приведен на рис. 1.
Рис. 1. Пример графа переходов обобщенного конечного автомата
Определим язык, задаваемый ОНКА. Для любого i ∈ T рассмотрим состояния si , fi , in i , out i множества Q такие, что
ςin ( in i , i ) = si ,
ςout ( fi , i ) = out i .
(2)
Определение 3. Пусть G – обобщенный конечный автомат (1). Для не-
которых S ' , F ' ⊆ Q обозначим
K ( S ' , F ' ) = K (Q, Σ, δ, S ' , F ' ) .
66
(3)
University proceedings. Volga region
№ 2 (26), 2013
Физико-математические науки. Математика
Определение 4. Пусть G – ОНКА (1). Тогда K (G ) = (Q, Σ, δ, S , F ) будет
соответствовать обычному конечному автомату.
Определение 5. Пусть G – обобщенный конечный автомат (1). Для
(
)
out
∀k ∈ T обозначим Gk = G Q, Σ, δ, {sk } , { f k } , T− k , ςin
− k , ς − k , где
T− k = T \ {k} ;
(4)
in
ςin
− k ( q, i ) = ς ( q, i ) для всех q ∈ Q, i ∈ T− k ;
out
ςout
( q, i ) для всех q ∈ Q, i ∈ T−k .
− k ( q, i ) = ς
Определение 6. Язык (G ) автомата (1) определяется следующим
образом:
 ( G ) =  ( K (G ) )

∪    ( K ( S ,
i∈T

{in i }) )  ( Gi )  ( K ({out i }, F ) )  .

(5)
Согласно определению 6 очевидно, что для любого обобщенного автомата G, определяемого согласно (1), задаваемый им язык  ( G ) регулярен.
Продолжим рассмотрение примера автомата, приведенного на рис. 1.
Подробности построения соответствующего ОРВ согласно определению 6
опускаем; кратко скажем лишь, что язык этого ОНКА описывает множество
слов над алфавитом {a, b}, в которых нет двух стоящих подряд букв b.
2. Построение обобщенного конечного автомата
по заданному обобщенному регулярному выражению
Для «классических» регулярных выражений и конечных автоматов
давно известно, что эти варианты представления регулярного языка эквивалентны. То есть для каждого конечного автомата существует регулярное выражение, задающее тот же язык, и наоборот.
Эквивалентность ОНКА и ОРВ следует просто из регулярности языка,
определяемого согласно (5). Однако в этом и следующем разделах мы опишем конкретные алгоритмы построения ОНКА по заданному ОРВ (и наоборот, ОРВ по заданному ОНКА). Таким образом, мы получим возможность
определения операции дополнения (и вообще обобщенных регулярных выражений) «обычными автоматными методами». При этом, как было отмечено
выше, с помощью небольшого числа примитивов можно, например, определить язык, который содержит все слова над рассматриваемым алфавитом – за
исключением некоторого множества (возможно, бесконечного, но обязательно регулярного), определенного пользователем.
Итак, сначала построим ОНКА, эквивалентный заданному ОРВ. Автомат будем строить по индукции. Обозначим через Gr автомат, эквивалентный выражению r. Поскольку любой автомат можно легко привести к эквивалентному автомату с одним входом и одним выходом, будем считать, что
все построенные автоматы имеют ровно один вход и один выход.
Графы переходов для ОНКА G∅ и Ga показаны на рис. 2.
Physics and mathematics sciences. Mathematics
67
Известия высших учебных заведений. Поволжский регион
Рис. 2. Графы переходов автоматов G∅ и Ga
Далее, пусть r и p – некоторые ОРВ, для которых уже построены эквивалентные автоматы
(
)
out
G p = G p ( Q p , Σ, δ p , {s p } , { f p } , T p , ςin
p , ςp ).
out
,
Gr = Gr Qr , Σ, δr , {sr } , { f r } , Tr , ςin
r , ςr
Эти автоматы изображены на рис. 3.
Рис. 3. Графы переходов автоматов Gr и G p
Тогда автоматы Gr + p и Grp построим согласно рис. 4:
(
{
} {
}
{
}
Gr + p = Gr + p Qr ∪ Q p ∪ sr + p ∪ f r + p , Σ, δr ∪ δ p ∪ δ, sr + p ,
out
{ fr + p } ,Tr ∪ Tp , ςinr ∪ ςinp , ςout
r ∪ςp ),
где
(
)
(
)
(
)
δ : δ sr + p , ε = sr , δ sr + p , ε = s p , δ ( f r , ε ) = f r + p , δ f p , ε = f r + p ,
(
{ }
)
in out
out
,
Grp = Grp Qr ∪ Q p , Σ, δr ∪ δ p ∪ δ,{sr } , f p ,Tr ∪ T p , ςin
r ∪ ς p , ςr ∪ ς p
здесь δ : δ ( f r , ε ) = s p .
68
University proceedings. Volga region
№ 2 (26), 2013
Физико-математические науки. Математика
Рис. 4. Графы переходов автоматов Gr + p и Grp
При этом будем считать, что ∀tr ∈ Tr , t p ∈ T p : tr ≠ t p , так как этого
условия легко добиться с помощью элементарных преобразований.
Автоматы Gr* и G~ r построим согласно рис. 5:
(
)
out
,
Gr* = Gr* Qr ∪ { f r*} , Σ, δr ∪ δ,{sr } ,{ f r*} ,Tr , ςin
r , ςr
где
δ : δ ( f r , ε ) = sr , δ ( f r , ε ) = f r* , δ ( sr , ε ) = f r* ,
(
)
in out
out
,
G~ r = G~ r Qr ∪ {s~ r } ∪ { f ~ r } , Σ, δr ,{s~ r } ,{ f ~ r } ,Tr ∪ {i}, ςin
r ∪ ς , ςr ∪ ς
здесь i = max t +1 , ςin ( s~ r , − i ) = sr , ςout ( f r , + i ) = f ~ r .
t  Tr
Корректность проведенных построений очевидна. Итак, мы привели индуктивный алгоритм построения эквивалентного ОНКА для заданного ОРВ.
3. Построение обобщенного регулярного выражения
по заданному обобщенному конечному автомату
Теперь докажем возможность построения ОРВ по заданному ОНКА,
т.е. фактически рассмотрим аналог теоремы Клини «в обобщенном случае».
При этом необходимы несколько следующих замечаний.
Во-первых, сама возможность построения следует из определения 6;
здесь же мы покажем возможность построения разных ОРВ (т.е. фактически
ОРВ, соответствующих заданному ОНКА, но с другими функциями ςin и
ςout ), что аналогично обычным доказательствам теоремы Клини [4–7].
Physics and mathematics sciences. Mathematics
69
Известия высших учебных заведений. Поволжский регион
Рис. 5. Графы переходов автоматов Gr* и G~r
Во-вторых, аналогия здесь далеко не полная: «в классическом случае»
теорема Клини доказывает регулярность языка автомата – мы же, зная эту
регулярность, заранее доказываем более простой факт, а именно корректность построения конкретных ОРВ.
Также отметим, что согласно материалу предыдущего раздела построенный ОНКА определяет, вообще говоря, несколько ОРВ, и при этом одно из
них совпадает с заданным.
Как известно, в различных вариантах доказательства «обычной» теоремы Клини содержится не только доказательство регулярности языка, определяемого автоматом, но и алгоритм построения регулярного выражения по заданному автомату. Регулярное выражение при этом строится в соответствии
с инъективной функцией, определяющей порядок состояний автомата. Для
различных вариантов инъективной функции в результате получаются различные регулярные выражения, но все они определяют один и тот же регулярный язык – язык, задаваемый исходным конечным автоматом.
Аналогичные построения производятся и в нашем, «обобщенном» случае. При этом мы доказываем еще и то, что при разном порядке выбора вершин (для построения ОРВ по заданному ОНКА) мы получаем различные
описания одного и того же регулярного языка. Значит, все построенные таким образом для данного ОНКА выражения эквивалентны и определяют тот
же язык, что и автомат.
Итак, опишем аналогичный алгоритм построения обобщенных регулярных выражений по обобщенному конечному автомату в соответствии
с инъективной функцией и докажем, что все построенные выражения определяют тот же регулярный язык, что и автомат. Будем обозначать такие выражения ρτ (G ) , где G – исходный автомат (1). При фиксированном τ будем
писать ρ(G ) .
70
University proceedings. Volga region
№ 2 (26), 2013
Физико-математические науки. Математика
Для заданного автомата G рассмотрим произвольную инъективную
функцию τ : Q → R + . Будем считать q < r, если τ ( q ) < τ(r ) . Зафиксируем на
данном этапе автомат G и функцию τ .
Для каждой пары состояний s, f ∈ Q (возможно s = f), рассмотрим ав-
(
)
томат K s→ f = Qs → f , Σ,δ s→ f ,{s} , { f } , где
Qs→ f = {s, f } ∪ Qsf ,
Qsf = {q ∈ Q | q > max ( s, f )} .
Функция переходов δ s→ f строится следующим образом:
a 
p 
r тогда и только тогда, когда p a r , p ∈ {s} ∪ Qsf , r ∈ { f } ∪ Qsf .
δs → f
δ
Рассмотрим язык
(
)
s→ f =  K s→ f ∪

∪   K s→ f
i∈T
 (

({s} ,{in i }) )  ( Gi )  ( K s→ f ({outi },{ f }) ) .

(6)
Если s = f , будем кратко обозначать s и K s соответственно. Тогда
язык автомата G можно записать в виде


 (G ) =
s ⋅  s → f ∪ 
s →q ⋅ q ⋅ q→ f

 q< min( s , f )
s∈S , f ∈F





  ⋅ f .


(7)
Далее построим регулярные выражения ρs → f , ρs , определяющие языки s → f и s . Сделаем это по индукции по τ(min ( s, f )) . Для этого сначала
для каждой пары состояний p, q∈ Q и i ∈ T определим обобщенное регулярное выражение gi ( p, q) :
1) если p = in i , q = out i , то gi ( p, q ) =~ ρ(Gi ) , где Gi – автомат (4);
2) иначе gi ( p, q ) = ∅ .
При этих обозначениях определяем
g ( p, q ) =
g i ( p, q ) .
i∈T
Теперь запишем выражения ρs → f , ρs .
Если min ( s, f ) = qmax = max({q | q ∈ Q}) , то
*
ρqmax
a
 


=  a ∈ Σ | qmax → qmax  + g ( qmax , qmax )  .





Physics and mathematics sciences. Mathematics
(8)
71
Известия высших учебных заведений. Поволжский регион
Если s ≠ f , то

a 


ρ s → f =  a ∈ Σ| s → f  + 
ρ s →q ⋅ ρq ⋅ ρq → f

  q > max( s , f )


 + g ( s, f ) .


(9)
Если s = f, то
*


a 


ρ s =   a ∈ Σ| s → s  +
ρ s →q ⋅ ρq ⋅ ρq → s + g ( s, s )  .
 

 q > s



(10)
Чтобы построить выражения g ( s, f ) , построим выражения gi ( s, f ) по
индукции по i ∈ T .
Пусть i = 1, тогда g1 ( p, q ) = ~ ρ ( G1 ) = ~ ρ( K ( {s1} ,{ f1}) . Выражение
ρ( K ( {s1} ,{ f1}) строится по алгоритму из «обычной» теоремы Клини.
Теперь предположим, что выражения g j ( p, q ) уже построены для
всех значений j < i, тогда
g i ( p, q ) =
ρ ( K ({si },{in j }) ) ⋅ g j ( in j , out j ) ⋅ ρ ( K ({out j } ,{ fi }) ) .
(11)
j <i
( ({s },{in })) и ρ ( K ({out },{ f })) построены по
Здесь выражения ρ K
(
теореме Клини, а g j in j , out j
i
)
j
j
i
– по предположению индукции.
Таким образом, у нас есть алгоритм построения выражений g ( s, f ) .
Пусть теперь известно, что все выражения из правых частей (9) и (10) уже построены. Тогда регулярное выражение, определяющее язык автомата (7),
можно записать в виде
ρ (G ) =

ρs ⋅  ρs→ f +
ρ s →q ⋅ ρq ⋅ ρ q → f

s∈S , f ∈F
q < min ( s , f )




⋅ρ .
 f

(12)
Из этого следует, что мы определили алгоритм построения обобщенного
регулярного выражения по заданному автомату G в соответствии с некоторой
инъективной функцией τ , и полученные описанным образом все такие возможные выражения всегда определяют тот же язык, что и автомат G согласно
определению 6. Итак, мы сформулировали алгоритм построения ОНКА по
ОРВ, а также алгоритм построения ОРВ по ОНКА. В результате было доказано,
что данные формализмы для описания регулярного языка эквивалентны.
Заключение
Итак, мы привели возможный подход к описанию обобщенных регулярных выражений с помощью расширения класса недетерминированных конечных автоматов. Отметим, что хотя определение обобщения автоматов мало похоже на рассматривавшееся в [5], но в то же время многие языки могут
72
University proceedings. Volga region
№ 2 (26), 2013
Физико-математические науки. Математика
быть определены этими двумя обобщениями с помощью практически одних и
тех же последовательностей примитивов.
Список литературы
1. Б а у м г е р т н е р , С . Мультиэвристический подход к проблеме звездно-высотной
минимизации недетерминированных конечных автоматов / С. Баумгертнер,
Б. Мельников // Вестник Воронежского государственного университета. Серия:
Cистемный анализ и информационные технологии. – 2010. – № 1. – C. 5–7.
2. Б а у м г е р т н е р , С . Математическая модель автоматов для обобщенных регулярных выражений / С. Баумгертнер, Б. Мельников // Эвристические алгоритмы и
распределенные вычисления в прикладных задачах : кол. моногр. – Тольятти :
Изд-во ТГУ, 2012. – С. 16–23.
3. Б а у м г е р т н е р , С . Аналог теоремы Клини для обобщенных недетерминированных конечных автоматов / С. Баумгертнер // Вектор науки Тольяттинского
государственного университета. – 2012. – № 4 (22). – С. 23–25.
4. С а л о м а а , А . Жемчужины теории формальных языков / А. Саломаа. – М. : Мир,
1986. – 159 с.
5. M e l n i k o v , B . Extended nondeterministic finite automata / B. Melnikov // Fundamenta Informaticae. – 2010. – Vol. 104, Т. 3. – Р. 255–265.
6. M e l n i k o v , B . Some more on the finite automata / B. Melnikov, A. Vakhitova // J. of
Applied Math. and Comp. (The Korean J. of Comp. Appl. Math.). – 1998. – Vol. 5,
№ 3. – Р. 495–506.
7. M e l n i k o v , B . Once more on the edge-minimization of nondeterministic finite automata and the connected problems / B. Melnikov // Fundamenta Informaticae. –
2010. – Vol. 104, № 3. – Р. 267–283.
References
1. Baumgertner S., Mel'nikov B. Vestnik Voronezhskogo gosudarstvennogo universiteta.
Seriya: Cistemnyy analiz i informatsionnye tekhnologii [Voronezh state university bulletin. Series: System analysis and information technologies]. 2010, no. 1, pp. 5–7.
2. Baumgertner S., Mel'nikov B. Evristicheskie algoritmy i raspredelennye vychisleniya v
prikladnykh zadachakh : kol. monogr. [Heuristic algorithms and distributed computing
in applied problems: joint monograph]. Tolyatti: Izd-vo TGU, 2012, pp. 16–23.
3. Baumgertner S. Vektor nauki Tol'yattinskogo gosudarstvennogo universiteta [Science
vector of Togliatti state university]. 2012, no. 4 (22), pp. 23–25.
4. Salomaa A. Zhemchuzhiny teorii formal'nykh yazykov [Pearls of the formal languages
theory]. Moscow: Mir, 1986, 159 p.
5. Melnikov B. Fundamenta Informaticae. 2010, vol. 104, no. 3, pp. 255–265.
6. Melnikov B., Vakhitova A. J. of Applied Math. and Comp. (The Korean J. of Comp.
Appl. Math.). 1998, vol. 5, no 3, pp. 495–506.
7. Melnikov B. Fundamenta Informaticae. 2010, vol. 104, no. 3, pp. 267–283.
Баумгертнер Светлана Викторовна
кандидат физико-математических наук,
старший преподаватель, кафедра
прикладной математики и информатики,
Тольяттинский государственный
университет (г. Тольятти,
ул. Белорусская, 14)
Baumgertner Svetlana Viktorovna
Candidate of physical and mathematical
sciences, senior lecturer, sub-department
of applied mathematics and informatics,
Togliatti State University (Togliatti,
14 Belorusskaya str.)
E-mail: S-Baumgertner@yandex.ru
Physics and mathematics sciences. Mathematics
73
Известия высших учебных заведений. Поволжский регион
Мельников Борис Феликсович
доктор физико-математических наук,
профессор, кафедра прикладной
математики и информатики,
Тольяттинский государственный
университет (г. Тольятти,
ул. Белорусская, 14)
Mel'nikov Boris Feliksovich
Doctor of physical and mathematical
sciences, professor, sub-department
of applied mathematics and informatics,
Togliatti State University (Togliatti,
14 Belorusskaya str.)
E-mail: B.Melnikov@tltsu.ru
УДК 519.178
Баумгертнер, С. В.
Обобщенные недетерминированные конечные автоматы / С. В. Баумгертнер, Б. Ф. Мельников // Известия высших учебных заведений.
Поволжский регион. Физико-математические науки. – 2013. – № 2 (26). –
С. 64–74.
74
University proceedings. Volga region
Документ
Категория
Без категории
Просмотров
4
Размер файла
599 Кб
Теги
конечный, недетерминированных, обобщенные, автомати
1/--страниц
Пожаловаться на содержимое документа