Algorytm Kleene'a

W informatyce teoretycznej , w szczególności w teorii języków formalnych , algorytm Kleene'a przekształca zadany niedeterministyczny automat skończony (NFA) w wyrażenie regularne . Wraz z innymi algorytmami konwersji ustala równoważność kilku formatów opisu dla języków regularnych . Alternatywne prezentacje tej samej metody obejmują „metodę eliminacji” przypisywaną Brzozowskiemu i McCluskeyowi , algorytm McNaughtona i Yamada oraz zastosowanie lematu Ardena .

Opis algorytmu

Według Grossa i Yellen (2004) algorytm można prześledzić wstecz do Kleene (1956). Prezentację algorytmu w przypadku deterministycznych automatów skończonych (DFA) podaje Hopcroft i Ullman (1979). Poniższa prezentacja algorytmu dla NFA jest zgodna z Grossem i Yellenem (2004).

₀₀ Mając niedeterministyczny automat skończony M = ( Q , Σ, δ, q , F ), gdzie Q = { q ,..., q _n } jego zbiór stanów , algorytm oblicza

zbiory R
^k _ij wszystkich strun, które przenoszą M ze stanu q _i do q _j bez przechodzenia przez stan o numerze wyższym niż k .

Tutaj „przechodzenie przez stan” oznacza wchodzenie i wychodzenie z niego, więc zarówno i, jak i j mogą być wyższe niż k , ale żaden stan pośredni nie może. Każdy zbiór R
^k _ij jest reprezentowany przez wyrażenie regularne; algorytm oblicza je krok po kroku dla k = -1, 0, ..., n . Ponieważ nie ma stanu o numerze wyższym niż n , wyrażenie regularne R
ⁿ _0j reprezentuje zbiór wszystkich ciągów, które biorą M z jego ₀ stan początkowy q do q _j . Jeśli F = { q ₁ ,..., q _f } jest zbiorem akceptowanych stanów , wyrażenie regularne R
ⁿ ₀₁ | ... | R
ⁿ _0f reprezentuje język akceptowany przez M .

Początkowe wyrażenia regularne, dla k = -1, są obliczane w następujący sposób dla i ≠ j :

R
⁻¹ _ij = za ₁ | ... | za _m gdzie q _jot ∈ δ( q _ja , za ₁ ), ..., q _jot ∈ δ( q _ja , a _m )

i następująco dla i = j :

R
^-1 _ii = za ₁ | ... | za _m | ε gdzie q _ja ∈ δ( q _ja , za ₁ ), ..., q _ja ∈ δ ( q _ja , a _m )

Innymi słowy, R
⁻¹ _ij wymienia wszystkie litery, które oznaczają przejście od i do j , a także uwzględniamy ε w przypadku, gdy i = j .

Następnie w każdym kroku obliczane są wyrażenia R
^k _ij na podstawie poprzednich przez

R
^k _ja = R
^{k -1} _jak ( R
^{k -1} _kk ) ^* R
^{k -1} _kj | R
^{k -1} _ij

Innym sposobem zrozumienia działania algorytmu jest „metoda eliminacji”, w której stany od 0 do n są sukcesywnie usuwane: gdy usuwany jest stan k , wyrażenie regularne R
^{k -1} _ij , które opisuje słowa oznaczające a ścieżka ze stanu i > k do stanu j > k , zostaje przepisana na R
^k _ij tak, aby uwzględnić możliwość przejścia przez stan "wyeliminowany" k .

Przez indukcję względem s k można wykazać, że długość każdego wyrażenia R k ij wynosi co najwyżej 1/3 ) ( 4 k
⁺¹ ₍ 6 +7 ^{- 4} ) symboli , gdzie s oznacza liczbę znaków w Σ. Dlatego długość wyrażenia regularnego reprezentującego język akceptowany przez M wynosi co najwyżej 1/3 gdzie n (4 ^{+1 (} 6 s +7) f - f - 3) symboli, f oznacza liczbę stanów końcowych. To wykładnicze powiększenie jest nieuniknione, ponieważ istnieją rodziny DFA, dla których każde równoważne wyrażenie regularne musi mieć rozmiar wykładniczy.

