Algoritmo de Thompson

El algoritmo Thompson (también conocido como método de Thompson) creado por Ken Thompson y Dennis Ritchie, sirve para obtener autómatas finitos no deterministas con transiciones vacías (AFND-ε) a partir de expresiones regulares (ER).

Algoritmo

Dadas las reglas que definen las expresiones regulares se pueden escribir como AFND-e:

Las precedencias de operador son *,., +.

Para el operador + de una ER el AFND-ε se arma de la siguiente manera:

Donde M1 y M2 son los AFND-ε que se suman.

Para el operador . de una ER el AFND-ε se arma de la siguiente manera:

Donde M1 y M2 son los AFND-ε que se concatenan.

Para el operador * de una ER el AFND-e se arma de la siguiente manera:

Donde M1 es el AFND-ε que se le aplica la clausura.

Herramientas

Existen varios programas que realizan este algoritmo y de hecho es habitual también pasar de AFND-e a AFND y de AFND a AFD, también suele ocurrir que el AFD no sea mínimo y se usa otro algoritmo para conseguir el AFD mínimo.

Cualquier ER puede ser reconocida por un AFD ya que los lenguaje regulares de tipo 3 son reconocidos por un AFD como autómata mas restrictivo habiendo equivalencia entre no determinismo y determinismo. Generalmente los programas que aplican el algoritmo suelen transformar una ER a AFD mínimo.

Algunos programas son:

Enlaces externos

Apunte de Gramaticas Regulares y Expresiones Regulares UNICEN

This article is issued from Wikipedia - version of the Saturday, December 21, 2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.