# 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:π$_1$ preserva a fita de entrada e π$_2$ preserva a fita de saída. A primeira projeção π$_1$ é definida da seguinte maneira: dado um transdutor T, então existe um autômato finito π$_1$$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