O Algoritmo de Thompson, criado por Ken Thompson e Dennis Ritchie, serve para construir Autômatos finitos não determinísticos a partir de uma Expressão Regular.
Em ciência da computação, Algoritmo de Thompson é um algoritmo para transformar uma expressão regular em um equivalente autômato finito não determinístico (AFN). Este AFN pode ser usado para casar palavras com expressões regulares.
Expressão regular e autômato finito não-determinístico são duas representações abstratas de linguagens formais. Enquanto expressões regulares são utilizadas, por exemplo, para descrever padrões avançados de pesquisa em " localizar e substituir " -como operações de utilidades de processamento de texto, o formato do AFN é mais adequado para a execução em um computador. Assim, este algoritmo é de interesse prático , uma vez que pode ser considerado como um compilador de expressão regular para AFN. Em um ponto de vista mais teórico, esse algoritmo é uma parte da prova que ambos aceitam exatamente as mesmas linguagens, isto é, as linguagens regulares.
Um automato obtido assim pode ser feito deterministicamente pela Construção do conjunto das partes e, em seguida, ser minimizado para obter um automato ótimo correspondente à expressão regular , mas também pode ser utilizado diretamente.
O algoritmo
O algoritmo funciona de forma recursiva dividindo uma expressão em subexpressões constituintes, das quais o AFN será construído usando um conjunto de regras. Mais precisamente, a partir de uma expressão regular , o autômato obtido com o da função de transição respeita as seguintes propriedades: tem exatamente um estado inicial , que não é acessível a partir de nenhum outro estado. Ou seja, para qualquer estado e qualquer letra , não contém . tem exatamente um estado final , que não é co-acessível a partir de nenhum outro estado. Isto é, para qualquer letra , . Seja o número de concatenação da expressão regular e seja o número de símbolos à parte de parênteses — Isto é, , , e . Em seguida, o número de estados de é (linear no tamanho de ). O número de transições que deixam qualquer estado é de no máximo dois. Uma vez que um AFN de estados e no máximo transições de cada estado pode corresponder a uma cadeia de comprimento em tempo , um AFN de Thompson pode fazer a correspondência de padrões em tempo linear,assumindo um alfabeto de tamanho fixo.
Regras
As regras a seguir são descritas de acordo com Aho et al. (1986),Alfred V. Aho, Ravi Sethi, Jeffrey Ullman: Compilers: Principles, Techniques and Tools. Addison Wesley, 1986 p. 122. N() eN() é o AFN da subexpressão e , respectivamente.
A expressão-vazia ε é convertida em
inline
Um símbolo a de um alfabeto de entrada é convertido em
inline
A expressão de união | é convertida em
inline
Estado q passa através de ε para o estado inicial de N() ou N().Seus estados finais se tornam estados intermediáriosde todo AFN e mescla através de duas transições ε para o estado final do AFN.
A expressão de concatenação st é convertida em
inline
O estado inicial de N() é o estado inicial de todo o AFN. O estado final de N() torna-se o estado inicial de N(). O estado final de N() é o estado final de todo o AFN.
A expressão Fecho de Kleene * é convertida em
inline
Uma transição ε conecta o estado inicial e final do AFN com o sub-AFN N() no meio. Outra transição ε do estado final interior para o estado inicial interior de N() permite a repetição da expressão de acordo com o operador estrela.
The parenthesized expression () is converted to N() itself.
Exemplo Dois exemplos são dados agora , um pequeno informal com o resultado, e um maior com um passo a passo de aplicação do algoritmo.
Pequeno Exemplo A imagem mostra o resultado do algoritmo de Thompson em (ε|a*b). O círculo rosa corresponde a a, o círculo da cerceta corresponde a a*, o círculo verde corresponde a b, o círculo laranja corresponde a a*b e o círculo azul corresponde a ε.
Example of (ε|a*b) using Thompson's construction, step by step
Aplicação do algoritmo thumb|494px|AFN obtido por uma expressão regular
Como exemplo , a imagem mostra o resultado do algoritmo de Thompson na expressão regular (0|(1(01*(00)*0)*1)*)* que denota o conjunto de números binários que são múltiplos de 3: { ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110", "1001", "1100", "1111", "00000", ... }.
A parte superior direita mostra a estrutura lógica (árvore de sintaxe) da expressão, com "." denotando concatenação (assumido ter aridade variável); subexpressões são nomeadas - para fins de referência. A parte esquerda mostra o autômato finito não determinístico , resultante do algoritmo de Thompson, com o estado de e de cada sub-expressão colorida em e , respectivamente. Um ε como rótulo de transição é omitida para maior clareza — transições não marcadas estão de fato em transições ε. O estado de entrada e saída que corresponde à expressão de raiz é o estado do automato de início e aceito, respectivamente.
Os passos do algoritmo são como se segue: q: iniciar conversão da expressão de fecho de Kleene (0|(1(01*(00)*0)*1)*)* b: iniciar conversão da expressão de união 0|(1(01*(00)*0)*1)* a: converter símbolo 0 p: iniciar conversão da expressão de fecho de Kleene (1(01*(00)*0)*1)* d: iniciar conversão da expressão de concatenação 1(01*(00)*0)*1 c: converter símbolo 1 n: iniciar conversão da expressão de fecho de Kleene (01*(00)*0)* f: iniciar conversão da expressão de concatenação 01*(00)*0 e: converter símbolo 0 h: iniciar conversão da expressão de fecho de Kleene 1* g: converter símbolo 1 h: terminado a conversão da expressão de fecho de Kleene 1* l: iniciar conversão da expressão de fecho de Kleene (00)* j: iniciar conversão da expressão de concatenação 00 i: converter símbolo 0 k: converter símbolo 0 j: terminado a conversão da expressão de concatenação 00 l: terminado a conversão da expressão de fecho de Kleene (00)* m: converter símbolo 0 f: terminado a conversão da expressão de concatenação 01*(00)*0 n: terminado a conversão da expressão de fecho de Kleene (01*(00)*0)* o: converter símbolo 1 d: terminado a conversão da expressão de concatenação 1(01*(00)*0)*1 p: terminado a conversão da expressão de fecho de Kleene (1(01*(00)*0)*1)* b: terminado a conversão da expressão de união 0|(1(01*(00)*0)*1)* q: terminado a conversão da expressão de fecho de Kleene (0|(1(01*(00)*0)*1)*)*
Um autômato determinístico mínimo equivalente é mostrado abaixo.
369px|center
Relação com outros algoritmos Thompson é um dos vários algoritmos para a construção de AFNs de expressões regulares; um algoritmo anterior foi dado por McNaughton e Yamada. Converse com o algoritmo de Thompson, o Algoritmo de Kleene transforma um autômato finito em uma expressão regular.
Categoria:Teoria da computação Categoria:Matemática Thompson