Transdutor de estados finitos

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Esta página ou secção cita fontes confiáveis e independentes, mas que não cobrem todo o conteúdo (desde março de 2014). Por favor, adicione mais referências e insira-as corretamente no texto ou no rodapé. Material sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

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
  • (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 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:

  • ;
  • para todo ; e
  • sempre que e então .


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[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 tal que se e somente se > ou .
  • Concatenação: Sejam os transdutores T e S, existe um transdutor tal que se e somente se e .
  • Fecho de Kleene : Dado um transdutor T, existe um transdutor com as seguintes propriedades: ; (2) se e então ; e 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 sobre Σ e Δ tal que se e somente se existe uma cadeia tal que e .

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 .

  • 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 tal que este aceita x se e somente se existe uma cadeia y para cada .
  • 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 , os transdutores de estado finito são isomorfos ao [[1]] sobre o alfabeto 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» (PDF). Consultado em August 25, 2012. 

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

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

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