Construcción de Thompson
Inducción: r posee uno o más operadores.
Base: supongamos que el teorema se cumple para expresiones regulares con menos de i operadores, (i ? 1).
Sea r una expresión regular con exactamente i operadores. Hay tres posibilidades dependiendo de la forma de r :
Tanto r1 como r2 han de tener menos de i operadores, por lo cual (hipótesis de inducción) existirán autómatas
M1?(?1, Q1, q1, {f1}, ?1) y
M2?(?2, Q2, q2, {f2}, ?2) tales que
L(M1)=L(r1) y L(M2)=L(r2)