W praktyce rozmiar wyrażenia regularnego uzyskanego w wyniku uruchomienia algorytmu może być bardzo różny w zależności od kolejności, w jakiej stany są rozpatrywane przez procedurę, tj. kolejności, w jakiej są one numerowane od 0 do n .

Przykład

Przykład DFA podany algorytmowi Kleene'a

₀ Pokazany na rysunku automat można opisać jako M = ( Q , Σ, δ, q , F ) gdzie

• ₀ zbiór stanów Q = { q , q ₁ , q ₂ },
• alfabet wejściowy Σ = { a , b },
• ₀₀₀ funkcja przejścia δ gdzie δ( q , a )= q , δ( q , b )= q ₁ , δ( q ₁ , a )= q ₂ , δ( q ₁ , b )= q ₁ , δ( q ₂ , za )= q ₁ , i δ ( q ₂ , b )= q ₁ ,
• ₀ stan początkowy q i
• zbiór stanów akceptacji F = { q ₁ }.

Algorytm Kleene'a oblicza początkowe wyrażenia regularne jako

R -1 00	= za | ε
R -1 01	= b
R -1 02	= ∅
R -1 10	= ∅
R -1 11	= b | ε
R -1 12	= za
R -1 20	= ∅
R -1 21	= za | B
R -1 22	= ε

Następnie R
^k _ij są obliczane krok po kroku z R
^{k -1} _{ij dla} k = 0, 1, 2. Równości algebry Kleene są używane w celu maksymalnego uproszczenia wyrażeń regularnych.

Krok 0

R 0 00	= R −1 00 ( R −1 00 ) * R −1 00 | R -1 00	= ( za | ε)	( za | ε) *	( za | ε)	| | _ ε	= za *
R 0 01	= R −1 00 ( R −1 00 ) * R −1 01 | R -1 01	= ( za | ε)	( za | ε) *	B	| B	= za * b
R 0 02	= R −1 00 ( R −1 00 ) * R −1 02 | R -1 02	= ( za | ε)	( za | ε) *	∅	| ∅	= ∅
R 0 10	= R −1 10 ( R −1 00 ) * R −1 00 | R -1 10	= ∅	( za | ε) *	( za | ε)	| ∅	= ∅
R 0 11	= R −1 10 ( R −1 00 ) * R −1 01 | R -1 11	= ∅	( za | ε) *	B	| b | ε	= b | ε
R 0 12	= R −1 10 ( R −1 00 ) * R −1 02 | R -1 12	= ∅	( za | ε) *	∅	| A	= za
0 20 zł	= R −1 20 ( R −1 00 ) * R −1 00 | R -1 20	= ∅	( za | ε) *	( za | ε)	| ∅	= ∅
R21 0 _	= R −1 20 ( R −1 00 ) * R −1 01 | R -1 21	= ∅	( za | ε) *	B	| | _ B	= za | B
R22 0 _	= R −1 20 ( R −1 00 ) * R −1 02 | R -1 22	= ∅	( za | ε) *	∅	| ε	= ε

Krok 1

