¿Están completadas las expresiones regulares de .NET?

Question

Las expresiones regulares a menudo se apuntan como el ejemplo clásico de un lenguaje que no se está volviendo completo. Por ejemplo, las "expresiones regulares" se otorgan como la respuesta a esta pregunta Buscando idiomas que no estén completos.

En mi comprensión, quizás algo básica, de la noción de integrar la integridad, esto significa que las expresiones regulares no se pueden usar, verifique los patrones que estén "equilibrados". El significado equilibrado tiene un número igual de personajes de apertura como personajes de cierre. Esto se debe a que hacer esto requeriría que tenga algún tipo de estado, para permitirle que coincida con los personajes de apertura y cierre.

Sin embargo, la implementación de .NET de expresiones regulares introduce la noción de un grupo equilibrado. Esta construcción está diseñada para permitirle retroceder y ver si se combinó un grupo anterior. Esto significa que un .NET expresiones regulares:

^(?<p>a)*(?<-p>b)*(?(p)(?!))$

Podría coincidir con un patrón que:

ab
aabb
aaabbb
aaaabbbb
... etc. ...

¿Esto significa que las expresiones regulares de .NET están completas? ¿O hay otras cosas que faltan que se requerirían para que el idioma sea completo?

Answer 1

En la teoría del cálculo, una expresión regular describe un lenguaje regular. La clase de idiomas regulares es precisamente aquellos idiomas que pueden ser reconocidos por alguna máquina de estado finito, o generadas por una gramática regular. Sin embargo, el ejemplo que ha descrito (frases equilibradas) no es un lenguaje regular y no puede ser reconocido por una máquina de estado finito o generado por una gramática regular. De hecho, este es un ejemplo de libro de texto de lo que se llama lenguaje sin contexto. Estos requieren un autómata de empuje para el reconocimiento. La clase de idiomas sin contexto es un superconjunto de idiomas regulares, pero un subconjunto adecuado de idiomas completos. La sintaxis (a diferencia de la semántica) de la mayoría de los lenguajes de programación es un lenguaje libre de contexto. Si está interesado en aprender más sobre este tema, puede comenzar con el Jerarquía de Chomsky

Answer 2

Se pierde la definición de Turing Complete.

La integridad de Turing, que lleva el nombre de Alan Turing, es significativa en el sentido de que cada diseño plausible para un dispositivo informático hasta ahora avanzado puede ser emulado por una máquina universal, una observación que se ha conocido como la tesis que aturde la iglesia. Por lo tanto, una máquina que puede actuar como una máquina universal de Turing puede, en principio, realizar cualquier cálculo que cualquier otra computadora programable sea capaz. Sin embargo, esto no tiene nada que ver con el esfuerzo requerido para escribir un programa para la máquina, el tiempo que puede tomar que la máquina realice el cálculo o cualquier habilidad que la máquina pueda poseer que no esté relacionada con el cálculo.

Ahora, no puede hacer ciertas cosas en expresiones regulares, por lo que el Langauge no está completo.

Realmente tienes que usar la misma definición que todos los demás, ya sabes. La comprensión limitada debería desencadenar descubrir la verdad.

Answer 3

Regex's in .net no está completo porque siempre se detienen. Esto no se puede decir de una máquina de Turing General.

Answer 4

@Inuyasha: En realidad, puedes hacer una adición con una expresión regular. Bueno, al menos verifique si el cálculo se realiza correctamente. Lo único es que tiene que dar la entrada al Regex en un orden extraño (no puede revertir una cadena (o verificar si se invierte) con una regex).

El patrón es:

abc
def
---
ghi

=> cfi beh adg

Supongamos que desea agregar 1011 un 0110 en binario:

01011
00110
-----
10001


=> 101 110 010 100 001

Si da esta entrada en el orden de arrendamiento de bits significativos al mejor, intercalando el primer operando, el segundo operando y la salida, obtendría la cadena 101110010100001. Esto se puede igualar por

((000|011|101)|(110(010|100|111)*001))*

Que es una variedad de jardín regex. Podrías extender esto a la adición decimal, pero el Regex se volvería loco.