Una expresión regular se define de forma recursiva como
- para algunos a ∈ Σ es una expresión regular,
- es una expresión regular,
- es una expresión regular,
- donde R 1 y R 2 son expresiones regulares es una expresión regular,
- donde R 1 y R 2 son expresiones regulares es una expresión regular,
- donde R 1 es una expresión regular es una expresión regular.
Esta definición está tomada de la página 64 de
Sipser, Michael. Introducción a la teoría de la computación, 3ra edición. Cengage Learning, 2012.
Ahora tengo las siguientes preguntas.
- ¿Por qué no contiene la definición de los
intersection
,complement
oreverse
las operaciones? - Si cambiamos el 4º elemento a , ¿obtenemos una definición equivalente, es decir, para cada idioma regular, hay una expresión regular modificada y viceversa?
- Sé que esta definición es completa y bien definida, pero ¿por qué se prefiere a otras definiciones equivalentes, bien definidas y completas?
formal-languages
regular-languages
regular-expressions
Ali Shakiba
fuente
fuente
Respuestas:
1) Si también permitimos la intersección y el complemento, las expresiones resultantes a veces se denominan expresiones regulares extendidas; Como los lenguajes regulares se cierran bajo operaciones booleanas, no ganan nada. Es solo azúcar sintáctico. Una conclusión similar es válida para la operación inversa. Parte de la razón por la cual, en primera instancia, no se mencionan todas las demás operaciones es el objetivo de mantener la definición lo más simple posible, de modo que las pruebas (inductivas) no tengan que ocuparse en muchos casos. Otra causa podría ser que si permitimos ciertas operaciones, pero otras no, en algunos casos resultan en clases de lenguaje muy distintas (subregulares), por ejemplo, si consideramos la expresión regular extendida sin el operador estrella, entonces obtenemos una subclase adecuada de las regulares. , los llamados lenguajes sin estrellas o aperiódicos, consulte wikipedia: lenguaje sin estrellas .
fuente
El informe técnico que introdujo lenguajes regulares, expresiones regulares y autómatas finitos hace su pregunta en la página 70:
La respuesta ocupa varias páginas. Primero, se observa que la respuesta debe buscarse en si los idiomas resultantes forman una clase interesante y cómo se comparan con los idiomas descritos por otros medios. En la página 72, se observa que la negación y la conjunción son redundantes: no agregan ningún poder expresivo. En la página 80 y más, se demuestra que los idiomas regulares son exactamente los idiomas reconocidos por las máquinas de estados finitos.
En otras palabras: la respuesta de Stefan puede considerarse concluyente con seguridad, como ya se dio en el informe que introdujo por primera vez estos conceptos.
fuente
A partir de esta selección de operadores (unión, concatenación y estrella) se puede construir un NFA con un tamaño lineal al tamaño de la expresión. Por otro lado, si agrega intersección y complementación, el tamaño del autómata equivalente puede explotar de manera no elemental, lo que generalmente no es deseable.
fuente