1 00 R	= R 0 01 ( R 0 11 ) * R 0 10 | R 0 00	= za * b	( b | ε) *	∅	| * _	= za *
R 1 01	= R 0 01 ( R 0 11 ) * R 0 11 | R 0 01	= za * b	( b | ε) *	( b | ε)	| a * b	= za * b * b
R 1 02	= R 0 01 ( R 0 11 ) * R 0 12 | R 0 02	= za * b	( b | ε) *	A	| ∅	= za * b * ba
R 1 10	= R 0 11 ( R 0 11 ) * R 0 10 | R 0 10	= ( b | ε)	( b | ε) *	∅	| ∅	= ∅
R 1 11	= R 0 11 ( R 0 11 ) * R 0 11 | R 0 11	= ( b | ε)	( b | ε) *	( b | ε)	| b | ε	= b *
R 1 12	= R 0 11 ( R 0 11 ) * R 0 12 | R 0 12	= ( b | ε)	( b | ε) *	A	| A	= b * za
R 1 20	= R 0 21 ( R 0 11 ) * R 0 10 | 0 20 zł	= ( za | b )	( b | ε) *	∅	| ∅	= ∅
R 1 21	= R 0 21 ( R 0 11 ) * R 0 11 | R21 0 _	= ( za | b )	( b | ε) *	( b | ε)	| | _ B	= ( za | b ) b *
R1 22 _	= R 0 21 ( R 0 11 ) * R 0 12 | R22 0 _	= ( za | b )	( b | ε) *	A	| ε	= ( za | b ) b * za | ε

Krok 2

200 _ zł	= R 1 02 ( R 1 22 ) * R 1 20 | 1 00 R	= za * b * ba	(( za | b ) b * za | ε) *	∅	| * _	= za *
R2 01 _	= R 1 02 ( R 1 22 ) * R 1 21 | R 1 01	= za * b * ba	(( za | b ) b * za | ε) *	( za | b ) b *	| a * b * b	= za * b ( za ( za | b ) | b ) *
R2 02 _	= R 1 02 ( R 1 22 ) * R 1 22 | R 1 02	= za * b * ba	(( za | b ) b * za | ε) *	(( za | b ) b * za | ε)	| a * b * ba	= za * b * b ( za ( za | b ) b * ) * za
R2 10 _	= R 1 12 ( R 1 22 ) * R 1 20 | R 1 10	= b * za	(( za | b ) b * za | ε) *	∅	| ∅	= ∅
R2 11 _	= R 1 12 ( R 1 22 ) * R 1 21 | R 1 11	= b * za	(( za | b ) b * za | ε) *	( za | b ) b *	| b *	= ( za ( za | b ) | b ) *
R2 12 _	= R 1 12 ( R 1 22 ) * R 1 22 | R 1 12	= b * za	(( za | b ) b * za | ε) *	(( za | b ) b * za | ε)	| b * a	= ( za ( za | b ) | b ) * za
R2 20 _	= R 1 22 ( R 1 22 ) * R 1 20 | R 1 20	= (( za | b ) b * za | ε)	(( za | b ) b * za | ε) *	∅	| ∅	= ∅
R2 21 _	= R 1 22 ( R 1 22 ) * R 1 21 | R 1 21	= (( za | b ) b * za | ε)	(( za | b ) b * za | ε) *	( za | b ) b *	| ( za | b ) b *	= ( za | b ) ( za ( za | b ) | b ) *
R2 22 _	= R 1 22 ( R 1 22 ) * R 1 22 | R1 22 _	= (( za | b ) b * za | ε)	(( za | b ) b * za | ε) *	(( za | b ) b * za | ε)	| ( za | b ) b * za | ε	= (( za | b ) b * za ) *

₀ Ponieważ q jest stanem początkowym, a q ₁ jest jedynym stanem akceptacji, wyrażenie regularne R
² ₀₁ oznacza zbiór wszystkich ciągów akceptowanych przez automat.

Zobacz też

• Algorytm Floyda-Warshalla - algorytm na grafach ważonych, który może być zaimplementowany przez algorytm Kleene'a przy użyciu określonej algebry Kleene'a
• Problem wysokości gwiazdy — jaka jest minimalna głębokość zagnieżdżenia gwiazdek wszystkich wyrażeń regularnych odpowiadających danemu DFA?
• Uogólniony problem wysokości gwiazdy — jeśli operator dopełnienia jest dozwolony dodatkowo w wyrażeniach regularnych, czy głębokość zagnieżdżenia gwiazd w danych wyjściowych algorytmu Kleene'a może być ograniczona do ustalonej granicy?
• Algorytm konstrukcyjny Thompsona — przekształca wyrażenie regularne w automat skończony