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:

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 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 como o menor conjunto tal que:


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 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: se e somente se lá existe e tal que . Isso significa que T traduz uma cadeia em uma cadeia 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:

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 e , quando existe algum tal que e .

Propriedades adicionais de transdutores de estados finitos

Applications

Mais leitura