Konečný převodník () je konečný automat se dvěma paměťovými páskami podle terminologie používané pro Turingovy stroje: vstupní páskou a výstupní páskou. Tím se odlišuje od obyčejného konečného automatu, který má jen jednu pásku. Konečný převodník je typem konečného automatu, který provádí převod mezi dvěma množinami symbolů. Konečné převodníky lze považovat za zobecnění konečných automatů; zatímco konečný automat definuje formální jazyk určením množiny přijímaných řetězců, konečný převodník definuje relaci mezi množinami řetězců.

Konečný převodník čte řetězce ze vstupní pásky a generuje množinu relací na výstupní pásce. Na konečný převodník lze pohlížet jako na překladač nebo zařízení pro určení vztahů mezi množinami řetězců.

Při morfologické analýze může být vstupem konečného převodníku řetězec symbolů, a konečný převodník produkuje řetězec morfémů.

Úvod Pokud chápeme obsah vstupní pásky jako vstup automatu, pak říkáme, že automat přijímá řetězec. Jinými slovy, automat počítá funkci, která přiřazuje řetězcům hodnoty {0,1}. Alternativně můžeme říct, že automat generuje řetězec, pokud pohlížíme na jeho pásku jako na výstup. Při tomto přístupu automat generuje formální jazyk, který je sadou řetězců. Oba pohledy na automat jsou ekvivalentní: funkce, kterou automat počítá, je právě charakteristická funkce množiny řetězců, které generuje. Třída jazyků generovaných konečnými automaty se nazývá regulární jazyky.

Na dvě pásky převodníku obvykle pohlížíme jako na vstupní pásku a výstupní pásku. Při tomto přístupu převodník převádí (překládá) obsah své vstupní pásky na výstupní pásku, načtením řetězce ze vstupní pásky a vygenerováním jiného řetězce na výstupní pásku. Převodník může pracovat nedeterministicky, a může produkovat více než jeden výstup pro každý vstupní řetězec. Převodník může také neprodukovat žádný výstup pro daný vstupní řetězec, čemuž říkáme, že daný vstup odmítá. Obecně převodník počítá relaci mezi dvěma formálními jazyky.

