¿Cuál es el poder de las expresiones regulares?

Como su nombre lo sugiere, podemos pensar que las expresiones regulares solo pueden coincidir con los idiomas normales. Pero las expresiones regulares que usamos en la práctica contienen cosas que no estoy seguro de que sea posible implementar con sus homólogos teóricos. ¿Cómo, por ejemplo, simularías una retrospectiva? Entonces surge la pregunta: ¿cuál es el poder teórico de las expresiones regulares que usamos en la práctica? ¿Puedes pensar en una forma de hacer coincidir {(a^n)(b^n)|n>=0}? ¿Qué hay de {(a^n)(b^n)(c^n)|n>=0}?¿Cuál es el poder de las expresiones regulares?

Fuente

2010-09-23 Artium

Necesita definir aún más "expresiones regulares que usamos en la práctica". Diferentes motores regex varían en potencia. – sepp2k

Existen expresiones que coinciden con sus ejemplos para el motor .NET Regex utilizando grupos de captura equilibrados. '"^(a (? )) * (b (? )) * (? (a) (?!)) $ "' para la primera, p. – Jens

Esto parece más como una pregunta para los teóricos computacionales que para un sitio de programación. –

La respuesta a su pregunta es que los lenguajes de "expresiones regulares" que permiten referencias no son ni regulares ni contextuales. (En otras palabras, como señaló, no puede simular referencias con un lenguaje regular, ni con una CFL). De hecho, Wikipedia dice que muchos de los lenguajes de "expresión regular" que usamos en la práctica son NP-Complete:

coincidencia de patrones con una ilimitada número de referencias de la espalda, como apoyado por numerosas herramientas modernas, es NP-completo (véase, [11] Teorema 6.2).

Como otros han sugerido, los lenguajes de expresiones regulares comúnmente admitidos en lenguajes de programación y bibliotecas son un animal diferente de las expresiones regulares en la teoría del lenguaje formal. Larry Wall wrote en lo que respecta a Perl expresiones regulares ""

'' Las expresiones regulares [...] sólo son marginalmente relacionadas con los bienes expresiones regulares. Sin embargo, el término ha crecido con las capacidades de nuestros motores de combinación de patrones , así que no estoy tratando de luchar contra la necesidad lingüística aquí.Yo, sin embargo, general, los llaman "expresiones regulares"

Usted preguntó,

¿Se puede pensar en una forma para que coincida con {(a^n) (b^n) | n> = 0}? ¿Qué pasa con {(a^n) (b^n) (c^n) | n> = 0}?

No estoy seguro de que aquí si usted está tratando de probar si teóricos lenguajes de expresiones regulares pueden coincidir con el "lenguaje de los cuadrados", o si usted está buscando una implementación en un (práctica) regex idioma. Here's the proof why the former is not possible; y here's a long explanation and implementation of the latter para expresiones regulares de Java.

Fuente

2010-09-28 20:24:22 LarsH

La dificultad básica con las expresiones regulares que está insinuando es el hecho de que las expresiones regulares no tienen una "memoria" para ellas. En la forma más pura, ninguna expresión regular real debería ser capaz de reconocer ninguno de estos lenguajes. Cualquier expresión regular que pueda analizar estos tipos de idiomas sería, por definición, no regular. Creo que lo que quiere decir con "expresiones regulares que usamos es practicar" es extendidas expresiones regulares, que no son expresiones técnicamente regulares.

El problema con su pregunta es que está solicitando aplicar un escenario teórico específicamente inventado a una situación práctica, que casi siempre termina en un desastre.

Así que mi respuesta es una especie de falta de respuesta, en el sentido de que debo reformular la pregunta para preguntar acerca de las expresiones regulares extendidas para que tenga una respuesta.

Un par de recursos que podrían ayudar en este asunto:

Helpful wikipedia article

¿Cuál es el poder de las expresiones regulares?

Respuesta

Cuestiones relacionadas