Construcción de Thompson
Sea r una expresión regular
Existe un NFA que acepta el lenguaje L(r)
Utilizaremos inducción sobre el número de operadores en la expresión regular para demostrar que existe un NFA M con un único estado final y que no posee transiciones fuera de ese estado final, tal que L(M)=L(r)
- Base de la inducción: r no tiene operadores
En este caso r ha de ser ?, ? o bien a para algún a ??