Konačni transduktor

Konačni transduktor (ili konačni pretvarač, konačni preobličavač, te još i konačni pretvarač) je konačna mašina sa dve trake: ulaznom i izlaznom.

Razlikuje se od običnog konačnog automata, koji ima samo jednu traku. Za automat se kaže da prepoznaje nisku ukoliko posmatramo sadržaj njegove trake kao ulaz. Drugim rečima, automat računa funkciju koja preslikava niske u skup {0,1}. Takođe, može se reći da automat generiše niske, što znači da posmatramo njegovu traku kao izlaznu traku. Na ovaj način, automat generiše formalni jezik, koji je skup niski. Ova dva viđenja su ekvivalentna: funkcija koju automat računa je upravo funkcija koja predstavlja indikator skupa niski koje automat prepoznaje. Klasa jezika generisanih konačnim automatima se naziva klasom regularnih jezika.

Dve trake kod transduktora se obično posmatraju kao ulazna i izlazna traka. Na ovaj način posmatrano, kaže se da on transdukuje (prevodi) sadržaj svoje ulazne trake u svoju izlaznu traku, prihvatanjem niske na ulazu i generisanjem nove niske na izlazu. Transduktor ovaj proces može da sprovodi nedeterministički, i tada može da proizvede više od jednog izlaza za svaku ulaznu nisku. Uopšteno posmatrano, transduktor računa relaciju između dva formalna jezika. Klasa relacija koje izračunavaju konačni transduktori se naziva klasom racionalnih relacija.

Konačni transduktori se obično koriste za istraživanje i primenu obrade prirodnih jezika u morfološkoj analizi.

Formalna konstrukcija

Formalno, konačni transduktor T je predstavljen uređenom šestorkom (Q, Σ, Γ, I, F, δ) gde je:

• Q konačan skup, skup stanja;
• Σ konačan skup, koji se naziva ulaznom azbukom;
• Γ konačan skup, koji se naziva izlaznom azbukom;
• I podskup od Q, skup početnih stanja;
• F podskup od Q, skup završnih stanja; i
• $\delta \subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q$ (gde je ε prazna niska) je relacija prelaza.

Možemo da posmatramo (Q, δ) kao usmereni graf, koji se naziva graf prelaza za T: skup čvorova je Q, a $(q,a,b,r)\in \delta$ znači da postoji označena grana koja vodi iz čvora q u čvor r. Takođe se kaže da je a ulazna etiketa a b je izlazna etiketa.

Moguće su i alternativne definicije konačnog transduktora, ali se sve mogu svesti na ovu. Definišemo proširenu relaciju prelaza $\delta ^{*}$ kao najmanji skup takav da:

• $\delta \subseteq \delta ^{*}$;
• $(q,\epsilon ,\epsilon ,q)\in \delta ^{*}$ za svaki $q\in Q$; i
• ako $(q,x,y,r)\in \delta ^{*}$ i $(r,a,b,s)\in \delta$ tada $(q,xa,yb,s)\in \delta ^{*}$.

Proširena relacija prelaza je u suštini refleksivno tranzitivno zatvorenje grafa prelaza koji je povećan na način da uzima u obzir i oznake ivica. Elementi relacije $\delta ^{*}$ su poznati kao putevi. Ivične oznake puta se dobijaju nadovezivanjem ivičnih oznaka svojih sastavnih prelaza u redosledu.

Ponašanje transduktora T je racionalna relacija [T] definisana na sledeći način: $x[T]y$ ako i samo ako postoji $i\in I$ i $f\in F$ tako da $(i,x,y,f)\in \delta ^{*}$. Ovime kažemo da T transdukuje string $x\in \Sigma ^{*}$ u nisku $y\in \Gamma ^{*}$ ako postoji put od početnog do konačnog stanja čija je ulazna oznaka x i izlazna oznaka y.

Operacije nad konačnim transduktorima

Sledeće operacije definisane nad konačnim automatima se takođe mogu primeniti i za konačne transduktore:

• Unija : Za date transduktore T i S, postoji transduktor $T\cup S$ takav da $x[T\cup S]y$ ako i samo ako $x[T]y$ ili $x[S]y$.

• Konkatenacija (nadovezivanje): Za date transduktore T i S, postoji transduktor $T\cdot S$ takav da $wx[T\cdot S]yz$ ako i samo ako $w[T]y$ i $x[S]z$.

• Klinijevo zatvorenje: Za dati transduktor T, postoji transduktor $T^{*}$ sa sledećim osobinama:

(1) $\epsilon [T^{*}]\epsilon$; (2) ako $w[T^{*}]y$ i $x[T]z$ tada $wx[T^{*}]yz$ ; i $x[T^{*}]y$ ne vredi osim ako to ne nalažu (1) ili (2).

Uočite da ne postoji notacija preseka transduktora. Umesto toga, postoji operacija kompozicije koja je karakteristična za transduktore i čija konstrukcija je slična onoj pri preseku automata. Kompozicija je definisana na sledeći način:

• Za dati transduktor T nad azbukama Σ i Γ i za transduktor S nad azbukama Γ i Δ, postoji transduktor $T\circ S$ nad Σ i Δ takav da je $x[T\circ S]z$ ako i samo ako postoji string $y\in \Gamma ^{*}$ takav da važi $x[T]y$ i $y[S]z$.

Takođe, može se napraviti projekcija neke od traka transduktora kako bi se dobio automat. Postoje dve funkcije projekcije: $\pi _{1}$ čuva ulaznu traku i $\pi _{2}$ čuva izlaznu traku. Prva projekcija, $\pi _{1}$, je definisana na sledeći način:

• Za dati transduktor T, postoji konačan automat $\pi _{1}T$ takav da $\pi _{1}T$ prihvata x ako i samo ako postoji string y za koji je $x[T]y$.

Druga projekcija, $\pi _{2}$, je definisana na sličan način.

Dodatna svojstva konačnih transduktora

• Odlučivo je da li je relacija [T] transduktora T prazna.

• Odlučivo je da li postoji string y takav da je x[T]y za dati string x.

• Neodlučivo je da li su dva transduktora ekvivalentna.