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 $E$ , o autômato $A$ obtido com o $δ$ da função de transição respeita as seguintes propriedades:

$A$ tem exatamente um estado inicial $q 0$ , que não é acessível a partir de nenhum outro estado. Ou seja, para qualquer estado $q$ e qualquer letra $a$ , $\delta (q,a)$ não contém $q 0$ .
$A$ tem exatamente um estado final $q f$ , que não é co-acessível a partir de nenhum outro estado. Isto é, para qualquer letra $a$ , $\delta (q_{f},a)=\emptyset$ .
Seja $c$ o número de concatenação da expressão regular $E$ e seja $s$ o número de símbolos à parte de parênteses — Isto é, $|$ , $*$ , $a$ e $ε$ . Em seguida, o número de estados de $A$ é $2 s - c$ (linear no tamanho de $E$ ).
O número de transições que deixam qualquer estado é de no máximo dois.
Uma vez que um AFN de $m$ estados e no máximo $e$ transições de cada estado pode corresponder a uma cadeia de comprimento $n$ em tempo $O (emn)$ , 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(s) eN(t) é o AFN da subexpressão s e t, respectivamente.

A expressão-vazia ε é convertida em

Um símbolo a de um alfabeto de entrada é convertido em

A expressão de união s|t é convertida em

Estado q passa através de ε para o estado inicial de N(s) ou N(t).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(s) é o estado inicial de todo o AFN. O estado final de N(s) torna-se o estado inicial de N(t). O estado final de N(t) é o estado final de todo o AFN.

A expressão Fecho de Kleene s^* é convertida em

Uma transição ε conecta o estado inicial e final do AFN com o sub-AFN N(s) no meio. Outra transição ε do estado final interior para o estado inicial interior de N(s) permite a repetição da expressão s de acordo com o operador estrela.

The parenthesized expression (s) is converted to N(s) 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 a-q 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 entrada e saída de cada sub-expressão colorida em magenta e ciano, 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 q é 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.

Referências

↑ Ken Thompson (junho de 1968). «Programming Techniques: Regular expression search algorithm». Communications of the ACM. 11 (6): 419-422. doi:10.1145/363347.363387
↑ Xing, Guangming. «Minimized Thompson NFA» (PDF)
↑ Alfred V. Aho, Ravi Sethi, Jeffrey Ullman: Compilers: Principles, Techniques and Tools. Addison Wesley, 1986
↑ Watson, Bruce W. (1995). A taxonomy of finite automata construction algorithms (PDF) (Relatório técnico). Eindhoven University of Technology. Computing Science Report 93/43
↑ R. McNaughton, H. Yamada (março de 1960). «Regular Expressions and State Graphs for Automata». IEEE Trans. on Electronic Computers. 9 (1): 39-47. doi:10.1109/TEC.1960.5221603

[1] Ken Thompson (junho de 1968). «Programming Techniques: Regular expression search algorithm». Communications of the ACM. 11 (6): 419-422. doi:10.1145/363347.363387

[2] Xing, Guangming. «Minimized Thompson NFA» (PDF)

[3] Alfred V. Aho, Ravi Sethi, Jeffrey Ullman: Compilers: Principles, Techniques and Tools. Addison Wesley, 1986

[4] Watson, Bruce W. (1995). A taxonomy of finite automata construction algorithms (PDF) (Relatório técnico). Eindhoven University of Technology. Computing Science Report 93/43

[5] R. McNaughton, H. Yamada (março de 1960). «Regular Expressions and State Graphs for Automata». IEEE Trans. on Electronic Computers. 9 (1): 39-47. doi:10.1109/TEC.1960.5221603

[1]

[2]

[3]

[4]

[5]