Lõplik muundur

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  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  väljundtähestikuga . Relatsioone  hulgal , mis on rakendatavad lõplike muunduritena, nimetatakse ratsionaalrelatsioonideks. Ratsionaalrelatsioone, mis on ühtlasi ka osafunktsioonid (ehk mis vastendavad iga sisendsõne hulgast  kõige enam ühe sõnega hulgast ), 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  viiekohaline ennik , kus

 on olekute hulk (lõplik hulk);
 on sisendtähestik (lõplik hulk);
 on väljundtähestik (lõplik hulk);
 on algolekute hulk ( alamhulk);
 on lõppolekute hulk ( alamhulk);
 kehtib , kus  on siirderelatsioonis tühi sõne.

Võime vaadata paari  kui sildistatud suunatud graafi ehk  siirdegraafi.  on tippude hulk ning 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  kui vähima hulga, mille puhul kehtivad järgmised tingimused:

 ;
 iga korral;
 alati kui kehtivad  ja , siis kehtib ka .

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  käitumine on ratsionaalrelatsioon , mida defineeritakse järgnevalt:  siis ja ainult siis, kui leiduvad ja selliselt, et . See tähendab, et  muundab sõne sõneks , 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 , kus

 defineeritakse samamoodi, kui ülalpool näidatud;
 , kus ε tähistab tühisõnet, on lõplik siirete hulk;
 vastendab algolekud kaaludega;
 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  ja , siis eksisteerib muundur  nii, et  kehtib siis ja ainult siis, kui kehtib  või .
 Konkatenatsioon. Kui on antud muundurid  ja , siis eksisteerib muundur nii, et siis ja ainult siis, kui leiduvad  nii, et .
 Kleene sulund. Kui on antud muundurid  ja , siis eksisteerib muundur T*, mille kohta kehtivad järgmised omadused:
    (k1)
 kui ja siis     (k2)
 ei kehti , kui just (k1) või (k2) vastupidist ei nõua.
 Kompositsioon. Kui on antud muundur  üle tähestike  ja  ning muundur  üle tähestike  ja , siis eksisteerib muundur üle tähestike  ja  nii, et siis ja ainult siis, kui leidub sõne nii, et ja . 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  ja , siis , kui leidub y selliselt, et ja .
 Projektsioon automaadiks. On antud kaks projektsiooni funktsiooni: säilitab sisendlinti ning väljundlinti. Funktsiooni projektsioon defineeritakse järgnevalt:  Kui on antud muundur , siis leidub lõplik automaat  selliselt, et aktsepteerib sõne x siis ja ainult siis, kui leidub sõne y, mille puhul kehtib .  Teine projektsioon defineeritakse analoogselt.
 Determineerimine. Kui on antud muundur , 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  relatsioon  on tühi.
 On võimalik otsustada, kas leidub sõne y selliselt, et antud sõne x puhul kehtiks .
 Ei ole võimalik otsustada, kas kaks muundurit on ekvivalentsed. Ekvivalentsuse üle on võimalik otsustada erijuhul, kus muunduri  relatsioon  on osafunktsioon.

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

Viited