Konačni transduktor

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon.

Konačni transduktor ili konačni pretvarač je konačni automat sa dvije trake.

Uporedite ovo sa 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 računa funkciju koja preslikava niz znakova u skup {0,1}. Alternativno, možemo reći da automat generiše nizove znakova, što znači da traku shvatamo kao izlaznu traku. Sa ovog gledišta, automat generiše formalni jezik, koji je formalno definisan skupom nizova znakova nad abecedom. Oba gledišta na automat su istovjetna - funkcija koju automat računa je tač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, za transduktor kažemo da transducira (ili preoblikuje) sadržaj svoje ulazne trake na izlaznu traku, prihvatanjem niza znakova na svojoj ulaznoj traci i pisanjem drugog niza na svojoj izlaznoj traci. Taj preobražaj 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 da ne proizvede izlaz za dati ulazni niz, pa u tom slučaju kažemo da ne prihvata (ili odbija) ulaz. Općenito, transduktor računa relaciju između dva formalna jezika. Klasa relacija koju računaju konačni transduktori jest klasa racionalnih relacija.

Formalna definicija[uredi | uredi izvor]

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.

Definišemo 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] definisana 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[uredi | uredi izvor]

Sljedeće operacije definisane nad konačnim automatima također vrijede 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.
  • Nadovezivanje (konkatenacija). 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.
  • Kleeneov operator. Za dati 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 definisana na sljedeći način:

  • Za dati 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 definisana na sljedeći način:

  • Za dati 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 definisana na sličan način.

Dodatna svojstva konačnih transduktora[uredi | uredi izvor]

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

Također pogledajte[uredi | uredi izvor]

Dodatna literatura[uredi | uredi izvor]

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

Vanjski linkovi[uredi | uredi izvor]