Kleenesův algoritmus - Kleenes algorithm - Wikipedia
v teoretická informatika, zejména v teorie formálního jazyka, Kleenův algoritmus transformuje danou nedeterministický konečný automat (NFA) do a regulární výraz. Spolu s dalšími převáděcími algoritmy vytváří ekvivalenci několika formátů popisu pro běžné jazyky. Alternativní prezentace stejné metody zahrnují „eliminační metodu“ připisovanou Brzozowski a McCluskey, algoritmus McNaughton a Yamada,[1] a používání Ardenovo lemma.
Popis algoritmu
Podle Grossa a Yellena (2004),[2] lze algoritmus vysledovat zpět Kleene (1956).[3] Prezentace algoritmu v případě deterministické konečné automaty (DFA) je uveden v Hopcroft a Ullman (1979).[4] Prezentace algoritmu pro NFA níže následuje Grossa a Yellena (2004).[2]
Vzhledem k nedeterministický konečný automat M = (Q, Σ, δ, q0, F), s Q = { q0,...,qn } jeho sada státy, algoritmus počítá
- sady Rk
ij ze všech strun, které zaberou M ze státu qi na qj aniž by prošel jakýmkoli státem číslovaným vyšší než k.
Zde znamená „projít státem“ vstoupit a opouštět to, tak oba i a j může být vyšší než k, ale žádný přechodný stav nemusí. Každá sada Rk
ij je reprezentován regulárním výrazem; algoritmus je vypočítá krok za krokem pro k = -1, 0, ..., n. Protože neexistuje žádný stát očíslovaný výše než n, regulární výraz Rn
0j představuje sadu všech řetězců, které berou M od jeho počáteční stav q0 na qj. Li F = { q1,...,qF } je množina přijímat státy, regulární výraz Rn
01 | ... | Rn
0f představuje jazyk přijato podle M.
Počáteční regulární výrazy pro k = -1, jsou pro i≠j:
- R−1
ij = A1 | ... | Am kde qj ∈ δ (qi,A1), ..., qj ∈ δ (qi,Am)
a následovně pro i=j:
- R−1
ii = A1 | ... | Am | ε kde qi ∈ δ (qi,A1), ..., qi ∈ δ (qi,Am)
Jinými slovy, R−1
ij zmiňuje všechna písmena, která označují přechod z i na j, a zahrneme také ε v případě, že i=j.
Poté v každém kroku výrazy Rk
ij jsou počítány z předchozích pomocí
- Rk
ij = Rk-1
ik (Rk-1
kk)* Rk-1
kj | Rk-1
ij
Dalším způsobem, jak porozumět fungování algoritmu, je „eliminační metoda“, kde jsou stavy od 0 do n jsou postupně odstraněny: když stav k je odstraněn, regulární výraz Rk-1
ij, který popisuje slova, která označují cestu ze státu i>k do stavu j>k, je přepsán do Rk
ij tak, aby byla zohledněna možnost přechodu přes „vyloučený“ stav k.
Indukcí dne k, lze ukázat, že délka[5] každého výrazu Rk
ij je nanejvýš 1/3(4k+1(6s+7) - 4) symboly, kde s označuje počet znaků v Σ. Délka regulárního výrazu představujícího jazyk přijatý znakem proto M je nanejvýš 1/3(4n+1(6s+7)F - F - 3) symboly, kde F označuje počet konečných stavů. Toto exponenciální zvětšení je nevyhnutelné, protože existují rodiny DFA, pro které musí mít ekvivalentní regulární výraz exponenciální velikost.[6]
V praxi se velikost regulárního výrazu získaného spuštěním algoritmu může velmi lišit v závislosti na pořadí, ve kterém jsou stavy považovány za proceduru, tj. Pořadí, ve kterém jsou očíslovány od 0 do n.
Příklad
Automat zobrazený na obrázku lze popsat jako M = (Q, Σ, δ, q0, F) s
- množina států Q = { q0, q1, q2 },
- vstupní abeceda Σ = { A, b },
- přechodová funkce δ s δ (q0,A)=q0, δ (q0,b)=q1, δ (q1,A)=q2, δ (q1,b)=q1, δ (q2,A)=q1, a δ (q2,b)=q1,
- počáteční stav q0, a
- sada přijímat státy F = { q1 }.
Kleenův algoritmus počítá počáteční regulární výrazy jako
R−1
00= A | ε R−1
01= b R−1
02= ∅ R−1
10= ∅ R−1
11= b | ε R−1
12= A R−1
20= ∅ R−1
21= A | b R−1
22= ε
Poté, co Rk
ij jsou počítány z Rk-1
ij krok za krokem pro k = 0, 1, 2.Kleene algebra Rovnosti se používají k co největšímu zjednodušení regulárních výrazů.
- Krok 0
R0
00= R−1
00 (R−1
00)* R−1
00 | R−1
00= (A | ε) (A | ε)* (A | ε) | A | ε = A* R0
01= R−1
00 (R−1
00)* R−1
01 | R−1
01= (A | ε) (A | ε)* b | b = A* b R0
02= R−1
00 (R−1
00)* R−1
02 | R−1
02= (A | ε) (A | ε)* ∅ | ∅ = ∅ R0
10= R−1
10 (R−1
00)* R−1
00 | R−1
10= ∅ (A | ε)* (A | ε) | ∅ = ∅ R0
11= R−1
10 (R−1
00)* R−1
01 | R−1
11= ∅ (A | ε)* b | b | ε = b | ε R0
12= R−1
10 (R−1
00)* R−1
02 | R−1
12= ∅ (A | ε)* ∅ | A = A R0
20= R−1
20 (R−1
00)* R−1
00 | R−1
20= ∅ (A | ε)* (A | ε) | ∅ = ∅ R0
21= R−1
20 (R−1
00)* R−1
01 | R−1
21= ∅ (A | ε)* b | A | b = A | b R0
22= R−1
20 (R−1
00)* R−1
02 | R−1
22= ∅ (A | ε)* ∅ | ε = ε
- Krok 1
R1
00= R0
01 (R0
11)* R0
10 | R0
00= A*b (b | ε)* ∅ | A* = A* R1
01= R0
01 (R0
11)* R0
11 | R0
01= A*b (b | ε)* (b | ε) | A* b = A* b* b R1
02= R0
01 (R0
11)* R0
12 | R0
02= A*b (b | ε)* A | ∅ = A* b* ba R1
10= R0
11 (R0
11)* R0
10 | R0
10= (b | ε) (b | ε)* ∅ | ∅ = ∅ R1
11= R0
11 (R0
11)* R0
11 | R0
11= (b | ε) (b | ε)* (b | ε) | b | ε = b* R1
12= R0
11 (R0
11)* R0
12 | R0
12= (b | ε) (b | ε)* A | A = b* A R1
20= R0
21 (R0
11)* R0
10 | R0
20= (A | b) (b | ε)* ∅ | ∅ = ∅ R1
21= R0
21 (R0
11)* R0
11 | R0
21= (A | b) (b | ε)* (b | ε) | A | b = (A | b) b* R1
22= R0
21 (R0
11)* R0
12 | R0
22= (A | b) (b | ε)* A | ε = (A | b) b* A | ε
- Krok 2
R2
00= R1
02 (R1
22)* R1
20 | R1
00= A*b*ba ((A|b)b*A | ε)* ∅ | A* = A* R2
01= R1
02 (R1
22)* R1
21 | R1
01= A*b*ba ((A|b)b*A | ε)* (A|b)b* | A* b* b = A* b (A (A | b) | b)* R2
02= R1
02 (R1
22)* R1
22 | R1
02= A*b*ba ((A|b)b*A | ε)* ((A|b)b*A | ε) | A* b* ba = A* b* b (A (A | b) b*)* A R2
10= R1
12 (R1
22)* R1
20 | R1
10= b* A ((A|b)b*A | ε)* ∅ | ∅ = ∅ R2
11= R1
12 (R1
22)* R1
21 | R1
11= b* A ((A|b)b*A | ε)* (A|b)b* | b* = (A (A | b) | b)* R2
12= R1
12 (R1
22)* R1
22 | R1
12= b* A ((A|b)b*A | ε)* ((A|b)b*A | ε) | b* A = (A (A | b) | b)* A R2
20= R1
22 (R1
22)* R1
20 | R1
20= ((A|b)b*A | ε) ((A|b)b*A | ε)* ∅ | ∅ = ∅ R2
21= R1
22 (R1
22)* R1
21 | R1
21= ((A|b)b*A | ε) ((A|b)b*A | ε)* (A|b)b* | (A | b) b* = (A | b) (A (A | b) | b)* R2
22= R1
22 (R1
22)* R1
22 | R1
22= ((A|b)b*A | ε) ((A|b)b*A | ε)* ((A|b)b*A | ε) | (A | b) b* A | ε = ((A | b) b* A)*
Od té doby q0 je počáteční stav a q1 je jediný akceptovaný stav, regulární výraz R2
01 označuje sadu všech řetězců přijatých automatem.
Viz také
- Floyd-Warshallův algoritmus - algoritmus na vážených grafech, který lze implementovat Kleeneovým algoritmem pomocí konkrétního Kleene algebra
- Problém s výškou hvězdy - jaká je minimální hloubka vnoření hvězd všech regulárních výrazů odpovídající dané DFA?
- Zobecněný problém s výškou hvězdy - pokud je operátor doplňku povolen dodatečně v regulárních výrazech, může hloubka hnízdění hvězd výstupu Kleeneova algoritmu omezen na pevnou hranici?
- Thompsonův konstrukční algoritmus - transformuje regulární výraz na konečný automat
Reference
- ^ McNaughton, R .; Yamada, H. (březen 1960). "Regulární výrazy a stavové grafy pro automaty". Transakce IRE na elektronických počítačích. EC-9 (1): 39–47. doi:10.1109 / TEC.1960.5221603. ISSN 0367-9950.
- ^ A b Jonathan L. Gross a Jay Yellen, ed. (2004). Příručka teorie grafů. Diskrétní matematika a její aplikace. CRC Press. ISBN 1-58488-090-2. Zde: oddíl 2.1, poznámka R13 na str.65
- ^ Kleene, Stephen C. (1956). „Reprezentace událostí v nervových sítích a Finite Automate“ (PDF). Automata Studies, Annals of Math. Studie. Princeton Univ. Lis. 34. Zde: oddíl 9, s. 37-40
- ^ John E. Hopcroft, Jeffrey D. Ullman (1979). Úvod do teorie automatů, jazyků a výpočtu. Addison-Wesley. ISBN 0-201-02988-X. Zde: Oddíl 3.2.1 strany 91-96
- ^ Přesněji řečeno, počet symbolů regulárního výrazu, “Ai"," ε "," | ","*"," · "; Nepočítám závorky.
- ^ Gruber, Hermann; Holzer, Markus (2008). Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M .; Ingólfsdóttir, Anna; Walukiewicz, Igor (eds.). „Konečné automaty, konektivita digrafu a velikost regulárního výrazu“. Automaty, jazyky a programování. Přednášky z informatiky. Springer Berlin Heidelberg. 5126: 39–50. doi:10.1007/978-3-540-70583-3_4. ISBN 9783540705833.. Věta 16.