Konačni pretvornik

Konačni pretvornik (konačni transduktor, konačni preobličavač, te još i konačni pretvarač) je konačni automat s dvije trake.

Kontrastirajte ovo s običnim konačnim automatom koji ima jednu traku. Za automat kažemo da prepoznaje niz znakova (string) ako sadržaj trake shvatimo kao ulaz. Drugim riječima, automat izračunava funkciju koja preslikava niz znakova u skup {0,1}. Alternativno, možemo reći da automat generira nizove znakova, što znači da traku shvaćamo kao izlaznu traku. S ovog gledišta, automat generira formalni jezik, koji je formalno definiran skupom nizova znakova nad abecedom. Oba gledišta na automat su istovjetna - funkcija koju automat izračunava je točno karakteristična funkcija jezika kojeg prepoznaje. Klasa jezika koje konačni automat generira jest klasa regularnih jezika.

Dvije trake transduktora se tipično gledaju kao ulazna traka i izlazna traka. Po ovom pogledu, za transduktor kažemo da transducira (ili preoblikuje) sadržaj svoje ulazne trake na izlaznu traku, prihvaćanjem niza znakova na svojoj ulaznoj traci i pisanjem drugog niza na svojoj izlaznoj traci. Tu pretvorbu može obaviti i nedeterministički te na taj način proizvesti više nego jedan izlaz za svaki ulazni niz. Transduktor također može i ne proizvesti izlaz za dani ulazni niz, u kojem pak slučaju kažemo da ne prihvaća (ili odbija) ulaz. Općenito, transduktor izračunava relaciju između dva formalna jezika. Klasa relacija koju izračunavaju konačni transduktori jest klasa racionalnih relacija.

Formalna definicija

Formalno, konačni transduktor T je šestorka (Q, Σ, Γ, I, F, δ) takva da:

• Q je konačan skup stanja;
• Σ je konačan skup ulaznih znakova (ili ulazna abeceda);
• Γ je konačan skup izlaznih znakova (ili izlazna abeceda);
• I je podskup skupa Q, skup početnih (ili inicijalnih) stanja;
• F je podskup skupa Q,skup konačnih (ili finalnih) stanja; i
• $\delta \subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q$ (gdje je ε prazni niz) je relacija prijelaza.

Par (Q, δ) možemo shvatiti kao usmjereni graf (digraf) poznat kao graf prijelaza automata T: skup vrhova je Q, a $(q,a,b,r)\in \delta$ znači da postoji označeni (labelirani) brid iz vrha q prema vrhu r. Još kažemo da je a ulazna oznaka (ili ulazna labela) a b je izlazna oznaka (ili izlazna labela) tog brida.

Definiramo proširenu relaciju prijelaza $\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 prijelaza jest u biti refleksivno okruženje grafa prijelaza koji je povećan na način da uzima u obzir i oznake bridova. Elementi relacije $\delta ^{*}$ su poznati kao putevi. Bridne oznake puta se dobiju nadovezivanjem bridnih oznaka svojih sastavnih prijelaza u redoslijedu.

Ponašanje transduktora T je racionalna relacija [T] definirana na sljedeći način: $x[T]y$ ako i samo ako postoji $i\in I$ i $f\in F$ takvi da $(i,x,y,f)\in \delta ^{*}$. Ovime kao da kažemo da T transducira niz znakova $x\in \Sigma ^{*}$ u niz znakova $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

Sljedeće operacije definirane nad konačnim automatima također vrijede i za konačne transduktore:

• Unija. Za dane 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$.
• Nadovezivanje (konkatenacija). Za dane 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$.
• Kleeneov operator. Za dani transduktor T, postoji transduktor $T^{*}$ sa sljedećim svojstvima: (1) $\epsilon [T^{*}]\epsilon$; (2) ako $w[T^{*}]y$ i $x[T]z$ tada $wx[T^{*}]yz$; i $x[T^{*}]y$ ne vrijedi osim ako to ne nalažu (1) ili (2).

Uočite da ne postoji operacija presjeka transduktora. Umjesto toga, postoji operacija kompozicije koja je specifična za transduktore i čija je konstrukcija slična onoj pri presjeku drugih automata. Kompozicija je definirana na sljedeći način:

• Za dani transduktor T nad abecedama Σ i Γ i transduktor S nad abecedama Γ i Δ, postoji transduktor $T\circ S$ nad Σ i Δ takav da $x[T\circ S]z$ ako i samo ako postoji niz znakova $y\in \Gamma ^{*}$ takav da $x[T]y$ i $y[S]z$.

Također se može napraviti projekcija neke od traka transduktora kako bi se dobio automat. Postoje dvije funkcije projekcije:

$\pi _{1}$ čuva ulaznu traku, i $\pi _{2}$ čuva izlaznu traku. Prva projekcija, $\pi _{1}$ je definirana na sljedeći način:

• Za dani transduktor T, postoji konačni automat $\pi _{1}T$ takav da $\pi _{1}T$ prihvaća x ako i samo ako postoji niz znakova y za koji $x[T]y$.

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

Dodatna svojstva konačnih transduktora

• Odlučivo je je li relacija [T] transduktora T prazna.
• Odlučivo je postoji li niz znakova y takav da x[T]y za dani niz znakova x.
• Neodlučivo je jesu li dva transduktora istovjetna.

Vidjeti također

• Mealyev automat
• Mooreov automat

Izvori

• Jurafsky, Daniel; Martin, James H. 2000. Speech and Language Processing. Prentice Hall. str. 71–83. ISBN 0-13-095069-6

• Galvez, Carmen. 2006. An Evaluation of Conflation Accuracy Using Finite-State Transducers. Journal of Documentation. str. Vol. 62 (3), 328–349. ISSN 0022-0418
• Galvez, Carmen. 2007. Approximate Personal Name-Matching Through Finite-State Graphs. Journal of The American Society for Information Science and Technology. str. Vol.58 (13), 1960–1976. ISSN 1532-2882
• Galvez, Carmen. 2007. Standardizing Formats of Corporate Source Data. Scientometrics. str. Vol. 70 (1), 3–26. ISSN 0138-9130