Konačni pretvornik

Izvor: Wikipedija
Skoči na: orijentacija, traži

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 VE | uredi]

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[uredi VE | uredi]

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[uredi VE | uredi]

  • 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 VE | uredi]

Izvori[uredi VE | uredi]

  1. Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 921