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

## Referansar