[HOME PAGE] [STORES] [CLASSICISTRANIERI.COM] [FOTO] [YOUTUBE CHANNEL]

Transductor d'estats finits - Viquipèdia

Transductor d'estats finits

De Viquipèdia

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òmata 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.


Taula de continguts

[edita] 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ó extesa δ * 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^* \and (r,a,b,s) \in \delta aleshores (q,xa,yb,s) \in \delta^*.

La funció de transició extesa és essencialment la clausura de transició extesa del graf de transició que s'ha augmentat per tindre en consideració les etiquetes de les arestes. Els elements de δ * es coneixen com a camins. Les etiquetes d'un camí s'obtenen concatenant les etiquetes que componen el camí en l'ordre en que 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 \and{} 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.

[edita] Operacions en transductors d'estats finits

Les següents operacions definides en autòmates 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ó: π1 manté la cinta d'entrada, i π2 manté la d'eixida. La primera projecció (π1) es defineix de la següent manera:

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

La segona projecció (π2) es pot definir de forma semblant.

[edita] Propietats adicionals 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òmata 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.

[edita] Vegeu també

  • Autòmat finit determinista
  • Transductor de letres

[edita] Bibliografia

Carmen Galvez; Félix Moya-Anegon (2006). An Evaluation of Conflation Accuracy Using Finite-State Transducers, Journal of Documentation, vol. 62 (3), 328-349. ISSN 0022-0418. 

Carmen Galvez (2007). Approximate Personal Name-Matching Through Finite-State Graphs, Journal of The American Society for Information Science and Technology, vol.58 (13), 1960-1976. ISSN 1532-2882. 

Carmen Galvez (2007). Standardizing Formats of Corporate Source Data, Scientometrics , vol. 70 (1), 3-26. ISSN 0138-9130. 

Daniel Jurafsky; James H. Martin (2000). Speech and Language Processing, Prentice Hall, 71-83. ISBN 0-13-095069-6. 

Emmanuel Roche; Yves Schabes (1997). Finite-state language processing, MIT Press, 1-65. ISBN 0-262-18182-7.