Lõplik olekumuundur

Lõplikuks olekumuunduriks nimetatakse lõplikku olekumasinat, millel on kaks mälulinti: sisend ja väljund. Tavalisel lõplikul olekumasinal on vaid üks mälulint. Lõplik olekumuundur on selline lõpliku oleku automaat, mis kaardistab kahe hulga sümbolite vahel. Lõpliku olekuga automaat defineerib formaalse keele määrates hulga masina poolt aktsepteeritud sõnu, aga olekumuundur defineerib suhted sõnade vahel, seetõttu peetakse lõplikku olekumuundurit ka üldisemaks kui lõplikku oleku automaati.

Ülevaade

Öeldakse, et automaat tunneb sõne ära, kui ta arvutab funktsiooni, mis kaardistab sõned hulka {0,1}. Alternatiivselt võime öelda, et automaat genereerib sõnu, sellel juhul vaatame masina väljundlinti. Selles vaates genereerib automaat formaalse keele, mis on sõnede hulk.

Neid kahte linti vaadatakse muunduril tavaliselt kui sisend- ja väljundlinti. Selles vaates öeldakse, et muundur muudab (tõlgib) sisendlindi sisu väljundlindile ehk sisendiks tuleb üks sõna, mille automaat aktsepteerib ja genereerib selle pealt väljundiks mingi uue sõna. Seda võib automaat teha ka mittedeterministlikult ja ühe sisendiga võib olla mitu erinevat väljundit. On ka võimalik, et lõplik olekumuundur ei annagi mingi sisendiga väljundit. Sellisel juhul öeldakse, et masin lükkas sisendi tagasi. Iga sõnest sõne tegev lõplik olekumuundur teeb sisendsõnastiku (Σ) ja väljundsõnastiku (Γ) vahelise suhte. Relatsioon R Σ*×Γ* peal, mida saab implementeerida kui lõplikku olekumuundurit, nimetatakse ratsionaalseks relatsiooniks. Ratsionaalsed relatsioonid, mis seostavad iga sõne Σ*-st maksimaalselt ühe sõnega Γ*-st, nimetatakse ratsionaalseteks funktsioonideks

Selle alal kuuluvad tegijate hulka näiteks Ronald Kaplan, Lauri Karttunen, Martin Klay ja Kimmo Koskenniemi.

Lõplikku olekumuundurit kasutatakse tihti näiteks keelte morfoloogilises analüüsis loomulike keelte töötlemises, uurimustes ja rakendustes..

Formaalne konstruktsioon

Formaalselt on lõplik muundur T 6-ennik ({Q, Σ, Γ, I, F, δ}) selliselt:

• {Q} on lõplik hulk, kuhu kuuluvad olekud;
• {Σ} lõplik hulk, nimetatakse sisendsõnastikuks;
• {Γ} lõplik hulk, nimetatakse väljundsõnastikuks;
• {I} on {Q} alamhulk, algolekute hulk;
• {F} on {Q} alamhulk, lõppolekute hulk;
• $\delta \subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q$ (kus ε on tühi sõne) on üleminekute relatsioon.

Me võime vaadata (Q, δ) kui märgistatud suunatud graafi. Graafi tippude hulk on Q ja $(q,a,b,r)\in \delta$ tähendab, et meil on märgistatud serv, mis läheb tipust q tippu r. Samuti saame öelda, et a on selle serva sisend ja b serva väljund.

Kaaludega automaat

Lõplik olekumuundur võib olla kaaludega, mis tähendab, et iga üleminek on märgistatud kaaluga lisaks sisend- ja väljundsiltidele. Kaalutud lõplik olekumuundur üle kaalude hulga K saab defineerida sarnaselt kaalumata muundurile 8-ennikuna {T=(Q, Σ, Γ, I, F, E, λ, ρ), kus

• {Q, Σ, Γ, I, F} on defineeritud nagu kaaludeta variandil;
• $E\subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q\times K$ (kus ε on tühi sõne) on lõplik üleminekute hulk;
• $\lambda :I\rightarrow K$ määrab algsed olekud kaaludele;
• $\rho :F\rightarrow K$ määrab lõplikud olekud kaaludele.

Selleks, et teha kindlaid operatsioone kaalutud lõplikus olekumuunduris paremini defineerituks, on mugav pärida, et kaalude hulk moodustaks semiringi.. Kõige sagedasemad semiringi variandid logaritmiline semiring ja troopiline semiring. Kui kõik kaalud kuuluvad tõeväärtuse (Boolean) semiringi, siis vaatleme seda kui kaaludeta automaati.