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 formula_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 formula_2 väljundtähestikuga formula_3. Relatsioone formula_4 hulgal formula_5, mis on rakendatavad lõplike muunduritena, nimetatakse ratsionaalrelatsioonideks. Ratsionaalrelatsioone, mis on ühtlasi ka osafunktsioonid (ehk mis vastendavad iga sisendsõne hulgast formula_6 kõige enam ühe sõnega hulgast formula_7), 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 formula_8 viiekohaline ennik formula_9, kus
Võime vaadata paari formula_19 kui sildistatud suunatud graafi ehk formula_8 siirdegraafi. formula_10 on tippude hulk ning formula_22tähendab, et leidub sildistatud kaar tipust q tippu r. Ütleme, et a on selle kaare sisendi ning b väljundi silt.
Defineerime laiendatud siirderelatsiooni formula_23 kui vähima hulga, mille puhul kehtivad järgmised tingimused:
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 formula_8 käitumine on ratsionaalrelatsioon formula_31, mida defineeritakse järgnevalt: formula_32 siis ja ainult siis, kui leiduvad formula_33ja formula_34selliselt, et formula_35. See tähendab, et formula_8 muundab sõne formula_37sõneks formula_38, 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 formula_39, kus
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.
Rakendused.
Kaalutud lõplikud muundurid on kasutusel keeletehnoloogias, muuhulgas masintõlke ning masinõppe juures.