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 bimaskinarSkut, W. (2004). Preference-Driven Bimachine Compilation An Application to TTS Text Normalisation. CLIN 2004.. Det går i tillegg an å bruka raskare akseptor-algoritmar i staden for overførar-algoritmarWojciech Skut, Stefan Ulrich, Kathrine Hammervold: A Generic Finite State Compiler for Tagging Rules. Machine Translation 18(3): 239-250 (2003).

Bimaskinar blei først introdusert av Schützenberger (1961)Schützenberger, M. P. (1961). A remark on finite transducers. Information and Control, 4(2), 185-196..

 Definisjon 
La inn-alfabetet vera  og ut-alfabetet . 

 og  er to endelege mengder med tilstandar, kor starttilstandane er  og , og overføringsfunksjonane er  og . Overføringsfunksjonane kan generaliserast til lengre strengar på same måte som for automatar generelt: .

Då er  ein deterministisk endeleg tilstandsmaskin (DFSA) frå venstre til høgre (utan aksepterande tilstandar), og  er ein deterministisk endeleg tilstandsmaskin (DFSA) frå høgre til venstre (utan aksepterande tilstandar).

Så definerer me ein ut-funksjon . Denne går altså frå tilstandane i dei to DFSA-ane, og inn-alfabetet, til ut-alfabetet. Gitt ein inn-streng , så vil ut-strengen for  vera 

Ut-strengen for heile  er konkateneringa av ut-strengane for .

 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  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  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øgrekontekstenRoche, E., & Schabes, Y. (Eds.). (1997). Finite-state language processing. MIT press. (s.419–). Viss inn-symbolet i sentrum av kontekst er , og me analyserer venstre DFSA på venstrekonteksten og ender opp i tilstanden , og høgre DFSA på høgrekonteksten og ender opp i tilstanden , så vil  gi ut-symbolet til handlingsdelen.

 Sjå òg 

 Automatteori

 Referansar 

Kategori:Automatteori
Kategori:Språkteknologi