¿Cuándo es una expresión regular no es una expresión regular?

Como estoy estudiando para mi curso universitario de idiomas formales, me topé con estas fascinantes publicaciones ( One Two ) que describen cómo encontrar un número primo usando una expresión regular . Como ya he dicho, una expresión regular , no una expresión regular . Dado que una expresión regular puede coincidir con cadenas calculadas por Autómatas de estado finito y una FSA no puede encontrar un número primo, la expresión regular que se muestra en la publicación del blog no es del todo una expresión regular, ya que hace un retroceso para coincidir con la cadena.

Como nunca he usado realmente ninguna expresión regular, ahora, mi pregunta:

¿Cómo puedo reconocer inmediatamente una expresión regular de una expresión regular "verdadera" con solo mirarla?

Definiciones: Por expresión regular, me refiero a la noción como se define en los lenguajes formales. Por regexp, me refiero a la noción soportada por los lenguajes de programación modernos; la sintaxis regexp a menudo contiene características adicionales, como referencias posteriores. Las expresiones regulares como se ve en los lenguajes de programación son estrictamente más poderosas que las expresiones regulares de estilo de lenguajes formales.

tl; dr backrefs.

Tan pronto como haya un \1(o cualquier número que no se use para escapar de Unicode) en la expresión regular, no es una expresión regular.

Backrefs le permite hacer coincidir (a+)b\1qué coincide n veces aseguido de b seguido de n veces apara cualquier n> 1. Este no es un idioma regular (es el póster hijo de un idioma no regular).

Es necesario y casi suficiente que la referencia de referencia haga referencia a un grupo que contiene una expresión regular que coincide con una cadena arbitrariamente larga o que contiene una *o +. La única excepción (que encontré) de una expresión regular de la forma (A)B\1en la que A es un lenguaje finito (podría reemplazarse por una enumeración de todas las palabras que las acepta). Puede convertirlo a word1+Bword1|word2+Bword2etc. porque A es finito.

Los grupos de búsqueda no eliminan la regularidad de la expresión regular. A(?=B)Ces la sección transversal de las expresiones regulares AB.*y ACla sección transversal de 2 idiomas regulares es regular. La búsqueda anticipada negativa es similar, excepto que utiliza el complemento de B.*(los complementos de los idiomas regulares son regulares). Mirar hacia atrás es exactamente igual, así como A(?<=B)Cla sección transversal de ACy .*BC.