A pergunta que eu respondi me fez pensar:

Como as expressões regulares são implementadas em Python? Que tipo de garantias de eficiência existem? A implementação é "padrão" ou está sujeita a alterações?

Pensei que expressões regulares seriam implementadas como DFAs e, portanto, eram muito eficientes (exigindo no máximo uma varredura da string de entrada).Laurence Gonsalves levantou um ponto interessante de que nem todas as expressões regulares do Python são regulares. (O exemplo dele é r "(a +) b \ 1", que corresponde a algum número de a, a b e, em seguida, o mesmo número de a como antes). Isso claramente não pode ser implementado com um DFA.

ntão, para reiterar: quais são os detalhes e as garantias de implementação das expressões regulares do Pytho

Também seria bom se alguém pudesse dar algum tipo de explicação (à luz da implementação) sobre por que as expressões regulares "cat | catdog" e "catdog | cat" levam a diferentes resultados de pesquisa na string "catdog", como mencionado no pergunta que eu referenciei antes.