Una cadena que empareja el algoritmo que construye una máquina de Estados finitos determinista para reconocer la cadena de búsqueda. La máquina entonces se ejecuta alternadamente en cada lugar. Si acepta la máquina, que es una coincidencia.