Bimaskin

Ein bimaskin er ein type endeleg tilstandseining, altså ein matematisk modell for utrekning som nyttar konseptet om ein abstrakt maskin med ei endeleg mengd tilstandar. Bimaskinar er samansette av to endelege tilstandsakseptorar, i tillegg til ein funksjon frå tilstandar i dei to maskinane til symbolar i ut-alfabetet. Fordelane med bimaskinar er at dei er deterministiske og at alle utvetydige endelege tilstandsoverførarar (òg kalla FST-ar, eller transduserar) kan konverterast til bimaskinar. Det går i tillegg an å bruka raskare akseptor-algoritmar i staden for overførar-algoritmar.

Bimaskinar blei først introdusert av Schützenberger (1961).

Definisjon

La inn-alfabetet vera $A_{I}$ og ut-alfabetet $A_{U}$.

$Q_{v}$ og $Q_{h}$ er to endelege mengder med tilstandar, kor starttilstandane er $q0_{v}\in Q_{v}$ og $q0_{h}\in Q_{h}$, og overføringsfunksjonane er $\delta _{v}:Q_{v}\times A_{I}\rightarrow Q_{v}$ og $\delta _{h}:Q_{h}\times A_{I}\rightarrow Q_{h}$. Overføringsfunksjonane kan generaliserast til lengre strengar på same måte som for automatar generelt: $\delta (q,\epsilon )=\epsilon ,\delta (q,wa)=\delta (\delta (q,w),a)$.

Då er $Q_{v},q0_{v},\delta _{v}$ ein deterministisk endeleg tilstandsmaskin (DFSA) frå venstre til høgre (utan aksepterande tilstandar), og $Q_{h},q0_{h},\delta _{h}$ er ein deterministisk endeleg tilstandsmaskin (DFSA) frå høgre til venstre (utan aksepterande tilstandar).

Så definerer me ein ut-funksjon $\gamma :Q_{v}\times A_{I}\times Q_{h}\rightarrow A_{U}$. Denne går altså frå tilstandane i dei to DFSA-ane, og inn-alfabetet, til ut-alfabetet. Gitt ein inn-streng $a_{1}a_{2}...a_{n}$, så vil ut-strengen for $a_{i}$ vera

$\gamma (\delta _{v}(q0_{v},a_{1}a_{2}...a_{i-1}),a_{i},\delta _{h}(q0_{h},a_{n},a_{n-1}...a_{i+1}))$

Ut-strengen for heile $a_{1}a_{2}...a_{n}$ er konkateneringa av ut-strengane for $a_{1},a_{2},...a_{n}$.

Bruksområde

Bimaskinar er nyttige verktøy i språkteknologi. Til dømes når ein skriv maskinlesbare ordbøker for morfologisk analyse, er det vanleg å spesifisera lingvistiske operasjonar (som lydendringar) i reglar som har ein «handlingsdel» (eller omskrivingsdel) og ein kontekstdel. Handlingsdelen og kontekstdelen er skilt med skråstrek, og «sentrum» av konteksten er markert med understrek «_». Kontekstdelen seier når regelen kan aktiverast, og handlingsdelen vil typisk omskriva symbolet som står i sentrum av konteksten.

Eit døme for norsk kan vera regelen $d\rightarrow \epsilon /d~\_{}~t~\#{}$ som seier «skriv om d til den tomme strengen viss det står ein d føre, og ein t følgt av ord-slutt etter». Så viss me tidlegare har lagt på inkjekjønnsendinga «-t» til ordet «nøydd», vil denne regelen skriva om «*nøyddt» til «nøydt». Konstekstar er regulære uttrykk og kan ofte vera meir kompliserte; t.d. viss me vil modellera r-bortfall i Grenlandsmålet kan me laga regelen $r\rightarrow \epsilon /\_{}~\#{}~[bfghjkmrv]$ som fjernar r i slutten av ord som byrjar på ikkje-koronale konsonantar.

Dei to delane i konteksten samsvarer med venstre og høgre DFSA til bimaskinen, som då kan lesa seg inn mot sentrum av konteksten frå kvar ende. Me kan konvertera ein slik regel til ein bimaskin ved å laga ein minimert DFSA som aksepterer venstrekonteksten, og ein annan minimert DFSA som aksepterer den reverserte høgrekonteksten. Viss inn-symbolet i sentrum av kontekst er $a$, og me analyserer venstre DFSA på venstrekonteksten og ender opp i tilstanden $q_{v}$, og høgre DFSA på høgrekonteksten og ender opp i tilstanden $q_{h}$, så vil $\gamma (q_{v},a,q_{h})$ gi ut-symbolet til handlingsdelen.

Sjå òg

• Automatteori