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, estealgoritmo é 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.