Thompsonsova konstrukce - Thompsons construction - Wikipedia

v počítačová věda, Thompsonova konstrukce algoritmus, nazývaný také McNaughton-Yamada-Thompsonův algoritmus^[1], je metoda transformace a regulární výraz do ekvivalentu nedeterministický konečný automat (NFA).^[2] Tuto NFA lze použít odpovídat řetězcům proti regulárnímu výrazu. Tento algoritmus je připsán na Ken Thompson.

Regulární výrazy a nedeterministické konečné automaty jsou dvě reprezentace formální jazyky. Například, zpracování textu obslužné programy používají k popisu pokročilých vyhledávacích vzorců regulární výrazy, ale NFA jsou vhodnější pro spuštění v počítači. Proto je tento algoritmus praktického zájmu, protože může kompilovat regulární výrazy do NFA. Z teoretického hlediska je tento algoritmus součástí důkazu, že oba přijímají přesně stejné jazyky, tj. běžné jazyky.

NFA lze 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. Může však být také NFA interpretováno přímo.

Chcete-li se rozhodnout, zda dva dané regulární výrazy popisují stejný jazyk, lze každý převést na ekvivalentní minimum deterministický konečný automat prostřednictvím konstrukce Thompsona, konstrukce výkonové sady, a Minimalizace DFA. Pokud a pouze pokud, výsledné automaty souhlasí až do přejmenování států, jazyky regulárních výrazů souhlasí.

Algoritmus

Algoritmus funguje rekurzivně rozdělením výrazu na jeho dílčí dílčí výrazy, ze kterých bude NFA vytvořena pomocí sady pravidel.^[3] Přesněji řečeno, z regulárního výrazu E, získaný automat A s přechodovou funkcí δ respektuje následující vlastnosti:

• A má přesně jeden počáteční stav q₀, který není přístupný z žádného jiného státu. To znamená pro každý stát q a jakýkoli dopis A, ${ displaystyle delta (q, a)}$ neobsahuje q₀.
• A má přesně jeden konečný stav q_F, který není společně přístupný z žádného jiného státu. To znamená pro jakýkoli dopis A, ${ displaystyle delta (q_ {f}, a) = emptyset}$.
• Nechat C být počet zřetězení regulárního výrazu E a nechte s být počet symbolů kromě závorek - to znamená, |, *, A a ε. Poté počet stavů A je 2s − C (lineární ve velikosti E).
• Počet přechodů opouštějících libovolný stav je nejvýše dva.
• Vzhledem k tomu, NFA m státy a nanejvýš E přechody z každého stavu se mohou shodovat s délkovým řetězcem n včas Ó(emn), Thompson NFA může provádět porovnávání vzorů v lineárním čase za předpokladu abecedy pevné velikosti.^{[4][je zapotřebí lepší zdroj ]}

Pravidla

Následující pravidla jsou znázorněna podle Aho et al. (2007),^[1] str. 122. V následujícím textu N(s) a N(t) jsou NFA dílčích výrazů s a t, resp.

The prázdný výraz ε se převede na

A symbol A vstupní abecedy se převede na

The odborový výraz s|t je převeden na

Stát q jde přes ε buď do počátečního stavu N(s) nebo N(t). Jejich konečné stavy se stávají přechodnými stavy celého NFA a spojují se dvěma e-přechody do konečného stavu NFA.

The zřetězení výraz Svatý je převeden na

Počáteční stav N(s) je počáteční stav celého NFA. Konečný stav N(s) se stane počátečním stavem N(t). Konečný stav N(t) je konečný stav celého NFA.

The Kleene hvězda výraz s^* je převeden na

Přechod ε spojuje počáteční a konečný stav NFA se sub-NFA N(s) mezi. Další přechod ε z vnitřního finále do vnitřního počátečního stavu N(s) umožňuje opakování výrazu s podle hvězdného operátora.

• The výraz v závorkách (s) se převede na N(s) sám.

S těmito pravidly pomocí prázdný výraz a symbol pravidla jako základní případy, je možné prokázat matematická indukce že jakýkoli regulární výraz lze převést na ekvivalentní NFA.^[1]

Příklad

Nyní jsou uvedeny dva příklady, malý neformální s výsledkem a větší s aplikací algoritmu krok za krokem.

Malý příklad

Příklad (ε | a * b) pomocí Thompsonovy konstrukce krok za krokem

Na následujícím obrázku je výsledek konstrukce Thompsona (ε | a * b). Růžový ovál odpovídá A, šedozelený ovál odpovídá A*, odpovídá zelený ovál b, oranžový ovál odpovídá a * ba modrý ovál odpovídá ε.

Aplikace algoritmu

NFA získané z regulárního výrazu (0|(1(01*(00)*0)*1)*)*

Jako příklad ukazuje obrázek výsledek Thompsonova konstrukčního algoritmu pro regulární výraz (0|(1(01*(00)*0)*1)*)* která označuje množinu binárních čísel, která jsou násobky 3:

{ε, „0“, „00“, „11“, „000“, „011“, „110“, „0000“, „0011“, „0110“, „1001“, „1100“, „1111“ , „00000“, ...}.

Pravá horní část ukazuje logickou strukturu (strom syntaxe) výrazu s „.“ označující zřetězení (předpokládá se, že má proměnnou arity); dílčí výrazy jsou pojmenovány A-q pro referenční účely. Levá část ukazuje nedeterministický konečný automat vyplývající z Thompsonova algoritmu, s vstup a výstup stav každého subexprese barevného v purpurová a tyrkysováŠtítek ε jako přechod je kvůli jasnosti vynechán - neoznačené přechody jsou ve skutečnosti přechody ε. Vstupní a výstupní stav odpovídající kořenovému výrazu q je počáteční a přijímací stav automatu, resp.

Kroky algoritmu jsou následující:

Ekvivalentní minimální deterministický automat je uveden níže.

Vztah k jiným algoritmům

Thompson's je jedním z několika algoritmů pro konstrukci NFA z regulárních výrazů;^[5] dřívější algoritmus dali McNaughton a Yamada.^[6] Konverzujte s konstrukcí Thompsona, Kleenův algoritmus transformuje konečný automat na regulární výraz.

Glushkovův konstrukční algoritmus je podobná Thompsonově konstrukci, jakmile jsou odstraněny přechody ε.

Reference