Každý konečný převodník, který převádí jeden řetězec na druhý, ukazuje souvislost vstupní abecedy Σ s výstupní abecedou Γ. Relace R na Σ*×Γ*, které lze implementovat jako konečné převodníky se nazývají racionální relace. Racionální relace, které jsou zobrazeními (tj. přiřazují každému vstupnímu řetězci z Σ* nejvýše jeden řetězec z Γ*, se nazývají racionální funkce.

Konečné převodníky se často používají pro fonologickou a morfologickou analýzu při výzkumu i v aplikacích v oblasti zpracování přirozeného jazyka. K průkopníkům v této oblasti patří Ronald Kaplan, Lauri Karttunen, Martin Kay a Kimmo Koskenniemi. Obvyklým způsobem použití převodníků je tak zvaná „kaskáda“, kdy se převodníky pro různé operace kombinují do jediného převodníku opakovanou aplikací operátoru skládání relací (definovaného níže).

Formalní konstrukce Formálně je konečný převodník T šestice () taková, že:

je konečná množina stavů; je konečná množina nazývaná vstupní abeceda; je konečná množina nazývaná výstupní abeceda; je podmnožina množiny , množina počátečních stavů; je podmnožina , množina koncových stavů; a je přechodová relace (ε je prázdný řetězec).

Na (Q, δ) můžeme nahlížet jako na orientovaný graf, nazývaný přechodový graf T: množina vrcholů je Q a znamená, že existuje označená hrana jdoucí z vrcholu q do vrcholu r. Přitom a je vstupní návěstí a b výstupní návěstí této hrany.

Poznámka: Tato definice konečného převodníku se také nazývá písmenový převodník (Roche a Schabes 1997); existují alternativní definice, ale všechny mohou být převedeny na převodníky, jako je tento.

Definujeme rozšířenou přechodovou relaci jako nejmenší množinu takovou, že:

pro všechny ; a když a pak .

Rozšířená přechodová relace je v zásadě reflexivní a tranzitivní uzávěr přechodového grafu, který byl rozšířen o návěstí hran. Prvky se nazývají cesty. Návěstí cesty se získá zřetězením návěstí jednotlivých hran v tom pořadí, v jaké se procházely.

Chování převodníku T je racionální relace [T] definovaná takto: právě tehdy, když existuje a tak, že . To znamená, že T převádí řetězec na řetězec , pokud existuje cesta z počátečního stavu do koncového stavu, jejíž vstupní návěstí je x, a výstupní návěstí y.

Vážený konečný převodník Konečné převodníky lze rozšířit o váhy tak, že každému přechodu je přiřazeno nejen vstupní a výstupní návěstí, ale také váha. Vážený konečný převodník (

přičemž neplatí, pokud není zaručeno () nebo (). Skládání relací. Je-li dán převodník na abecedách Σ a Γ a převodník na abecedách Γ a Δ, existuje převodník na Σ a Δ takový, že právě tehdy, když existuje řetězec tak, že a . Tuto operaci lze rozšířit na vážené konečné převodníky.

Tato definice používá notaci používanou v matematice pro skládání relací. Nicméně obvyklé chápání skládání relací je jiné: jsou-li dány dvě relace a , , když existuje nějaké tak, že a

Projekce automatu. Existují dvě projekční funkce: zachovává vstupní pásku a zachovává výstupní pásku. První projekce je definována takto:

Je-li dán převodník , existuje konečný automat tak, že přijme x právě tehdy, když existuje řetězec y pro který

Druhá projekce je definovaná obdobně.

Determinizace. Je-li dán převodník , chceme vytvořit ekvivalentní převodník, které má jedinečná/jednoznačná počáteční stav a tak, že žádné dva přechody ponechává jakýkoli stav sdílí stejný vstupní návěstí. Pomocí podmnožinové konstrukce lze tuto vlastnost rozšířit na konečné převodníky i na vážené konečné převodníky, které se ale někdy nemusí zastavit; skutečně, některé nedeterministické převodníky nepřipouštějí ekvivalentní deterministické převodníky. Byly navrženy různé charakterizace determinizovatelných převodníků spolu s efektivními algoritmy, jak je testovat: spoléhají na vlastnosti polookruhu používaného ve váženém případě, i na obecné vlastnosti struktury převodníku (tzv. ). Ukládání () vah pro vážené konečné převodníky. Minimalizace vážených konečných převodníků. Odstranění epsilon přechodů.

Další vlastnosti konečných převodníků Je rozhodnutelné, zda relace [T] převodníku T je prázdná. Je rozhodnutelné, zda existuje řetězec y tak, že x[T]y pro daný řetězec x. Je nerozhodnutelné, zda dva převodníky jsou ekvivalentní. Ekvivalence je ale rozhodnutelná ve speciálním případě, když relace [T] převodníku T je zobrazení. Pokud definujeme abecedu návěstí , konečné převodníky jsou izomorfní s nedeterministickými konečnými automaty s abecedou , takže mohou být determinizovány (převedeny na deterministický konečný automat nad abecedou ) a následně minimalizovány, čímž se minimalizuje počet stavů.

Aplikace Kontextová přepisovací pravidla tvaru a → b / c _ d, používaná v lingvistice pro modelování fonologických pravidel a posouvání hlásek jsou výpočetně ekvivalentní s konečnými převodníky za předpokladu, že jejich aplikace není rekurzivní, tj. není povoleno, aby pravidla přepisovala stejný podřetězec opakovaně.

Vážené konečné převodníky se používají pro zpracování přirozeného jazyka, včetně strojového překladu a pro strojové učení. Jednou z komponent knihovny OpenGrmOpenGrm je implementace morfologického značkování.

Odkazy

Reference

Literatura

Související články Mealyho automat Mooreův stroj Morfologický slovník Foma (software) Stromový převodník Dvouúrovňová morfologie

Externí odkazy OpenFst, knihovna s otevřeným zdrojovým textem pro práci s konečnými převodníky. Stuttgart Finite State Transducer Tools, sada nástrojů s otevřeným zdrojovým textem pro konečné převodníky java FST Framework, Java FST Framework s otevřeným zdrojovým textem schopný zpracovávat textový formát OpenFst. Vcsn , platforma s otevřeným zdrojovým textem pro C++ & IPython pro vážené automaty a racionální výrazy. Finite State Morphology--The Book XFST/ LEXC, popis implementace konečných převodníků firmy Xerox určených pro lingvistické aplikace. FOMA, implementace s otevřeným zdrojovým textem většiny funkcionalit implementace XFST/LEXC firmy Xerox.

Kategorie:Konečné automaty