Algoritmo de Thompson
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.[1] Mais precisamente, a partir de uma expressão regular Predefinição:Mvar, o autômato Predefinição:Mvar obtido com o Predefinição:Mvar da função de transição respeita as seguintes propriedades:
- Predefinição:Mvar tem exatamente um estado inicial Predefinição:Math, que não é acessível a partir de nenhum outro estado. Ou seja, para qualquer estado Predefinição:Mvar e qualquer letra Predefinição:Mvar, não contém Predefinição:Math.
- Predefinição:Mvar tem exatamente um estado final Predefinição:Mvar, que não é co-acessível a partir de nenhum outro estado. Isto é, para qualquer letra Predefinição:Mvar, .
- Seja Predefinição:Mvar o número de concatenação da expressão regular Predefinição:Mvar e seja Predefinição:Mvar o número de símbolos à parte de parênteses — Isto é, Predefinição:Math, Predefinição:Math, Predefinição:Mvar e Predefinição:Mvar. Em seguida, o número de estados de Predefinição:Mvar é Predefinição:Math (linear no tamanho de Predefinição:Mvar).
- O número de transições que deixam qualquer estado é de no máximo dois.
- Uma vez que um AFN de Predefinição:Mvar estados e no máximo Predefinição:Mvar transições de cada estado pode corresponder a uma cadeia de comprimento Predefinição:Mvar em tempo Predefinição:Math, um AFN de Thompson pode fazer a correspondência de padrões em tempo linear,assumindo um alfabeto de tamanho fixo.[2]
Regras
As regras a seguir são descritas de acordo com Aho et al. (1986),[3] p. 122. N(Predefinição:Color) eN(Predefinição:Color) é o AFN da subexpressão Predefinição:Color e Predefinição:Color, respectivamente.
A expressão-vazia ε é convertida em
Um símbolo a de um alfabeto de entrada é convertido em
A expressão de união Predefinição:Color|Predefinição:Color é convertida em
Estado q passa através de ε para o estado inicial de N(Predefinição:Color) ou N(Predefinição:Color).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
O estado inicial de N(Predefinição:Color) é o estado inicial de todo o AFN. O estado final de N(Predefinição:Color) torna-se o estado inicial de N(Predefinição:Color). O estado final de N(Predefinição:Color) é o estado final de todo o AFN.
A expressão Fecho de Kleene Predefinição:Color* é convertida em
Uma transição ε conecta o estado inicial e final do AFN com o sub-AFN N(Predefinição:Color) no meio. Outra transição ε do estado final interior para o estado inicial interior de N(Predefinição:Color) permite a repetição da expressão Predefinição:Color de acordo com o operador estrela.
- The parenthesized expression (Predefinição:Color) is converted to N(Predefinição:Color) 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 ε.
Aplicação do algoritmo
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 Predefinição:Color-Predefinição:Color 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 Predefinição:Color e Predefinição:Color de cada sub-expressão colorida em Predefinição:Color e Predefinição:Color, 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 Predefinição:Color é 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.
Relação com outros algoritmos
Thompson é um dos vários algoritmos para a construção de AFNs de expressões regulares;[4] um algoritmo anterior foi dado por McNaughton e Yamada.[5] Converse com o algoritmo de Thompson, o Algoritmo de Kleene transforma um autômato finito em uma expressão regular.
- ↑ Predefinição:Citar periódico
- ↑ Predefinição:Citar web
- ↑ Alfred V. Aho, Ravi Sethi, Jeffrey Ullman: Compilers: Principles, Techniques and Tools. Addison Wesley, 1986
- ↑ Predefinição:Citar relatório técnico
- ↑ Predefinição:Citar periódico