Zobrazení zdroje stránky Konečný převodník

'''Konečný převodník''' ({{Vjazyce2|en|''finite-state transducer'', ''FST''}}) je [[konečný automat]] se dvěma paměťovými ''páskami'' podle terminologie používané pro [[Turingův stroj|Turingovy stroje]]: vstupní páskou a výstupní páskou. Tím se odlišuje od obyčejného [[konečný automat|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ů.{{sfn|Jurafsky09}} 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í jazyk]]y.

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 [[Nedeterministický algoritmus|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á [[relace (matematika)|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í (matematika)|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 [[fonologie|fonologickou]] a [[morfologie (lingvistika)|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]].{{sfn|Koskenniemi83}}
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 ({{math|''Q'', Σ, Γ, ''I'', ''F'', δ}}) taková, že:

* {{mvar|Q}} je [[konečná množina]] ''stavů'';
* {{math|Σ}} je konečná množina nazývaná ''vstupní abeceda'';
* {{math|Γ}} je konečná množina nazývaná ''výstupní abeceda'';
* {{mvar|I}} je [[podmnožina]] množiny {{mvar|Q}}, množina ''počátečních stavů'';
* {{mvar|F}} je podmnožina {{mvar|Q}}, množina ''koncových stavů''; a
* <math>\delta \subseteq Q \times (\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\}) \times Q</math> 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 <math>(q,a,b,r)\in\delta</math> 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'' <math>\delta^*</math> jako nejmenší množinu takovou, že:

* <math>\delta\subseteq\delta^*</math>;
* <math>(q,\epsilon,\epsilon,q)\in\delta^*</math> pro všechny <math>q\in Q</math>; a
* když <math>(q,x,y,r) \in \delta^*</math> a <math>(r,a,b,s) \in \delta</math> pak <math>(q,xa,yb,s) \in \delta^*</math>.

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 <math>\delta^*</math> 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: <math>x[T]y</math> právě tehdy, když existuje <math>i \in I</math> a <math>f \in F</math> tak, že <math>(i,x,y,f) \in \delta^*</math>. To znamená, že ''T'' převádí řetězec <math>x\in\Sigma^*</math> na řetězec <math>y\in\Gamma^*</math>, 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 ({{Vjazyce2|en|''Weighted Finite State Transducer'', ''WFST'') s množinou vah ''K'' lze definovat obdobně jako převodník bez vah – jako osmici {{math|1=''T''=(''Q'', Σ, Γ, ''I'', ''F'', ''E'', ''λ'', ''ρ'')}}, kde:
* {{math|''Q'', Σ, Γ, ''I'', ''F''}} jsou definovány jako výše;
* <math> E \subseteq Q \times (\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\}) \times Q \times K</math> (kde ''ε'' je [[prázdný řetězec]]) je konečná množina přechodů;
* <math>\lambda:  I \rightarrow K </math> přiřazuje váhy počátečním stavům;
* <math>\rho: F \rightarrow K </math> přiřazuje váhy koncovým stavům.
Aby byly určité operace na vážených konečných převodnících dobře definované, je vhodné vyžadovat, aby množina vah tvořila [[polookruh]].{{sfn|Rational series|s=16}}
Dva typické polookruhy používané v praxi jsou [[logaritmický polookruh]] a [[tropický polookruh]]: automaty bez vah mohou být považovány za automaty, jejichž váhy jsou v [[Booleovský polookruh|booleovském polookruhu]].{{sfn|Lothaire05}}

=== Stochastické konečné převodníky ===
Stochastické konečné převodníky (nazývané také pravděpodobnostní konečné převodníky nebo statistické konečné převodníky) jsou podle všeho tvarem vážených konečných převodníků.{{Doplňte zdroj
 | datum = duben 2017}}

== Operace na konečných převodnících ==
Následující operace definované na konečných automatech lze také aplikovat na konečné převodníky:

* [[Sjednocení]]. Jsou-li dány převodníky {{mvar|T}} a {{mvar|S}}, existuje převodník <math>T\cup S</math> tak, že <math>x[T\cup S]y</math> právě tehdy, když <math>x[T]y</math> nebo <math>x[S]y</math>.
* [[Zřetězení]]. Jsou-li dány převodníky {{mvar|T}} a {{mvar|S}}, existuje převodník <math>T\cdot S</math> tak, že <math>x[T\cdot S]y</math> právě tehdy, když existuje <math>x_1, x_2, y_1, y_2</math> s <math>x=x_1x_2, y =y_1y_2, x_1[T]y_1</math> a <math>x_2[S]y_2.</math>
* [[Kleeneho hvězdička|Kleeneho uzávěr]]. Je-li dán převodník {{mvar|T}}, existuje převodník <math>T^*</math> s následujícími vlastnostmi:
{{Vzorec|<math>\epsilon[T^*]\epsilon</math>,|k1}}}}
{{Vzorec|pokud <math>w[T^*]y</math> a <math>x[T]z</math>, pak <math>wx[T^*]yz</math>;|k2}}
:: přičemž <math>x[T^*]y</math> neplatí, pokud není zaručeno ({{Odkaz na vzorec|k1}}) nebo ({{Odkaz na vzorec|k2}}).
* [[Skládání relací]]. Je-li dán převodník {{mvar|T}} na abecedách Σ a Γ a převodník {{mvar|S}} na abecedách Γ a Δ, existuje převodník <math>T \circ S</math> na Σ a Δ takový, že <math>x[T \circ S]z</math> právě tehdy, když existuje řetězec <math>y\in\Gamma^*</math> tak, že <math>x[T]y</math> a <math>y[S]z</math>. Tuto operaci lze rozšířit na vážené konečné převodníky.{{sfn|Mohri|2004|s=3–5}}

: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 {{mvar|T}} a {{mvar|S}}, <math>(x,z)\in T\circ S</math>, když existuje nějaké {{mvar|y}} tak, že <math>(x,y)\in S</math> a <math>(y,z)\in T.</math>

* [[Projekce (lineární algebra)|Projekce]] automatu. Existují dvě projekční funkce: <math>\pi_1</math> zachovává vstupní pásku a <math>\pi_2</math> zachovává výstupní pásku. První projekce <math>\pi_1</math> je definována takto:

: Je-li dán převodník {{mvar|T}}, existuje konečný automat <math>\pi_1 T</math> tak, že <math>\pi_1 T</math> přijme ''x'' právě tehdy, když existuje řetězec ''y'' pro který <math>x[T]y.</math>

:Druhá projekce <math>\pi_2</math> je definovaná obdobně.

* [[Determinizace]]. Je-li dán převodník {{mvar|T}}, 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|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.{{sfn|van Noord|Gerdemann}} Byly navrženy různé [[Charakterizace (matematika)|charakterizace]] determinizovatelných převodníků{{sfn|Mohri|2004|s=5–6}} spolu s efektivními algoritmy, jak je testovat:{{sfn|Allauzen|Mohri|2003}} spoléhají na vlastnosti [[polookruh]]u používaného ve váženém případě, i na obecné vlastnosti struktury převodníku (tzv. {{Cizojazyčně|en|''[[twins property]]''}}).
* Ukládání ({{Vjazyce2|en|''pushing''}}){{Ujasnit}} vah pro vážené konečné převodníky.{{sfn|Mohri|2004|s=7–9}}
* Minimalizace vážených konečných převodníků.{{sfn|Mohri|2004|s=9–11}}
* Odstranění [[Nedeterministický konečný automat|epsilon přechodů]].

== Další vlastnosti konečných převodníků ==
* Je [[Rozhodnutelnost|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ý problém|nerozhodnutelné]], zda dva převodníky jsou ekvivalentní.{{sfn|Griffiths|1968}} 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í <math>L=(\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\})</math>, konečné převodníky jsou izomorfní s [[nedeterministický konečný automat|nedeterministickými konečnými automaty]] s abecedou <math>L</math>, takže mohou být determinizovány (převedeny na [[deterministický konečný automat]] nad abecedou <math>L=[(\Sigma\cup\{\epsilon\}) \times \Gamma] \cup [\Sigma \times (\Gamma\cup\{\epsilon\})]</math>) a následně minimalizovány, čímž se minimalizuje počet stavů.{{Doplňte zdroj
 | datum = září 2008}}

== Aplikace ==
Kontextová přepisovací pravidla tvaru ''a'' → ''b'' / ''c'' _ ''d'', používaná v [[lingvistika|lingvistice]] pro modelování [[fonologické pravidlo|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ě.{{sfn|Kaplan|Kay}}

Vážené konečné převodníky se používají pro [[zpracování přirozeného jazyka]], včetně [[strojový překlad|strojového překladu]] a pro [[strojové učení]].{{sfn|Knight|May|2009}}{{sfn|Cortes|Mohri}} Jednou z komponent knihovny OpenGrm<ref>[http://opengrm.org/ OpenGrm]</ref> je implementace [[Morfologické značkování|morfologického značkování]].

== Odkazy ==

=== Reference ===
{{Překlad|en|Finite-state transducer|931226956}}<references />

=== Literatura ===
* {{Citace periodika
 | ref = harv
 | příjmení = Allauzen
 | jméno = Cyril
 | příjmení2 = Mohri
 | jméno2 = Mehryar
 | titul = Efficient Algorithms for Testing the Twins Property
 | periodikum = Journal of Automata, Languages and Combinatorics
 | rok = 2003
 | ročník = 8
 | číslo = 2
 | strany = 117–144
 | url = http://www.cs.nyu.edu/~mohri/pub/twins.pdf
 | datum přístupu = 2020-05-06
 | url archivu = https://web.archive.org/web/20120318032710/http://www.cs.nyu.edu/~mohri/pub/twins.pdf
 | datum archivace = 2012-03-18
 | nedostupné = ano
}}
* {{Citace monografie
 | příjmení = Beesley
 | jméno = Kenneth R.
 | jméno2 = Lauri
 | příjmení2 = Karttunen
 | titul = Finite State Morphology
 | vydavatel = Center for the Study of Language and Information
 | rok = 2003
 | isbn = 1-57586-434-7
}}
* {{Citace monografie
 | příjmení = Berstel
 | jméno = Jean
 | příjmení2 = Reutenauer
 | jméno2 = Christophe
 | titul = Noncommutative rational series with applications
 | edice = Encyclopedia of Mathematics and Its Applications
 | ročník = 137
 | místo = Cambridge
 | vydavatel = [[Cambridge University Press]]
 | rok = 2011
 | isbn = 978-0-521-19022-0
 | zbl = 1250.68007
 | ref = Rational series
}}
* {{Citace monografie
 | příjmení = Berstel
 | jméno = Jean
 | titul = Transductions and Context-free Languages
 | vydavatel = Teubner Verlag
 | rok = 1979
 | url = http://www-igm.univ-mlv.fr/~berstel/LivreTransductions/LivreTransductions.html
 | poznámka = Volná PDF verze
}}
* {{Citace elektronické monografie
 | ref = harv
 | jméno = Corinna
 | příjmení = Cortes
 | jméno2 = Mehryar
 | příjmení2 = Mohri
 | url = http://www.cs.nyu.edu/~mohri/pub/fsmnlp08.pdf
 | titul = Learning with Weighted Transducers
 | datum přístupu = 2017-04-29
}}
* {{Citace periodika
 | ref = harv
 | příjmení = Griffiths
 | jméno = T. V.
 | titul = The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
 | periodikum = Journal of the ACM
 | doi = 10.1145/321466.321473
 | url = https://doi.org/10.1145/321466.321473
 | rok = 1968
 | ročník = 15
 | číslo = 3
 | strany = 409–413
 | vydavatel = ACM
}}
* {{Citace monografie
 | ref = Jurafsky09
 | titul = Speech and Language Processing
 | příjmení = Jurafsky
 | jméno = Daniel
 | vydavatel = Pearson
 | rok = 2009
 | isbn = 9789332518414
 | místo = 
}}
* {{Citace monografie
 | příjmení = Jurafsky
 | jméno = Daniel
 | příjmení2 = Martin
 | jméno2 = James H.
 | titul = Speech and Language Processing
 | url = https://archive.org/details/speechlanguagepr00jura
 | vydavatel = Prentice Hall
 | rok = 2000
 | isbn = 0-13-095069-6
 | strany = [https://archive.org/details/speechlanguagepr00jura/page/n71 71]–83
}}
* {{Citace elektronické monografie
 | jméno = Ronald M.
 | příjmení = Kaplan
 | jméno2 = Martin
 | příjmení2 = Kay
 | ref = harv
 | url = http://acl.ldc.upenn.edu/J/J94/J94-3001.pdf
 | titul = Regular Models of Phonological Rule Systems
 | datum přístupu = 2012-08-25
 | url archivu = https://web.archive.org/web/20101011225829/http://acl.ldc.upenn.edu/J/J94/J94-3001.pdf
 | datum archivace = 2010-10-11
 | url-status = mrvý
}}
* {{Citace monografie
 | jméno = Kevin
 | příjmení = Knight
 | jméno2 = Jonathan
 | příjmení2 = May
 | ref = harv
 | sestavitel = Manfred Droste
 | sestavitel2 = Werner Kuich
 | sestavitel3 = Heiko Vogler
 | titul = Handbook of Weighted Automata
 | rok = 2009
 | vydavatel = Springer Science & Business Media
 | isbn = 978-3-642-01492-5
 | kapitola = Applications of Weighted Automata in Natural Language Processing
}}
* {{Citace monografie
 | příjmení = Kornai
 | jméno = Andras
 | titul = Extended Finite State Models of Language
 | url = https://archive.org/details/extendedfinitest0000unse
 | vydavatel = Cambridge University Press
 | rok = 1999
 | isbn = 0-521-63198-X
}}
* {{Citace monografie
 | ref = Koskenniemi83
 | příjmení = Koskenniemi
 | jméno = Kimmo
 | odkaz na autora = Kimmo Koskenniemi
 | titul = [[Dvouúrovňová morfologie|Two-level morphology]]: A general computational model of word-form recognition and production
 | vydavatel = Department of General Linguistics, [[Helsinská univerzita|University of Helsinki]]
 | rok = 1983
 | místo = Helsinky
 | počet stran = 160
 | jazyk = en
 | isbn = 951-45-3201-5
 | url = http://www.ling.helsinki.fi/~koskenni/doc/Two-LevelMorphology.pdf
 | datum přístupu = 2020-05-06
 }} {{Wayback|url=http://www.ling.helsinki.fi/~koskenni/doc/Two-LevelMorphology.pdf |date=20181221032913 }}
* {{Citace monografie
 | ref = Lothaire05
 | příjmení = Lothaire
 | jméno = M.
 | odkaz na autora = M. Lothaire
 | titul = Applied combinatorics on words
 | ostatní = Kolektivní dílo: Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, [[Gesine Reinert]], Sophie Schbath, Michael Waterman, Philippe Jacquet, [[Wojciech Szpankowski]], Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche a [[Valérie Berthé]]
 | edice = Encyclopedia of Mathematics and Its Applications
 | ročník = 105
 | místo = Cambridge
 | vydavatel = [[Cambridge University Press]]
 | rok = 2005
 | isbn = 0-521-84802-4
 | zbl = 1133.68067
 | strany = [https://archive.org/details/appliedcombinato0000loth/page/211 211]
 | url = https://archive.org/detaily/appliedcombinato0000loth/page/211
}}
* {{Citace periodika
 | ref = harv
 | příjmení = Mohri
 | jméno = Mehryar
 | titul = Weighted Finite-State Transducer Algorithms: An Overview
 | periodikum = Formal Languages and Application
 | rok = 2004
 | ročník = 148
 | číslo = 620
 | strany = 551–564
 | url = http://www.cs.nyu.edu/~mohri/pub/fla.pdf
 | doi = 10.1007/978-3-540-39886-8_29
}}
* {{Citace monografie
 | příjmení = Roark
 | jméno = Brian
 | jméno2 = Richard
 | příjmení2 = Sproat
 | titul = Computational Approaches to Morphology and Syntax
 | vydavatel = Oxford University Press
 | rok = 2007
 | isbn = 0-19-927478-9
}}
* {{Citace monografie
 | ref = harv
 | příjmení = Roche
 | jméno = Emmanuel
 | jméno2 = Yves
 | příjmení2 = Schabes
 | titul = Finite-state language processing
 | url = https://archive.org/details/finitestatelangu00roch
 | vydavatel = MIT Press
 | rok = 1997
 | isbn = 0-262-18182-7
 | strany = [https://archive.org/details/finitestatelangu00roch/page/n15 1]–65
}}
* {{Citace elektronické monografie
 | ref = harv
 | titul = Finite State Transducers with Predicates and Identities
 | jméno = Gertjan
 | příjmení = van Noord
 | jméno2 = Dale
 | příjmení2 = Gerdemann
 | url = http://www.let.rug.nl/~vannoord/papers/preds/node22.html
}}

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

=== Externí odkazy ===
* [http://openfst.org/ OpenFst], knihovna s [[Svobodný software|otevřeným zdrojovým textem]] pro práci s konečnými převodníky.
* [http://www.cis.uni-muenchen.de/~schmid/tools/SFST/ Stuttgart Finite State Transducer Tools], sada nástrojů s [[Svobodný software|otevřeným zdrojovým textem]] pro konečné převodníky
* [http://jsalatas.ictpro.gr/java-fst-framework-api-review/ java FST Framework], Java FST Framework s [[Svobodný software|otevřeným zdrojovým textem]] schopný zpracovávat textový formát OpenFst.
* [http://vcsn.lrde.epita.fr/ Vcsn] {{Wayback|url=http://vcsn.lrde.epita.fr/ |date=20200623094748 }}, platforma s [[Svobodný software|otevřeným zdrojovým textem]] pro C++ & IPython pro vážené automaty a racionální výrazy.
* [http://web.stanford.edu/~laurik/fsmbook/home.html Finite State Morphology--The Book] {{Wayback|url=http://web.stanford.edu/~laurik/fsmbook/home.html |date=20200919004916 }} XFST/ LEXC, popis implementace konečných převodníků firmy Xerox určených pro lingvistické aplikace.
* [https://code.google.com/archive/p/foma/ FOMA], implementace s [[Svobodný software|otevřeným zdrojovým textem]] většiny funkcionalit implementace XFST/LEXC firmy Xerox.

{{Formální jazyky a gramatiky}}

{{Autoritní data}}
{{Portály|Matematika}}

[[Kategorie:Konečné automaty]]