Konečný převodník

Konečný převodník (Šablona:Vjazyce2) 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ů.Šablona:Sfn 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.Šablona:Sfn 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 (Šablona:Math) taková, že:

• Šablona:Mvar je konečná množina stavů;
• Šablona:Math je konečná množina nazývaná vstupní abeceda;
• Šablona:Math je konečná množina nazývaná výstupní abeceda;
• Šablona:Mvar je podmnožina množiny Šablona:Mvar, množina počátečních stavů;
• Šablona:Mvar je podmnožina Šablona:Mvar, množina koncových stavů; a
• $\delta \subseteq Q\times (\mathrm{\Sigma }\cup \{ϵ\})\times (\mathrm{\Gamma }\cup \{ϵ\})\times Q$ 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 $(q,a,b,r)\in \delta$ 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 ${\delta }^{*}$ jako nejmenší množinu takovou, že:

• $\delta \subseteq {\delta }^{*}$;
• $(q,ϵ,ϵ,q)\in {\delta }^{*}$ pro všechny $q\in Q$; a
• když $(q,x,y,r)\in {\delta }^{*}$ a $(r,a,b,s)\in \delta$ pak $(q,xa,yb,s)\in {\delta }^{*}$.

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 ${\delta }^{*}$ 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: $x[T]y$ právě tehdy, když existuje $i\in I$ a $f\in F$ tak, že $(i,x,y,f)\in {\delta }^{*}$. To znamená, že T převádí řetězec $x\in {\mathrm{\Sigma }}^{*}$ na řetězec $y\in {\mathrm{\Gamma }}^{*}$, 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 (Šablona:Vjazyce2 Šablona:Vzorec

přičemž $x[T^{*}]y$ neplatí, pokud není zaručeno (Šablona:Odkaz na vzorec) nebo (Šablona:Odkaz na vzorec).

• Skládání relací. Je-li dán převodník Šablona:Mvar na abecedách Σ a Γ a převodník Šablona:Mvar na abecedách Γ a Δ, existuje převodník $T\circ S$ na Σ a Δ takový, že $x[T\circ S]z$ právě tehdy, když existuje řetězec $y\in {\mathrm{\Gamma }}^{*}$ tak, že $x[T]y$ a $y[S]z$. Tuto operaci lze rozšířit na vážené konečné převodníky.Šablona:Sfn

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 Šablona:Mvar a Šablona:Mvar, $(x,z)\in T\circ S$, když existuje nějaké Šablona:Mvar tak, že $(x,y)\in S$ a $(y,z)\in T.$

• Projekce automatu. Existují dvě projekční funkce: ${\pi }_1$ zachovává vstupní pásku a ${\pi }_2$ zachovává výstupní pásku. První projekce ${\pi }_1$ je definována takto:

Je-li dán převodník Šablona:Mvar, existuje konečný automat ${\pi }_{1}T$ tak, že ${\pi }_{1}T$ přijme x právě tehdy, když existuje řetězec y pro který $x[T]y.$

Druhá projekce ${\pi }_2$ je definovaná obdobně.

• Determinizace. Je-li dán převodník Šablona:Mvar, 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.Šablona:Sfn Byly navrženy různé charakterizace determinizovatelných převodníkůŠablona:Sfn spolu s efektivními algoritmy, jak je testovat:Šablona:Sfn spoléhají na vlastnosti polookruhu používaného ve váženém případě, i na obecné vlastnosti struktury převodníku (tzv. Šablona:Cizojazyčně).
• Ukládání (Šablona:Vjazyce2)Šablona:Ujasnit vah pro vážené konečné převodníky.Šablona:Sfn
• Minimalizace vážených konečných převodníků.Šablona:Sfn
• 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í.Šablona:Sfn 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í $L=(\mathrm{\Sigma }\cup \{ϵ\})\times (\mathrm{\Gamma }\cup \{ϵ\})$, konečné převodníky jsou izomorfní s nedeterministickými konečnými automaty s abecedou $L$, takže mohou být determinizovány (převedeny na deterministický konečný automat nad abecedou $L=[(\mathrm{\Sigma }\cup \{ϵ\})\times \mathrm{\Gamma }]\cup [\mathrm{\Sigma }\times (\mathrm{\Gamma }\cup \{ϵ\})]$) a následně minimalizovány, čímž se minimalizuje počet stavů.Šablona:Doplňte zdroj

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ě.Šablona:Sfn

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í.Šablona:SfnŠablona:Sfn Jednou z komponent knihovny OpenGrm je implementace morfologického značkování.

Odkazy

Literatura

• Šablona:Citace periodika
• Šablona:Citace monografie
• Šablona:Citace monografie
• Šablona:Citace monografie
• Šablona:Citace elektronické monografie
• Šablona:Citace periodika
• Šablona:Citace monografie
• Šablona:Citace monografie
• Šablona:Citace elektronické monografie
• Šablona:Citace monografie
• Šablona:Citace monografie
• Šablona:Citace monografie Šablona:Wayback
• Šablona:Citace monografie
• Šablona:Citace periodika
• Šablona:Citace monografie
• Šablona:Citace monografie
• Šablona:Citace elektronické monografie

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 Šablona:Wayback, 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 Šablona:Wayback 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.