Lõplik muundur

Mall:Liita Lõplik muundur või lõplik olekumuundur on Turingi masinate terminoloogia kohaselt kahe mälulindiga (sisend- ja väljundlint) lõplik automaat. Tavalisel lõplikul automaadil on ainult üks mälulint. Lõplik muundur on lõplik automaat, mis seab omavahel vastavusse kaks hulka sümboleid.

Lõpliku muunduri mõiste on üldisem kui lõpliku automaadi oma. Lõplik automaat defineerib formaalse keele aktsepteeritavate sõnede hulga abil, samas kui lõplik muundur defineerib seosed sõnede hulkade vahel. Lõplik muundur loeb sisendlingilt sõnede hulga ning loob väljundlindile hulga seoseid. Lõplikku muundurit võib vaadata kui sõnedevahelist tõlki või sidujat.

Morfoloogilisest parsimisest võib näiteks tuua olukorra, kus muundurisse sisestatakse tähtedest koosnev sõne ning saadakse väljundiks morfeemidest koosnev sõne.

Ülevaade

Öeldakse, et automaat tuvastab sõne, kui vaatame selle lindi sisu sisendina. Teisisõnu leiab automaat funktsiooni, mis vastendab sõned hulga $\{0,1\}$ väärtustega. Samuti võime vaadelda automaadi linti väljundina ning öelda, et automaat genereerib sõnesid. Sel juhul loob automaat konkreetse sõnede hulga ehk formaalse keele. Need kaks viisi automaadi kirjeldamiseks on samaväärsed: automaadi genereeritud funktsioon on enda loodud sõnede hulga karakteristlik funktsioon. Lõpliku automaadi loodud keelte klassi nimetatakse regulaarsete keelte klassiks.

Muunduri kahte linti vaadeldakse tavaliselt kui sisend- ja väljundlinti. Öeldakse, et muundur muundab ehk tõlgib sisendlindil olevad väärtused väljundlindile - sisendlindile antud sõne jaoks genereeritakse väljundlindile uus sõne. Muundur võib seda teha mittedeterministlikult ning ühele sisendsõnele võib vastata mitu väljundsõne. Muundur võib sisendsõne ka tagasi lükata - sel juhul sisendsõnele vastavat väljundsõne ei genereerita.

Üldsõnaliselt võib öelda, et muundur arvutab välja suhte kahe formaalse keele vahel.

Iga sõnest-sõneks-tüüpi lõplik muundur vastendab sisendtähestiku $\mathrm{\Sigma }$ väljundtähestikuga $\mathrm{\Gamma }$. Relatsioone $R$ hulgal $\mathrm{\Sigma }*\times \mathrm{\Gamma }*$, mis on rakendatavad lõplike muunduritena, nimetatakse ratsionaalrelatsioonideks. Ratsionaalrelatsioone, mis on ühtlasi ka osafunktsioonid (ehk mis vastendavad iga sisendsõne hulgast $\mathrm{\Sigma }*$ kõige enam ühe sõnega hulgast $\mathrm{\Gamma }*$), nimetatakse ratsionaalfunktsioonideks.

Lõplikud muundurid leiavad sageli kasutust keeletehnoloogias fonoloogilise ning morfoloogilise analüüsi juures.

Formaalne kirjeldus

Formaalse kirjelduse järgi on lõplik muundur $T$ viiekohaline ennik $(Q,\mathrm{\Sigma },\mathrm{\Gamma },I,F,\delta )$, kus

• $Q$ on olekute hulk (lõplik hulk);
• $\mathrm{\Sigma }$ on sisendtähestik (lõplik hulk);
• $\mathrm{\Gamma }$ on väljundtähestik (lõplik hulk);
• $I$ on algolekute hulk ($Q$ alamhulk);
• $F$ on lõppolekute hulk ($Q$ alamhulk);
• kehtib $\delta \subseteq Q\times (\mathrm{\Sigma }\cup \{ϵ\})\times (\mathrm{\Gamma }\cup \{ϵ\})\times Q$, kus $ϵ$ on siirderelatsioonis tühi sõne.

Võime vaadata paari $(Q,\delta )$ kui sildistatud suunatud graafi ehk $T$ siirdegraafi. $Q$ on tippude hulk ning $(q,a,b,r)\in \delta$tähendab, et leidub sildistatud kaar tipust q tippu r. Ütleme, et a on selle kaare sisendi ning b väljundi silt.

Defineerime laiendatud siirderelatsiooni $\delta *$ kui vähima hulga, mille puhul kehtivad järgmised tingimused:

• $\delta \subseteq \delta \ast$;
• $(q,ϵ,ϵ,q)\in \delta *$iga $q\in Q$korral;
• alati kui kehtivad $(q,x,y,r)\in \delta *$ ja $(r,a,b,s)\in \delta *$, siis kehtib ka $(q,xa,yb,s)\in \delta *$.

Laiendatud siirderelatsioon on olemuslikult siirdegraafi refleksiivne transitiivne sulund, mis võtab arvesse ka servade silte. Ühe tee sildi leidmiseks konkateneeritakse seda teed moodustavate servade sildid kindlas järjekorras.

