Transductor d'estats finits

Un transductor d'estats finits, o transductor finit, és un autòmat finit (o màquina d'estats finits) amb dues cintes, una d'entrada i una d'eixida.

Açò contrasta amb un autòmat finit habitual, que només té una cinta. Podem dir que l'autòmat reconeix una cadena si aquesta es troba en la seva cinta d'entrada. En altres paraules, l'autòmat computa una funció que converteix una cadena en un element del conjunt {0,1}. D'altra banda, podem dir que un autòmat genera cadenes, a partir de la seva cinta d'eixida. Des d'aquest punt de vista, l'autòmat genera un llenguatge formal, que no és més que un conjunt de cadenes. Els dos punts de vista de l'autòmat són equivalents: la funció que computa l'autòmat és la funció indicadora del conjunt de cadenes reconegudes. La classe de llenguatges generats per un autòmat finit es coneix amb el nom de llenguatges regulars.

Les dues cintes d'un transductor són vistes típicament com una cinta d'entrada i una altra d'eixida. Des d'aquest punt de vista, un transductor transdueix (açò és, tradueix) el contingut de la seva cinta d'entrada a la seva cinta d'eixida, acceptat cadenes en la seva cinta d'entrada i generant altres cadenes en la seva cinta d'eixida. Pot fer-ho de forma no-determinística, cosa que produirà més d'una eixida per a cada cadena d'entrada. Un transductor també pot no produir cap eixda per a una cadena d'entrada donada; en aquest cas es diu que rebutja l'entrada. En general, un transductor computa una relació entre dos llenguatges formals. La classe de relacions computades per un transductor d'estats finits es coneix com a classe de relacions racionals.

Els transductors d'estats finits són utilitzats habitualment en anàlisi morfològiques, en l'àrea d'investigació de processament del llenguatge natural i en les seves aplicacions.

Construcció formal

Formalment, un transductor finit T és una tupla (Q, Σ, Γ, I, F, δ) on:

• Q és un conjunt finit dels estats;
• Σ és un conjunt finit de símbols, anomenat alfabet d'entrada;
• Γ és un conjunt finit de símbols, anomenat alfabet d'eixida;
• I és un subconjunt de Q, que representa els estats inicials;
• F és un subconjunt de Q, que representa els estats finals; i
• $\delta \subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q$ és la funció de transició, on ε és la cadena buida.

Podem veure (Q, δ) com un graf dirigit etiquetat, conegut com el graf de transició de T: el conjunt de vèrtex és Q, i $(q,a,b,r)\in \delta$ significa que hi ha una aresta etiquetada que va des del vèrtex q cap al vèrtex r. També diem que a és l'etiqueta d'entrada i b és l'etiqueta d'eixida de l'aresta.

Es defineix la funció de transició estesa $\delta ^{*}$ com el conjunt mínim que compleix les següents restriccions:

• $\delta \subseteq \delta ^{*}$;
• $(q,\epsilon ,\epsilon ,q)\in \delta ^{*}$ $\forall q\in Q$; i
• $\forall (q,x,y,r)\in \delta ^{*}$ $\land$$(r,a,b,s)\in \delta$ aleshores $(q,xa,yb,s)\in \delta ^{*}$.

La funció de transició estesa és essencialment la clausura de transició estesa del graf de transició que s'ha augmentat per tindre en consideració les etiquetes de les arestes. Els elements de $\delta ^{*}$ es coneixen com a camins. Les etiquetes d'un camí s'obtenen concatenant les etiquetes que componen el camí en l'ordre en què es produeixen les transicions.

El comportament del transductor T és la relació racional [T] definida de la següent manera: $x[T]y$ si i només si $\exists {}i\in I\land {}f\in F$ de forma que $(i,x,y,f)\in \delta ^{*}$. Açò és com dir que T transdueix (o tradueix) una cadena $x\in \Sigma ^{*}$ en una altra cadena $y\in \Gamma ^{*}$ si existeix un camí des d'un estat inicial fins a un estat final amb entrada x i eixida y.

Operacions en transductors d'estats finits

Les següents operacions definides en autòmats finits també es poden aplicar als transductors:

• Unió. Donats els transudctors T i S, existeix un transducttor $T\cup S$ tal que $x[T\cup S]y$ si i només si $x[T]y$ o $x[S]y$.

• Concatenació. Donats els transductors T i S, existeix un transductor $T\cdot S$ tal que $wx[T\cdot S]yz$ si i només si $w[T]y$ i $x[S]z$.

• Clausura de Kleene.

No existeix el concepte d'intersecció de transductors. Per contra, existeix una operació de composició que és específica per als transductors, la construcció de la qual és semblant a la intersecció dels autòmats. La composició es defineix de la següent forma:

• Donat un transductor T sobre els alfabets Σ i Γ i un transductor S sobre els alfabets Γ i Δ, existeix un transductor $T\circ S$ sobre Σ i Δ tal que $x[T\circ S]z$ si i només si existeix un cadena $y\in \Gamma ^{*}$ tal que $x[T]y$ i $y[S]z$.

També es pot projectar una cinta del transductor per obtenir un autòmat. Hi ha dues funcions de projecció: $\pi _{1}$ manté la cinta d'entrada, i $\pi _{2}$ manté la d'eixida. La primera projecció ($\pi _{1}$) es defineix de la següent manera:

• Donat un transductor T, existeix un autòmat finit $\pi _{1}T$ tal que $\pi _{1}T$ accepta x si i només si existeix una cadena y de forma que $x[T]y$.

La segona projecció ($\pi _{2}$) es pot definir de forma semblant.

Propietats addicionals dels transductors d'estats finits

• Saber si la relació [T] d'un transductor T està buida és decidible.

• Saber si existeix una cadena y tal que x[T]y per a una cadena x donada és decidible.

• Saber si dos transductors són equivalents no és decidible.

• Si es defineix un alfabet d'etiquetes $L=(\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})$, el traductor d'estats finits és isomòrfic a un autòmat finit indeterminista (AFI) sobre l'alfabet $L$, i pot convertirse en un autòmat finit determinista sobre l'alfabet $L=[(\Sigma \cup \{\epsilon \})\times \Gamma ]\cup [\Sigma \times (\Gamma \cup \{\epsilon \})]$) i ésser minimitzat de tal forma que tinguen el mínim nombre d'estats.

Vegeu també

• Autòmat finit determinista
• Transductor de letres