Transdutor de estados finitos

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita uma ou mais fontes fiáveis e independentes, mas ela(s) não cobre(m) todo o texto (desde março de 2014).
Por favor, melhore este artigo providenciando mais fontes fiáveis e independentes e inserindo-as em notas de rodapé ou no corpo do texto, conforme o livro de estilo.
Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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 π1T 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[editar | editar código-fonte]

  • É 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 [[1]] sobre o alfabeto L e pode, portanto, ser minimizado de forma que ele tenha um número mínimo de estados.

Applications[editar | editar código-fonte]

  • 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]

Referências

  1. Regular Models of Phonological Rule Systems. Página visitada em August 25, 2012.

Ligações externas[editar | editar código-fonte]

Mais leitura[editar | editar código-fonte]

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