Muunduri $T$ käitumine on ratsionaalrelatsioon $[T]$, mida defineeritakse järgnevalt: $x[T]y$ siis ja ainult siis, kui leiduvad $i\in I$ja $f\in F$selliselt, et $(i,x,y,f)\in \delta *$. See tähendab, et $T$ muundab sõne $x\in \mathrm{\Sigma }*$sõneks $y\in \mathrm{\Gamma }*$, kui algolekust lõppolekuni viib tee, mille sisendi silt on x ning väljundi silt y.

Kaalutud automaat

Lõplikud muundurid võivad olla kaalutud. Sellised juhul on igal siirdel lisaks sisend- ja väljundsildile ka kaalu tähistav silt. Kaalutud lõplik muundur üle kaalude hulga K defineeritakse sarnaselt kaalumata muunduriga kaheksakohalise ennikuna $T=(Q,\mathrm{\Sigma },\mathrm{\Gamma },I,F,E,\lambda ,\rho )$, kus

• $Q,\mathrm{\Sigma },\mathrm{\Gamma },I,F$ defineeritakse samamoodi, kui ülalpool näidatud;
• $E\subseteq Q\times (\mathrm{\Sigma }\cup \{ϵ\})\times (\mathrm{\Gamma }\cup \{ϵ\})\times Q\times K$, kus ε tähistab tühisõnet, on lõplik siirete hulk;
• $\lambda :I\to K$ vastendab algolekud kaaludega;
• $\rho :F\to K$ vastendab lõppolekud kaaludega.

Võimaldamaks kaalutud lõpliku muunduri operatsioonide täpset defineerimist, kehtib nõue, et kaalude hulk peab moodustama poolringi. Kaks kõige tavalisemat poolringi varianti on log-poolring ja troopiline poolring. Kaalumata automaati võib vaadelda kui juhtu, mil kõik kaalud kuuluvad Booleani poolringi.

Tehted lõplike muunduritega

Järgnevad lõplikel automaatidel defineeritud tehted kehtivad ka lõplike muundurite puhul.

• Ühend. Kui on antud muundurid $T$ ja $S$, siis eksisteerib muundur $T\cup S$ nii, et $x[T\cup S]y$ kehtib siis ja ainult siis, kui kehtib $x[T]y$ või $x[S]y$.
• Konkatenatsioon. Kui on antud muundurid $T$ ja $S$, siis eksisteerib muundur $T\cdot S$nii, et $x[T\cdot S]y$siis ja ainult siis, kui leiduvad $x_1,x_2,y_1,y_2$ nii, et $x=x_1{x}_2,y=y_1{y}_2,x_1[T]y_1,x_2[S]y_2$.
• Kleene sulund. Kui on antud muundurid $T$ ja $S$, siis eksisteerib muundur T*, mille kohta kehtivad järgmised omadused:
  1. $ϵ[T*]ϵ$ (k1)
  2. kui $w[T*]y$ja $x[T]z$siis $wx[T*]yz$ (k2)
  3. ei kehti $x[T*]y$, kui just (k1) või (k2) vastupidist ei nõua.
• Kompositsioon. Kui on antud muundur $T$ üle tähestike $\mathrm{\Sigma }$ ja $\mathrm{\Gamma }$ ning muundur $S$ üle tähestike $\mathrm{\Gamma }$ ja $\mathrm{\Delta }$, siis eksisteerib muundur $T\circ S$üle tähestike $\mathrm{\Sigma }$ ja $\mathrm{\Delta }$ nii, et $x[T\circ S]z$siis ja ainult siis, kui leidub sõne $y\in \mathrm{\Gamma }*$nii, et $x[T]y$ja $y[S]z$. See tehe kehtib ka kaalutud juhu korral. See definitsioon järgib tähistust, mis on kasutusel matemaatikas relatsioonide kompositsiooni märkimiseks. Traditsiooniliselt loetakse relatsioonide kompositsiooni aga teisiti: kui on antud relatsioonid $T$ ja $S$, siis $(x,z)\in T\circ S$, kui leidub y selliselt, et $(x,y)\in S$ja $(y,z)\in T$.
• Projektsioon automaadiks. On antud kaks projektsiooni funktsiooni: ${\pi }_1$säilitab sisendlinti ning ${\pi }_2$väljundlinti. Funktsiooni ${\pi }_1$projektsioon defineeritakse järgnevalt: Kui on antud muundur $T$, siis leidub lõplik automaat ${\pi }_{1}T$ selliselt, et ${\pi }_{1}T$aktsepteerib sõne x siis ja ainult siis, kui leidub sõne y, mille puhul kehtib $x[T]y$. Teine projektsioon ${\pi }_2$defineeritakse analoogselt.
• Determineerimine. Kui on antud muundur $T$, soovime luua ekvivalentse muunduri, millel on ainult üks algolek ning mille puhul ei välju ühestki olekust mitu sama sisendsildiga kaart.
• Kaalutud muunduri minimeerimine.
• Epsilonsiirete eemaldamine.

Lõplike muundurite omadused

• On võimalik otsustada, kas muunduri $T$ relatsioon $[T]$ on tühi.
• On võimalik otsustada, kas leidub sõne y selliselt, et antud sõne x puhul kehtiks $x[T]y$.
• Ei ole võimalik otsustada, kas kaks muundurit on ekvivalentsed. Ekvivalentsuse üle on võimalik otsustada erijuhul, kus muunduri $T$ relatsioon $[T]$ on osafunktsioon.

Rakendused

Kaalutud lõplikud muundurid on kasutusel keeletehnoloogias, muuhulgas masintõlke ning masinõppe juures.