Glushkovův konstrukční algoritmus - Glushkovs construction algorithm - Wikipedia
Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto problémech na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)
|
v počítačová věda teorie - zvláště teorie formálního jazyka - Glushkovův stavební algoritmus, vynalezl Victor Michajlovič Glushkov, transformuje danou regulární výraz do ekvivalentu nedeterministický konečný automat (NFA). Tvoří tedy most mezi regulárními výrazy a nedeterministickými konečnými automaty: dvě abstraktní reprezentace stejné třídy formální jazyky.
Regulární výraz lze použít k pohodlnému popisu vzoru pokročilého hledání v operaci typu „najít a nahradit“ zpracování textu nástroj. Glushkovův algoritmus lze použít přeměnit to do NFA, který je navíc od přírody malý, protože počet jeho stavů se rovná počtu symbolů regulárního výrazu plus jeden. Následně lze NFA učinit deterministickou pomocí konstrukce výkonové sady a pak být minimalizováno získat optimální automat odpovídající danému regulárnímu výrazu. Druhý formát je nejvhodnější pro spuštění v počítači.
Z jiného, více teoretického hlediska, Glushkovův algoritmus je součástí důkazu, že NFA i regulární výrazy přijímají přesně stejné jazyky; toto je běžné jazyky. Opakem Glushkovova algoritmu je Kleenův algoritmus, který transformuje konečný automat na regulární výraz. Automat získaný Glushkovovou konstrukcí je stejný jako automat získaný Thompsonův konstrukční algoritmus, jakmile jsou odstraněny jeho přechody ε.
Konstrukce
Vzhledem k regulárnímu výrazu EGlushkovův stavební algoritmus vytváří nedeterministický automat, který jazyk přijímá přijato E.[1][2]:59—61 Konstrukce využívá čtyři kroky:
Krok 1
Linearizace výrazu. Každé písmeno abecedy uvedené ve výrazu E je přejmenován, takže každé písmeno se v novém výrazu vyskytuje nejvýše jednou . Glushkovova konstrukce se v zásadě spoléhá na to představuje a místní jazyk . Nechat A být stará abeceda a nechat B být nový.
Krok 2a
Výpočet množin , , a . První, , je sada písmen, která se vyskytuje jako první písmeno slova z . Druhý, , je sada písmen, která mohou končit písmenem . Poslední, , je sada dvojic písmen, která se mohou vyskytovat ve slovech , tj. je to soubor faktorů délky dvou ze slov . Tyto sady jsou matematicky definovány
- ,
- ,
- .
Jsou počítány indukcí přes strukturu výrazu, jak je vysvětleno níže.
Krok 2b
Výpočet množiny který obsahuje prázdné slovo, pokud toto slovo patří , a jinak je prázdná množina. Formálně to tak je, kde označuje prázdné slovo.
Krok 3
Výpočet místní jazyk,[je zapotřebí objasnění ] jak je definováno , , , a . Podle definice je místní jazyk definován sadami P, D, a F je sada slov, která začínají písmenem P, zakončeno dopisem Da jejichž faktory délky 2 patří F; to znamená, že je to jazyk:
- ,
případně s prázdným slovem.
Výpočet automatu pro místní jazyk označený tímto linearizovaným výrazem je formálně známý jako Glushkovova konstrukce. Konstrukci automatu lze provést pomocí klasických konstrukčních operací: zřetězení, průnik a iterace automatu.
Krok 4
Mazání vymezení s každým písmenem B dopis A bývalo to.
Příklad
Zvážit[2]:60—61 regulární výraz.
- Linearizovaná verze je
- .
- Sady P, D, a F prvních písmen, posledních písmen a faktorů délky 2 pro lineární výraz
- .
- Automat místního jazyka
- .
- Získejte automat pro odstraněním indexů.
Výpočet sady písmen
Výpočet množin P, D, F, a Λ se provádí indukčně přes regulární výraz . Je třeba uvést hodnoty pro ∅, ε (symboly pro prázdný jazyk a singletonový jazyk obsahující prázdné slovo), písmena a výsledky operací .
- Pro Λ, jeden má
- ,
- ,
- pro každé písmeno A,
- ,
- , a
- .
- Pro P, jeden má
- ,
- pro každé písmeno A,
- ,
- , a
- .
Stejné vzorce se také používají pro D, s výjimkou produktu, kde
- .
- Pro množinu faktorů délky 2 jeden má
- pro každé písmeno A,
- ,
- , a
- .
Nejnákladnější operace jsou produkty sad pro výpočet F.
Vlastnosti
Získaný automat je nedeterministický a má tolik stavů, kolik je počet písmen regulárního výrazu plus jeden. Dále to bylo prokázáno[3]:215[4] že Glushkovův automat je stejný jako Thompsonův automat když jsou odstraněny ε-přechody.
Aplikace a deterministické výrazy
Výpočet automatu výrazem se vyskytuje často; byl systematicky používán při vyhledávacích funkcích, zejména u Unix grep příkaz. Podobně, XML Specifikace také používá takové konstrukce; pro větší efektivitu, pravidelné výrazy určitého druhu, tzv deterministické výrazy, byly studovány.[4][5]
Viz také
Poznámky a odkazy
- ^ V.M. Glushkov (1961). „Abstraktní teorie automatů“. Ruské matematické průzkumy (v Rusku). 16: 1–53. doi:10.1070 / rm1961v016n05abeh004112.
- ^ A b Jean-Éric Pin (listopad 2016). Matematické základy teorie automatů (PDF). Paříž.
- ^ Jacques Sakarovitch (únor 2003). Éléments de théorie des automates. Paříž: Vuibert. ISBN 978-2711748075.
- ^ A b Jacques Sakarovitch (2009). Základy teorie automatů. Cambridge: Cambridge University Press. ISBN 9780521844253.
- ^ Brüggemann-Klein, Anne (1993). "Regulární výrazy do konečných automatů". Teoretická informatika. 12 (2): 197–213. doi:10.1016/0304-3975(93)90287-4.