Transdutor de estados finitos

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).

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
• ${\displaystyle \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 ${\displaystyle (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 ${\displaystyle \delta ^{*}}$  como o menor conjunto tal que:

• ${\displaystyle \delta \subseteq \delta ^{*}}$ ;
• ${\displaystyle (q,\epsilon ,\epsilon ,q)\in \delta ^{*}}$  para todo ${\displaystyle q\in Q}$ ; e
• sempre que ${\displaystyle (q,x,y,r)\in \delta ^{*}}$  e ${\displaystyle (r,a,b,s)\in \delta }$  então ${\displaystyle (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 ${\displaystyle \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: ${\displaystyle x[T]y}$  se e somente se lá existe ${\displaystyle i\in I}$  e ${\displaystyle f\in F}$  tal que ${\displaystyle (i,x,y,f)\in \delta ^{*}}$ . Isso significa que T traduz uma cadeia ${\displaystyle x\in \Sigma ^{*}}$  em uma cadeia ${\displaystyle 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.

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 ${\displaystyle T\cup S}$  tal que ${\displaystyle x[T\cup S]y}$  se e somente se ${\displaystyle x[T]y}$ > ou ${\displaystyle x[S]y}$ .

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

• Fecho de Kleene : Dado um transdutor T, existe um transdutor ${\displaystyle T^{*}}$  com as seguintes propriedades: ${\displaystyle \epsilon [T^{*}]\epsilon }$ ; (2) se ${\displaystyle w[T^{*}]y}$  e ${\displaystyle x[T]z}$  então ${\displaystyle wx[T^{*}]yz}$ ; e ${\displaystyle 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 ${\displaystyle T\circ S}$  sobre Σ e Δ tal que ${\displaystyle x[T\circ S]z}$  se e somente se existe uma cadeia ${\displaystyle y\in \Gamma ^{*}}$  tal que ${\displaystyle x[T]y}$  e ${\displaystyle 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 ${\displaystyle T}$  e ${\displaystyle S}$ , ${\displaystyle (x,z)\in T\circ S}$  quando existe algum ${\displaystyle y}$  tal que ${\displaystyle (x,y)\in S}$  e ${\displaystyle (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 π₁${\displaystyle T}$  tal que este aceita x se e somente se existe uma cadeia y para cada ${\displaystyle 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.

• É 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 ${\displaystyle L=(\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})}$ , os transdutores de estado finito são isomorfos ao AFND sobre o alfabeto ${\displaystyle L}$  e pode, portanto, ser minimizado de forma que ele tenha um número mínimo de estados.

• 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^[1]