Konačni pretvornik
Konačni pretvornik (konačni transduktor, konačni preobličavač, te još i konačni pretvarač[1]) 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[uredi | uredi kôd]
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
- (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 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 kao najmanji skup takav da:
- ;
- za svaki ; i
- ako i tada .
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 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: ako i samo ako postoji i takvi da . Ovime kao da kažemo da T transducira niz znakova u niz znakova ako postoji put od početnog do konačnog stanja čija je ulazna oznaka x i izlazna oznaka y.
Operacije nad konačnim transduktorima[uredi | uredi kôd]
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 takav da ako i samo ako ili .
- Nadovezivanje (konkatenacija). Za dane transduktore T i S, postoji transduktor takav da ako i samo ako i .
- Kleeneov operator. Za dani transduktor T, postoji transduktor sa sljedećim svojstvima: (1) ; (2) ako i tada ; i 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 nad Σ i Δ takav da ako i samo ako postoji niz znakova takav da i .
Također se može napraviti projekcija neke od traka transduktora kako bi se dobio automat. Postoje dvije funkcije projekcije:
čuva ulaznu traku, i čuva izlaznu traku. Prva projekcija, je definirana na sljedeći način:
- Za dani transduktor T, postoji konačni automat takav da prihvaća x ako i samo ako postoji niz znakova y za koji .
Druga projekcija, je definirana na sličan način.
Dodatna svojstva konačnih transduktora[uredi | uredi kôd]
- 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[uredi | uredi kôd]
Izvori[uredi | uredi kôd]
- ↑ Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 921
- 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