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
  • (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 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 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 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