A pregunta que respondí me hizo preguntarme:

¿Cómo se implementan las expresiones regulares en Python? ¿Qué tipo de garantías de eficiencia hay? ¿La implementación es "estándar" o está sujeta a cambios?

Pensé que las expresiones regulares se implementarían como DFA y, por lo tanto, eran muy eficientes (requiriendo como máximo un escaneo de la cadena de entrada). @Laurence Gonsalves planteó un punto interesante de que no todas las expresiones regulares de Python son regulares. (Su ejemplo es r "(a +) b \ 1", que coincide con un número de a's, a b, y luego el mismo número de a's que antes). Esto claramente no se puede implementar con un DFA.

Entonces, para reiterar: ¿cuáles son los detalles de implementación y las garantías de las expresiones regulares de Python?

También sería bueno que alguien pudiera dar algún tipo de explicación (a la luz de la implementación) de por qué las expresiones regulares "cat | catdog" y "catdog | cat" conducen a resultados de búsqueda diferentes en la cadena "catdog", como se menciona en el pregunta a la que hice referencia antes.