Contenido
PalancaConstrucción Thompson
El algoritmo de Thompson o construcción de Thompson permite construir un autómata no determinista con epsilon-transition de un expresión regular. El autómata se construye recursivamente a partir de patrones básicos:
Los elementos unitarios como ∅, ε y a son reconocidos por
![Edificio Thompson Edificio Thompson construcción thompson](https://complex-systems-ai.com/wp-content/uploads/2018/05/langage15.png)
Consideramos los operadores de la expresión regular R en orden decreciente de exterioridad. El operador más externo permite dividir R en R1 | R2, R1.R2 o R1 * que son reconocidos por
![Edificio Thompson Edificio Thompson construcción thompson](https://complex-systems-ai.com/wp-content/uploads/2018/05/langage16.png)
Aquí hay un ejemplo de construcción con la expresión (a | b) (a ∗ | ba ∗ | b ∗) ∗
Comenzamos la recursividad creando (A) (B); el contenido es solo indicativo, veremos cómo completar A y B a medida que avanzamos.
![Edificio Thompson Edificio Thompson construcción thompson](https://complex-systems-ai.com/wp-content/uploads/2018/05/langage17.png)
Luego, colocando la estrella en (B) *, aquí aprovechamos la oportunidad para hacer la función OR en (A) = (a | b).
![Edificio Thompson Edificio Thompson construcción thompson](https://complex-systems-ai.com/wp-content/uploads/2018/05/langage18.png)
El siguiente paso es hacer la función OR en (B) = (C | D | E)
![Edificio Thompson Edificio Thompson construcción thompson](https://complex-systems-ai.com/wp-content/uploads/2018/05/langage19.png)
El proceso se contuvo descendiendo de forma recursiva hasta obtener el autómata Thompson final.
![Edificio Thompson Edificio Thompson construcción thompson](https://complex-systems-ai.com/wp-content/uploads/2018/05/langage20.png)
Este último debe determinarse y minimizarse para una mejor lectura.
Algunos ejemplos sencillos
- 01∗
- (0 + 1)01
- 00(0 + 1)*
![Edificio Thompson Edificio Thompson construcción thompson](https://complex-systems-ai.com/wp-content/uploads/2018/09/langage59.png)