Construcción de Thompson
Todo camino en este NFA que vaya desde q1 a f2 es un camino que estará etiquetado con alguna cadena x de símbolos desde q1 hasta f1 seguida por el arco etiquetado ? que une f1 con q2, seguido de un camino desde q2 hasta f2 etiquetados con símbolos de una cadena y.
Así tenemos que L(M)={xy| x?L(M1) ? y?L(M2)} y por lo tanto L(M)=L(M1)L(M2) como pretendíamos.