Transdutor de estados finitos

Transdutor de estados finitos é um máquina de estados finitos com duas fitas: uma fita de entrada e uma fita de saída. Isto contrasta com um autômato finito comum (ou aceitador de estado finito), que tem apenas uma única fita.

Visão global

Um autômato pode ser dito como reconhecedor de uma cadeia se visualizar o conteúdo de sua fita como entrada. Em outras palavras, o autômato computa uma função que mapeia cadeias no conjunto {0,1}. Alternativamente, podemos dizer que um autômato gera cadeias, o que significa ver sua fita como uma fita de saída. Deste ponto de vista, o autômato gera um linguagem formal, que nada mais é que um conjunto de cadeias. Os dois pontos de vista dos autômatos são equivalentes: a função que o autômato computa é precisamente a função característica do conjunto de cadeias que ele gera. A classe de linguagens geradas por autômatos finitos é conhecido como a classe das linguagens regulares.

As duas fitas de um transdutor são normalmente vistas como uma fita de entrada e uma fita de saída. Deste ponto de vista, um transdutor traduz o conteúdo de sua fita de entrada para a sua fita de saída, ao aceitar uma cadeia em sua fita de entrada e gerar uma outra cadeia em sua fita de saída. Isso pode ser feito não-deterministicamente e é possível produzir mais de uma saída para cada cadeia de entrada. Um transdutor também pode não produzir uma saída para uma dada cadeia de entrada, neste caso, diz-se que ele rejeitou a entrada. Em geral, um transdutor computa uma relação entre duas linguagens formais.

Cada transdutor de estados finitos cadeia-por-cadeia define uma relação R em Σ × Γ. Relações R que podem ser implementadas como tradutores de estados finitos são chamadas de relações racionais. Relações racionais que são funções parciais, ou seja, que relacionam cada cadeia de entrada de Σ* a no máximo uma em Γ* são chamadas de funções racionais.

Tradutores de estados finitos são frequentemente utilizados para fonologia e em análise morfológica nas pesquisas e aplicações de processamento de linguagem natural. Pioneiros neste campo incluem Ronald Kaplan, Lauri Karttunen, Martin Kay e Kimmo Koskenniemi. Uma maneira comum de utilizar transdutores é em uma assim chamada "cascata", onde os transdutores para várias operações são combinados em um único transdutor por aplicação repetida do operador composição (definido abaixo).

Construção Formal

Formalmente, um transdutor finito T é uma 6-tupla (Q, Σ, Γ, I, F, δ) tal que:

• Q é um conjunto finito, um conjunto de estados;
• Σ é um conjunto finito , chamado de alfabeto de entrada;
• Γ é um conjunto finito , chamado de alfabeto de saída;
• I é um subconjunto de Q, o conjunto dos estados iniciais;
• F é um subconjunto de Q, o conjunto dos estados finais; e
• $\delta \subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q$ (onde ε é uma cadeia vazia) é uma relação de transição.

Nós podemos ver ( Q, δ) como um gráfico dirigido, conhecido como o grafo de transição de T: o conjunto de vértices é Q, e $(q,a,b,r)\in \delta$ significa que existe uma ligação marcada indo do vértice q para vértice r. Dizemos também que a é o rótulo de entrada e b o rótulo de saída de uma ligação.

NOTA: Esta definição de transdutor finito é também chamada de trandutor de carta (Roche e Schabes 1997); definições alternativas são possíveis, mas podem ser convertidas em transdutores a partir deste.

Definir a relação de transição estendida $\delta ^{*}$ como o menor conjunto tal que:

• $\delta \subseteq \delta ^{*}$;
• $(q,\epsilon ,\epsilon ,q)\in \delta ^{*}$ para todo $q\in Q$; e
• sempre que $(q,x,y,r)\in \delta ^{*}$ e $(r,a,b,s)\in \delta$ então $(q,xa,yb,s)\in \delta ^{*}$.

A relação de transição estendida é essencialmente o fecho reflexivo e transitivo do grafo de transição que foi modificado para incluir os rótulos nas arestas. Os elementos de $\delta ^{*}$ são conhecidos como caminhos. Os rótulos das arestas de um caminho são obtidos pela concatenação dos rótulos das arestas de suas transições constituintes em ordem.

O comportamento do transdutor T é a relação racional [T] definida como a seguir: $x[T]y$ se e somente se lá existe $i\in I$ e $f\in F$ tal que $(i,x,y,f)\in \delta ^{*}$. Isso significa que T traduz uma cadeia $x\in \Sigma ^{*}$ em uma cadeia $y\in \Gamma ^{*}$ se existe um caminho de um estado inicial para um estado final, cujo rótulo de entrada é x e cujo rótulo de saída é y.

Operações em transdutores de estados finitos

As seguintes operações definidas em autômatos finitos também se aplicam aos transdutores finitos:

