Jak převést konečné automaty na regulární výrazy?
On 16 února, 2021 by adminPřevádění regulárních výrazů na (minimální) NFA, které přijímají stejný jazyk, je snadné pomocí standardních algoritmů, např. Thompsonův algoritmus . Zdá se však, že druhý směr je zdlouhavější a výsledné výrazy jsou někdy chaotické.
Jaké jsou algoritmy tam pro převod NFA na ekvivalentní regulární výrazy? Existují výhody týkající se časové složitosti nebo velikosti výsledku?
Toto má být referenční otázka. Uveďte obecný popis své metody a také netriviální příklad.
Komentáře
- Všimněte si podobné otázky na adrese cstheory.SE , který pravděpodobně není vhodný pro naše publikum.
- všechny odpovědi používají k napsání RE z DFA formální techniku. Věřím, že moje technika na základě analýzy je poměrně snadná a objektivní. : Jaký je jazyk těchto deterministických konečných automatů? Cítím, že by to někdy pomohlo. Ano, samozřejmě někdy sám používám formální metodu (Ardenova věta) psát RE je otázka je složitá, jak je uvedeno v tomto příkladu: Jak psát regulární výraz pro DFA
Odpověď
Převod z konečných automatů na regulární výrazy lze provést několika způsoby. Zde popíšu ten, který se obvykle vyučuje ve škole a který je velmi vizuální. Věřím, že je v praxi nejpoužívanější. Psaní algoritmu však není tak dobrý nápad.
Metoda odstranění stavu
Tento algoritmus je o zpracování grafu automatu, a proto není pro algoritmy příliš vhodný, protože potřebuje primitiva grafu, jako … odstranění stavu. Popíšu to pomocí primitiv vyšší úrovně.
Klíčová myšlenka
Myšlenkou je uvažovat o regulárních výrazech na okrajích a poté odstranit mezilehlé stavy při zachování konzistence štítků hran.
Hlavní vzor je vidět na následujících obrázcích. První má popisky mezi $ p, q, r $, které jsou regulárními výrazy $ e, f, g, h, i $ a chceme odstranit $ q $.
Po odstranění složíme $ e, f, g, h, i $ společně (při zachování ostatních hran mezi $ p $ a $ r $, ale toto se nezobrazí k tomu):
Příklad
Použijte stejný příklad jako v Raphaelova odpověď :
postupně odstraňujeme $ q_2 $:
a poté $ q_3 $:
pak musíme na výraz od $ q_1 $ do $ q_1 $ použít hvězdičku. V tomto případě je konečný stav také počáteční, takže opravdu stačí přidat hvězdu:
$$ (ab + (b + aa) (ba) ^ * (a + bb)) ^ * $$
Algoritmus
L[i,j]
je regulární výraz jazyka od $ q_i $ do $ q_j $. Nejprve odstraníme vše ti-edge:
for i = 1 to n: for j = 1 to n: if i == j then: L[i,j] := ε else: L[i,j] := ∅ for a in Σ: if trans(i, a, j): L[i,j] := L[i,j] + a
Nyní odstranění stavu. Předpokládejme, že chceme odstranit stav $ q_k $:
remove(k): for i = 1 to n: for j = 1 to n: L[i,i] += L[i,k] . star(L[k,k]) . L[k,i] L[j,j] += L[j,k] . star(L[k,k]) . L[k,j] L[i,j] += L[i,k] . star(L[k,k]) . L[k,j] L[j,i] += L[j,k] . star(L[k,k]) . L[k,i]
Všimněte si, že jak tužkou, tak pomocí algoritmu byste měli zjednodušit výrazy jako star(ε)=ε
, e.ε=e
, ∅+e=e
, ∅.e=∅
(autor ruku prostě nenapíšeš hranu, když to není $ ∅ $, nebo dokonce $ ε $ pro vlastní smyčku a ignoruješ, když neexistuje přechod mezi $ q_i $ a $ q_k $ nebo $ q_j $ a $ q_k $)
Jak používat remove(k)
? Neměli byste lehce odstraňovat konečné nebo počáteční stavy, jinak vám budou chybět části jazyka.
for i = 1 to n: if not(final(i)) and not(initial(i)): remove(i)
Pokud máte pouze jeden konečný stav $ q_f $ a jeden počáteční stav $ q_s $, výsledný výraz je:
e := star(L[s,s]) . L[s,f] . star(L[f,s] . star(L[s,s]) . L[s,f] + L[f,f])
Pokud máte několik konečných stavů (nebo dokonce počátečních stavů), neexistuje jednoduchý způsob sloučení tyto, jiné než použití metody přechodného uzavření. Obvykle to není problém ručně, ale při psaní algoritmu je to nepříjemné. Mnohem jednodušším řešením je výčet všech párů $ (s, f) $ a spuštění algoritmu na (již odstraněném stavu) grafu pro získání všech výrazů $ e_ {s, f} $ za předpokladu, že $ s $ je jediný počáteční stav a $ f $ je jediný konečný stav, poté se sjednotí všechny $ e_ {s, f} $.
Toto a skutečnost, že se tím mění jazyky dynamičtěji než první metoda náchylnější k chybám při programování. Navrhuji použít jakoukoli jinou metodu.
Nevýhody
V tomto algoritmu existuje mnoho případů, například pro výběr uzlu, který bychom měli odstranit, počet konečných stavů na konci skutečnost, že konečný stav může být také počáteční atd.
Všimněte si, že nyní, když je algoritmus napsán, je to hodně jako metoda tranzitivního uzavření.Pouze kontext použití se liší. Nedoporučuji implementovat algoritmus, ale použití metody, jak to udělat ručně, je dobrý nápad.
Komentáře
- V příkladu, druhý obrázek, po odebrání uzlu “ 2 “ chybí hrana – hrana smyčky (ab) v uzlu A.
- @Kabamaru: Opraveno. Ale teď si myslím, že $ \ varepsilon $ ve 3. obrázku by měl být také
ab
a podobně možná v konečném regulárním výrazu. - Algoritmus můžete vytvořit pracujte pro libovolný počet počátečních a konečných stavů přidáním nového počátečního $ q ^ + $ a nového konečného stavu $ q ^ – $ a jejich spojením s původním počátečním a konečným stavem pomocí $ \ varepsilon $ -edges. Nyní odeberte všechny původní stavy. Výraz je pak nalezen na jediné zbývající hraně od $ q ^ + $ do $ q _- $. Konstrukce neposkytne smyčky na $ q ^ + $ nebo $ q _- $, protože tyto státy nemají příchozí resp. odchozí hrany. Nebo pokud jste přísní, budou mít štítky představující prázdnou množinu.
- U druhého příkladu stále existuje problém: před zjednodušením automaty přijmou “ ba „, (1, 3, 1), ale po zjednodušení to není ‚ t.
Odpověď
Metoda
Nejhezčí metoda, kterou jsem viděl, je ta, která vyjadřuje automat jako systém rovnic (běžných) jazyků, které mohou být vyřešen. Je to obzvláště pěkné, protože se zdá, že poskytuje výstižnější výrazy než jiné metody.
Nechte $ A = (Q, \ Sigma, \ delta, q_0, F) $ an NFA bez $ \ varepsilon $ – přechody. Pro každý stát $ q_i $ vytvořte rovnici
$ \ qquad \ displaystyle Q_i = \ bigcup \ limits_ {q_i \ overset {a} {\ to} q_j} aQ_j \ cup \ begin {cases} \ {\ varepsilon \} &, \ q_i \ in F \\ \ emptyset &, \ text {else} \ end {případy} $
kde $ F $ je sada konečných stavů a $ q_i \ overset {a} {\ to} q_j $ znamená, že existuje přechod z $ q_i $ na $ q_j $ označený $ a $ . Pokud čtete $ \ cup $ jako $ + $ nebo $ \ mid $ (v závislosti na definici regulárního výrazu), uvidíte, že se jedná o rovnici regulárních výrazů.
K řešení systému potřebujete asociativitu a distribuce $ \ cup $ a $ \ cdot $ (zřetězení řetězců), komutativita $ \ cup $ a Ardenova Lemma ¹:
Nechejte $ L, U, V \ subseteq \ Sigma ^ * $ běžné jazyky s $ \ varepsilon \ notin U $. Potom,
$ \ qquad \ displaystyle L = UL \ cup V \ quad \ Longleftrightarrow \ quad L = U ^ * V $
Řešením je sada regulárních výrazů $ Q_i $, jeden pro každý stát $ q_i $. $ Q_i $ popisuje přesně ta slova, která mohou být přijata $ A $ při spuštění v $ q_i $; proto $ Q_0 $ (pokud je počáteční stav $ q_0 $) je požadovaný výraz.
Příklad
Kvůli jasnosti označujeme množiny singletonů jejich prvkem, tj. $ a = \ {a \} $. příkladem je Georg Zetzsche.
Zvažte t jeho NFA:
[ zdroj ]
Odpovídající systém rovnic je:
$ \ qquad \ begin {align} Q_0 & = aQ_1 \ cup bQ_2 \ cup \ varepsilon \\ Q_1 & = bQ_0 \ cup aQ_2 \\ Q_2 & = aQ_0 \ cup bQ_1 \ end {align} $
Nyní zapojte třetí rovnici do druhé:
$ \ qquad \ begin {align} Q_1 & = bQ_0 \ cup a (aQ_0 \ cup bQ_1) \\ & = abQ_1 \ cup (b \ cup aa) Q_0 \\ & = (ab) ^ * ( b \ cup aa) Q_0 \ end {align} $
V posledním kroku použijeme Ardenovu Lemmu s $ L = Q_1 $, $ U = ab $ a $ V = (b \ cup aa) \ cdot Q_0 $. Všimněte si, že všechny tři jazyky jsou běžné a $ \ varepsilon \ notin U = \ {ab \} $, což nám umožňuje použít lemma. Nyní zapojíme tento výsledek do první rovnice:
$ \ qquad \ begin {align} Q_0 & = a (ab) ^ * (b \ cup aa ) Q_0 \ cup baQ_0 \ cup bb (ab) ^ * (b \ cup aa) Q_0 \ cup \ varepsilon \\ & = ((a \ cup bb) (ab) ^ * (b \ cup aa) \ cup ba) Q_0 \ cup \ varepsilon \\ & = ((a \ cup bb) (ab) ^ * (b \ cup aa) \ cup ba) ^ * \ qquad \ text {(Ardenova Lemma)} \ end {align} $
Tak jsme našli regulární výraz pro jazyk akceptovaný výše uvedeným automatem, jmenovitě
$ \ qquad \ displaystyle ((a + bb) (ab) ^ * (b + aa) + ba) ^ *. $
Všimněte si, že je to celkem stručné (srovnejte s výsledek jiných metod), ale není jednoznačně stanoveno; řešení systému rovnic s jinou posloupností manipulací vede k dalším – ekvivalentním! – výrazům.
- Pro důkaz Arden “ s Lemma, viz zde .
Komentáře
- Co je časová složitost tohoto algoritmu? Existuje vazba na velikost produkovaného výrazu?
- @jmite: Nemám ponětí. ‚ si nemyslím, že se to ‚ pokusím implementovat (jiné metody se v tomto ohledu zdají být proveditelnější), ale použít je jako metoda pera a papíru.
- Zde ‚ sa Prolog implementace tohoto algoritmu: github.com / wvxvw / intro-to-automata-theory / blob / master / automata / … , ale jeho
maybe_union/2
predikát mohl použít více práce (zejm. s vyloučením společné předpony) pro vytvoření pořádnějších regulárních výrazů. Další způsob, jak tuto metodu vidět, je pochopit ji jako překlad z regexu do pravo-lineární gramatiky, kde jazyky se sjednocením podobným Prologu nebo shodou vzorů ML vytvářejí velmi dobré převodníky, takže ‚ není jen algoritmus pera a papíru 🙂 - Jen jedna otázka. Ε v první rovnici je proto, že Qo je počáteční stav nebo proto, že ‚ je konečný stav? Stejným způsobem, pokud mám dva konečné stavy platí?
- @PAOK Zkontrolujte definici $ Q_i $ výše (řádek); ‚ s, protože $ q_0 $ je konečný stav.
Odpovědět
Brzozowského algebraická metoda
Jedná se o stejnou metodu jako metoda popsaná v Raphaelově odpovědi , ale z hlediska pohled na systematický algoritmus a poté na algoritmus. Ukázalo se, že jeho implementace je snadná a přirozená, jakmile víte, kde začít. Rovněž může být jednodušší ručně, pokud je kreslení všech automatů z nějakého důvodu nepraktické.
Při psaní algoritmu musíte pamatovat na to, že rovnice musí být vždy lineární, abyste měli dobrou abstraktní reprezentaci rovnic, na co můžete při ručním řešení zapomenout.
Myšlenka algoritmu
Nebudu popisovat, jak to funguje, protože je to dobře provedeno v Raphaelově odpovědi , kterou místo toho se zaměřím na to, v jakém pořadí byste měli řešit rovnice, aniž byste museli dělat příliš mnoho navíc mputace nebo případy navíc.
Od důmyslného řešení Ardenova pravidla je důmyslné řešení $ X = A ^ * B $ k jazykové rovnici $ X = AX∪B $ můžeme automat považovat za množinu rovnic ve tvaru:
$$ X_i = B_i + A_ {i, 1} X_1 +… + A_ {i, n} X_n $$
můžeme to vyřešit indukcí na $ n $ aktualizací polí $ A_ {i, j} $ a $ B_ {i, j} $ odpovídajícím způsobem. V kroku $ n $ máme:
$$ X_n = B_n + A_ {n, 1} X_1 +… + A_ {n, n} X_n $$
a Ardenovo pravidlo nám dává:
$$ X_n = A_ {n, n} ^ * (B_n + A_ {n, 1} X_1 + … + A_ {n, n-1} X_ {n -1}) $$
a nastavením $ B „_n = A_ {n, n} ^ * B_n $ a $ A“ _ {n, i} = A_ {n, n} ^ * A_ {n, i} $ dostaneme:
$$ X_n = B „_n + A“ _ {n, 1} X_1 + … + A „_ {n, n-1} X_ {n -1} $$
a pak můžeme odstranit všechny potřeby $ X_n $ v systému nastavením, pro $ i, j < n $:
$$ B „_i = B_i + A_ {i, n} B“ _n $$ $$ A „_ {i, j} = A_ {i, j} + A_ {i, n} A „_ {n, j} $$
Když jsme vyřešili $ X_n $, když $ n = 1 $, získáme tuto rovnici:
$$ X_1 = B“ _1 $$
bez $ A „_ {1, i} $. Tak jsme dostali náš regulární výraz.
Algoritmus
Díky tomu můžeme algoritmus sestavit. Abychom měli stejnou konvenci než ve výše uvedené indukci, řekneme, že počáteční stav je $ q_1 $ a že počet stavů je $ m $. Nejprve inicializace k vyplnění $ B $:
for i = 1 to m: if final(i): B[i] := ε else: B[i] := ∅
a $ A $:
for i = 1 to m: for j = 1 to m: for a in Σ: if trans(i, a, j): A[i,j] := a else: A[i,j] := ∅
a poté řešení:
for n = m decreasing to 1: B[n] := star(A[n,n]) . B[n] for j = 1 to n: A[n,j] := star(A[n,n]) . A[n,j]; for i = 1 to n: B[i] += A[i,n] . B[n] for j = 1 to n: A[i,j] += A[i,n] . A[n,j]
konečný výraz je pak:
e := B[1]
Implementace
I když se může zdát systém rovnic, který se pro algoritmus zdá příliš symbolický, je vhodný pro implementaci. Zde je implementace tohoto algoritmu v Ocaml (nefunkční odkaz) . Všimněte si, že kromě funkce brzozowski
je vše možné vytisknout nebo použít jako příklad Raphaela. Všimněte si, že existuje překvapivě efektivní funkce zjednodušení regulárních výrazů simple_re
.
Komentáře
- Odkaz je mrtvý …
- Implementace v jazyce Javascript: github.com/devongovett/regexgen/blob/master/src/regex.js
- Děkuji za toto skvělé vysvětlení. Pokud správně rozumím, váš inicializační pseudokód předpokládá, že pro dané i a j existuje nanejvýš jedna taková, že (i, a, j) je přechod. To je správné, pokud souhlasíme s tím, že tento přechod označíme regexp, který odpovídá všem písmenům v Σ tento štítek přechází z i na j v automatu na dopisy, ale pak je váš zápis a in Σ trochu divný, protože to ve skutečnosti není písmeno. Jdeme-li po písmenech, můžeme mít několik přechodů z i na j a musíme sjednotit jejich štítky v těle smyčky.
Odpověď
Metoda tranzitivního uzavření
Tuto metodu lze snadno napsat ve formě algoritmu, ale generuje absurdně velké regulární výrazy a je nepraktické, pokud to děláte ručně, hlavně proto, že je to příliš systematické. Je to dobré a jednoduché řešení pro algoritmus.
Klíčová myšlenka
Nechť $ R ^ k_ {i, j} $ představuje regulární výraz pro řetězce vycházející z $ q_i $ až $ q_j $ pomocí stavů $ \ {q_1,…, q_k \} $. Nechť $ n $ je počet stavů automatu.
Předpokládejme, že už znáte regulární výraz $ R_ {i, j} $ od $ q_i $ do $ q_j $ bez mezilehlého stavu $ q_k $ (kromě končetin), pro všechny $ i, j $. Pak můžete hádat, jak přidání dalšího stavu ovlivní nový regulární výraz $ R „_ {i, j} $: změní se pouze v případě, že máte přímé přechody na $ q_k $, a lze to vyjádřit takto:
$$ R „_ {i, j} = R_ {i, j} + R_ {i, k}. R_ {k, k} ^ *. R_ {k, j} $$
($ R $ je $ R ^ {k-1} $ a $ R „$ je $ R ^ k $.)
Příklad
Použijeme stejný příklad jako v Raphaelově odpovědi . Nejprve můžete použít pouze přímé přechody.
Zde je první krok (všimněte si, že vlastní smyčka se štítkem $ a $ by transformovala prvních $ ε $ na $ (ε + a) $.
$$ R ^ 0 = \ begin {bmatrix} ε & a & b \\ b & ε & a \\ a & b & ε \ end {bmatrix} $$
Ve druhém kroku můžeme použít $ q_0 $ (které je pro nás přejmenováno na $ q_1 $, protože $ R ^ 0 $ je již použito pro výše uvedený účel). Uvidíme, jak $ R ^ 1 $ funguje.
Od $ q_2 $ do $ q_2 $: $ R ^ 1_ {2,2} = R ^ 0_ {2,2} + R ^ 0_ {2,1} {R ^ 0_ {1,1}} ^ * R ^ 0_ {1,2} = ε + b ε ^ * a = ε + ba $.
Proč je to tak? Je to proto, že přechod z $ q_2 $ na $ q_2 $ s použitím pouze $ q_1 $ jako přechodného stavu lze provést pobytem zde ($ ε $) nebo přechodem na $ q_1 $ ($ a $), opakováním ($ ε ^ * $) a návrat ($ b $).
$$ R ^ 1 = \ begin {bmatrix} ε & a & b \\ b & ε + ba & a + bb \\ a & b + aa & ε + ab \ end {bmatrix} $$
Můžete také počítat $ R ^ 2 $ a $ R ^ 3 $ a $ R ^ 3_ {1,1 } $ vám dá konečný výraz, protože $ 1 $ je počáteční i konečný. Všimněte si, že zde bylo provedeno mnoho zjednodušení výrazů. Jinak by první $ a $ z $ R ^ 0 $ bylo $ (∅ + a) $ a první $ a $ z $ R ^ 1 $ by bylo $ ((∅ + a) + ε (ε) ^ * a ) $.
Algoritmus
Inicializace:
for i = 1 to n: for j = 1 to n: if i == j: R[i,j,0] := ε else: R[i,j,0] := ∅ for a in Σ: if trans(i, a, j): R[i,j,0] := R[i,j,0] + a
Přechodné uzavření:
for k = 1 to n: for i = 1 to n: for j = 1 to n: R[i,j,k] := R[i,j,k-1] + R[i,k,k-1] . star(R[k,k,k-1]) . R(k,j,k-1)
Pak je konečný výraz (za předpokladu, že počáteční stav je $ q_s $):
e := ∅ for i = 1 to n: if final(i): e := e + R[s,i,n]
Ale můžete si představit generuje ošklivé regulární výrazy. Můžete opravdu očekávat věci jako $ (∅) ^ * + (a + (∅) ^ *) (ε) ^ * (a + ∅) $, které představují stejný jazyk jako $ aa $. Zjednodušení regulárního výrazu je v praxi užitečné.
Napsat komentář