Transductor d'estats finitos determinista p-subsecuencial alvançat

Els transductores d'estats finitos són Autómates d'estats finitos determinista en transicions sobre parelles de símbols.

Un transductor d'estats finitos determinista p-subsecuencial alvançat (TpSSDA o EDpSST de les seues sigles en anglés Earliest Deterministic Finite-State p-Subsequential Transducers) és l'implementació habitual de les transducciones p-subsecuenciales alvançades per a un diccionari morfològic no alineat. Estos transductores no tenen estats d'acceptació explícitament definits.

Definició

Un transductor és alvançat si l'eixida està assignada als arcs de manera que es produïxca tan pronte com siga possible.

Un transductor d'estats finitos determinista p-subsecuencial alvançat és l'implementació habitual de les transducciones p-subsecuenciales alvançades per a un diccionari morfològic no alineat.

Cada u dels seus estats representa el conjunt de prefixos que compartixen un prefix (el més llarc possible) d'eixida comuna.

S'aplega a un únic estat per a cada símbol d'entrada i estat, lo que fa que l'autómata siga determinista.

L'eixida està associada a les transicions estat-a-estat: es va construint incrementalmente el prefix comú més llarc.

Formalment es definix com:

Donada una transducción $\tau :E\to 2^{{\Gamma }^{*}}$, en $E$ un conjunt finito, el corresponent transductor d'estats finitos determinista $p$-subsecuencial alvançat (ED$p$SST, earliest deterministic finite-state $p$-subsequential transducer) és $T=(Q,\Sigma ,\Gamma ,\delta ,\lambda ,q_I,\psi )$, a on :

• $Q$ és el conjunt $Pr(E)\cup \{\perp \}$ de tots els prefixos d'entrada més l'estat d'absorció
• $\Sigma$ és l'alfabet d'entrada
• $\Gamma$ és l'alfabet d'eixida
• $\delta :Q\times \Sigma \to Q$ és la funció de transició

$\delta (x,\sigma )=\{\begin{array}{cc}x\sigma & \text{ Si }x,x\sigma \in \mathrm{P}\mathrm{r}(E)\\ \perp & \text{otro caso }\end{array}$

• $\lambda :Q\times \Sigma \to {\Gamma }^{*}$ és la funció d'eixida

$\lambda (x,\sigma )=[\mathrm{L}\mathrm{C}\mathrm{P}(\tau (x{x}^{-1}E)){]}^{-1}[\mathrm{L}\mathrm{C}\mathrm{P}(\tau ((x\sigma )(x\sigma {)}^{-1}E))]$ per a $x,x\sigma \in \mathrm{P}\mathrm{r}(E)$, i indefinit en un atre cas.

Si $\mathrm{L}\mathrm{C}\mathrm{P}[\tau (E)]\ne \epsilon$, totes les eixides $\lambda (ϵ,\sigma )$ tenen $\mathrm{L}\mathrm{C}\mathrm{P}[\tau (E)]$ com a prefix.

• $q_I=\{\epsilon \}$ és l'estat inicial
• $\psi :Q\to 2^{{\Gamma }^{*}}$ és una funció que assigna a cada estat un conjunt de coes a agregar a l'eixida al final de l'entrada

$\psi (w)=\{\begin{array}{cc}[\mathrm{L}\mathrm{C}\mathrm{P}(\tau (x{x}^{-1}E)){]}^{-1}\tau (w)& \text{ si }w\in E\\ \mathrm{\varnothing }& \text{ otro caso }\end{array}$

Esta construcció és bàsicament un trie per a les cadenes de $E$ dotada de funcions d'eixida $\lambda$ i $\psi$ que produïxen la cadena d'eixida tan pronte com és possible (l'informació d'eixida pot ser afegida fàcilment a lo llarc del recorregut en post-orde del trie). El transductor resultant (acíclic) es pot minimisar fàcilment en un transductor equivalent que produïx la mateixa eixida per a tots els prefixos en $Pr(E)$ i afegint les mateixes coes a totes les cadenes de caràcters en I mentres utilisa el número mínim d'estats.

Eixemple

Taula del diccionari morfològic utilisat per a construir el Transductor d'estats finitos determinista p-subsecuencial alvançat

Transductor d'estats finitos determinista p-subsecuencial alvançat corresponent al diccionari morfològic de la taula

L'image de la taula representa el diccionari morfològic alineat utilisat per a representar el transductor d'estats finitos determinista p-subsecuencial alvançat que es representa en la segona image.

En la representació del transductor, les arístas tenen representades els parells d'entrada i eixida separats pel signe ':', és dir, el parell s : t, a on s ∈ $\Sigma$ és la cadena d'entrada i t ∈ $\Gamma$ és la cadena d'eixida.

Podem observar que és alvançat, ya que una volta que s'ha vist la cadena "reco" el transductor assigna a l'eixida la cadena "recordar".

Vore també

• Transductor d'estats finitos
• Transductor seqüencial
• Transductor subsecuencial
• Transductor p-subsecuencial
• Transductor p-subsecuencial alvançat
• Transductor d'estats finitos determinista p-subsecuencial