• União : Sejam os transdutores T e S, existe um transdutor $T\cup S$ tal que $x[T\cup S]y$ se e somente se $x[T]y$> ou $x[S]y$.

• Concatenação: Sejam os transdutores T e S, existe um transdutor $T\cdot S$ tal que $wx[T\cdot S]yz$ se e somente se $w[T]y$ e $x[S]z$.

• Fecho de Kleene : Dado um transdutor T, existe um transdutor $T^{*}$ com as seguintes propriedades: $\epsilon [T^{*}]\epsilon$; (2) se $w[T^{*}]y$ e $x[T]z$ então $wx[T^{*}]yz$; e $x[T^{*}]y$ não se verifica a menos que exigido por (1) ou (2).

• Interseção: Sejam os transdutores T e S, a interseção desses transdutores H tem a propriedade de que (1) x[H]y se e somente se x[T]y e x[S]y.
• Composição: Dado um transdutor T sobre o alfabeto Σ e Γ, um transdutor S sobre o alfabeto Γ e Δ, então existe um transdutor $T\circ S$ sobre Σ e Δ tal que $x[T\circ S]z$ se e somente se existe uma cadeia $y\in \Gamma ^{*}$ tal que $x[T]y$ e $y[S]z$.

Esta definição usa a mesma notação que é usada em matemática para composição de relações. Entretanto, a leitura convencional para composição de relação é o contrário: dada duas relações $T$ e $S$, $(x,z)\in T\circ S$ quando existe algum $y$ tal que $(x,y)\in S$ e $(y,z)\in T$.

• Projeção para um autômato. Existem duas funções de projeção:π₁ preserva a fita de entrada e π₂ preserva a fita de saída. A primeira projeção π₁ é definida da seguinte maneira: dado um transdutor T, então existe um autômato finito π₁$T$ tal que este aceita x se e somente se existe uma cadeia y para cada $x[T]y$.
• Determinação. Dado um transdutor T, queremos construir um transdutor equivalente que tem um estado inicial único e de tal forma que não há duas transições que deixam qualquer estado compartilhando um mesmo rótulo de entrada. A construção do conjunto pode ser estendido para transdutores, mas às vezes, este, não consegue parar, na verdade, alguns transdutores não-determinísticos não admitem transdutores determinísticos equivalentes. Caracterizações de transdutores determinísticos foram propostas, juntamente com eficientes algoritmos para testá-las.

Propriedades adicionais de transdutores de estados finitos

• É decidível se a relação [T] de um transdutor T está vazio.

• É decidível se existe uma cadeia y tal que x[T]y para uma determinada cadeia.

• É problema indecidível se dois transdutores são equivalentes.

• Se definirmos o alfabeto de rótulos $L=(\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})$, os transdutores de estado finito são isomorfos ao AFND sobre o alfabeto $L$ e pode, portanto, ser minimizado de forma que ele tenha um número mínimo de estados.

Applications

• Regras de reescrita sensíveis ao contexto da forma a → b / c _ d, usada em Linguística para modelar regra fonológica e mudança de som, são equivalentes computacionalmente para tradutores de estado finitos, desde que a aplicação seja não recursiva, ou seja, a regra não é permitida para reescrever a mesma subcadeia duas vezes

Referências

• Allauzen, Cyril; Mohri, Mehryar (2003). «Efficient Algorithms for Testing the Twins Property» (PDF). Journal of Automata, Languages and Combinatorics. 8 (2): 117–144 
• Koskenniemi, Kimmo (1983), Two-level morphology: A general computational model of word-form recognition and production (PDF), Department of General Linguistics, University of Helsinki 
• Mohri, Mehryar (2004). «Weighted Finite-State Transducer Algorithms: An Overview» (PDF). Formal Languages and Applications. 148 (620): 551–564 

Ligações externas

• OpenFst, an open-source library for FST operations.
• Stuttgart Finite State Transducer Tools, another open-source FST toolkit
• java FST Framework, an open-source java FST Framework capable of handling OpenFst text format.

Mais leitura

• Jurafsky, Daniel; James H. Martin (2000). Speech and Language Processing. [S.l.]: Prentice Hall. pp. 71–83. ISBN 0-13-095069-6 
• Kornai, Andras (1999). Extended Finite State Models of Language. [S.l.]: Cambridge University Press. ISBN 0-521-63198-X 
• Roche, Emmanuel; Yves Schabes (1997). Finite-state language processing. [S.l.]: MIT Press. pp. 1–65. ISBN 0-262-18182-7 
• Beesley, Kenneth R.; Lauri Karttunen (2003). Finite State Morphology. [S.l.]: Center for the Study of Language and Information. ISBN 1-57586-434-7 
• Roark, Brian; Richard Sproat (2007). Computational Approaches to Morphology and Syntax. [S.l.]: Oxford University Press. ISBN 0-19-927478-9 
• Berstel, Jean (1979). Transductions and Context-free Languages. [S.l.]: Teubner Verlag . Free PDF version