¿Por qué no hay permutación en expresiones regulares? (Incluso si los idiomas normales parecen ser capaces de hacer esto)

13

El problema

No hay una manera fácil de obtener una permutación con una expresión regular.

  • Permutación: Obtener una palabra ("aabc") en otro orden, sin cambiar el número o el tipo de letras.
    w=x1xn
  • Regex: expresión regular.

Para verificar:

El tipo de solución que estoy buscando

Debe tener la forma:

  • »Aabc« (o cualquier otra cosa que pueda usar entre paréntesis de apertura y cierre)
  • (aabc)! (similar a (abc)? pero con otro símbolo al final)
  • [aabc]! (similar a [abc] + pero con otro símbolo al final)

Ventajas de estas soluciones

Son:

  • fácil
  • adaptable
  • reutilizable

Por qué esto debería existir

  • Las expresiones regulares son una forma de describir una gramática de un lenguaje regular. Tienen todo el poder de ser cualquier tipo de lenguaje regular.
  • Digamos que los lenguajes regulares son lo suficientemente potentes para las permutaciones (prueba a continuación): ¿por qué no hay una manera fácil de expresar esto?

Entonces mi pregunta es:

  • (¿Por qué?) ¿Está equivocada mi prueba?
  • Si es correcto: ¿por qué no hay una manera fácil de expresar permutaciones?

La prueba

  • Las expresiones regulares son una forma de notar la gramática de un lenguaje regular. Pueden describir cualquier gramática de idiomas regulares.
  • Otra forma de describir cualquier gramática de los idiomas regulares (que tienen un número finito de letras dentro de su alfabeto) son los autómatas no deterministas (con un número finito de estados).

Con un número finito de letras, puedo crear este autómata: (Ejemplo. Formal: ver más abajo)

Gramática que acepta permutaciones de "abbc":

(busque números en la parte superior, tal vez alguien sepa cómo hacer que esta parte se vea mejor)

s -> ah¹

s -> bh²

s -> ch³

h¹ -> bh¹¹

h¹ -> ch¹²

h² -> ah¹¹ (sin error tipográfico)

h² -> bh²²

h² -> ch²³

h³ -> ah¹²

h³ -> bh²³

h¹¹ -> bc

h¹¹ -> cb

h¹² -> bb

h²² -> ac

h²² -> ca

h²³ -> ab

h²³ -> ba

Más formal: (usando un autómata de estado finito, pero esto también podría hacerse con gramática)

  • Una palabra q (con longitud finita) a la que cualquier permutación debe alcanzar un estado de aceptación.
  • X es el alfabeto finito.
  • El conjunto de estados S contiene cualquier orden de letras hasta la longitud de q. (Por lo tanto, el tamaño de S es finito). Más un estado de "cualquier palabra más larga".
  • función de transición de estado d que toma una letra y se mueve en el estado que corresponde a la parte ahora leída de la palabra.
  • F es un conjunto de estados que son permutaciones exactas de q.

Por lo tanto, es posible crear un autómata de estado finito para aceptar permutaciones de una palabra dada.

Continuando con la prueba

Así que he demostrado que los idiomas normales tienen el poder de verificar las permutaciones, ¿no?

Entonces, ¿por qué no hay un enfoque para alcanzar esto con Regexes? Es una funcionalidad útil.

Asqiir
fuente
10
Puede enumerar todas las permutaciones de su palabra con una expresión regular. La expresión resultante será bastante grande, pero definitivamente será una expresión regular.
Yuval Filmus
77
Sugiero ignorar todas las respuestas sobre Teoría de la Computación en stackoverflow. Esta no es la especialidad de ese sitio.
Yuval Filmus
La respuesta en su página vinculada aquí - stackoverflow.com/a/3102205/6936386 - parece ser fácilmente adaptable y no demasiado complicada: ^(a()|a()|b()|c()){4}\2\3\4\5$parece funcionar (ver regex101.com/r/9URPpg/4/tests ).
boboquack
77
@boboquack Esa no es una expresión regular en el sentido en que se usa el término en informática. (Este tipo de cosas es exactamente por qué Yuval sugiere no confiar en las respuestas de Stack Overflow sobre CS teóricas).
David Richerby

Respuestas:

37

Los teoremas fundamentales de la teoría del lenguaje formal son que las expresiones regulares, las gramáticas regulares, los autómatas finitos deterministas (DFA) y los autómatas finitos no deterministas (NFA) describen todos los mismos tipos de lenguajes: a saber, los lenguajes regulares. El hecho de que podamos describir estos idiomas de maneras completamente diferentes sugiere que hay algo natural e importante acerca de estos idiomas, de la misma manera que la equivalencia de las máquinas de Turing, el cálculo lambda y todo tipo de otras cosas sugiere que los lenguajes computables Son naturales e importantes. No son solo un artefacto de las decisiones aleatorias que tomó el descubridor original.

Supongamos que añadimos una nueva regla para la creación de expresiones regulares: si  es una expresión regular, entonces es una expresión regular, y que coincide con todas las permutaciones de cada cadena coincidente por  . Entonces, por ejemplo, . El problema es que esto rompe las equivalencias fundamentales descritas anteriormente. es el idioma de las cadenas que contienen un número igual de sy sy este no es un lenguaje normal. Compare esto con, por ejemplo, agregar un operador de negación o inversión a las expresiones regulares, lo que no cambia la clase de lenguajes que se aceptan.Rπ(R)RL(π(abc))={abc,acb,bac,bca,cab,cba}L(π((ab))))ab

Entonces, para responder la pregunta del título, las expresiones regulares no pueden hacer permutaciones y no agregamos esa capacidad porque las expresiones regulares no coincidirían con los lenguajes regulares. Dicho esto, es posible que las "expresiones regulares con permutaciones" también sean una clase interesante de lenguajes con muchas caracterizaciones diferentes.

David Richerby
fuente
Pero L ((ab) *) tampoco es un lenguaje regular, por lo que L (perm ((ab) *)) no puede ser uno. ((ab) * no es un lenguaje normal ya que no hay ningún tipo de memoria para recordar cuántas "a" s de apertura hay, así que con un número finito de estados no se puede poner el mismo número de "b" s).
Asqiir
99
@Asqiir es regular porque es el lenguaje que coincide con la expresión regular dada. Parece que has entendido mal el idioma. Es , no . El último idioma no es regular, pero ese no es el idioma del que estamos hablando. L((ab)){ε,ab,abab,ababab,abababab,}{ε,ab,aabb,aaabbb,aaaabbbb,}
David Richerby
44
@Asqiir Es ese lenguaje porque es lo que obtienes al aplicar cualquier permutación que desees a un idioma en el que cada cadena contenía el mismo número de sy s; no es regular porque puede probar que usa el lema de bombeo. ab
David Richerby
2
Tienes toda la razón. Perdí el punto de "poner expresiones regulares entre sí", solo pensé en "permutar una palabra fija" no "permutar otra expresión regular" que por supuesto no es posible.
Asqiir
1
Tal vez las expresiones regulares con permutaciones describen una clase de lenguajes con propiedades interesantes, pero nunca me he encontrado con la necesidad del !operador en la práctica, y supongo que pocas personas lo tienen, ya que es fácil de implementar y no implementan expresiones regulares extendidas. Lo he visto lo apoya.
reinierpost
16

Entonces mi pregunta es:

  • (¿Por qué?) ¿Está equivocada mi prueba?
  • Si es correcto: ¿por qué no hay una manera fácil de expresar permutaciones?

Su "prueba" solo miró permutaciones de palabras individuales, que son idiomas finitos.

Cada idioma finito es regular (por ejemplo, simplemente enumerando todos los miembros con un |intermedio), pero hay infinitos idiomas regulares (y esos son generalmente los más interesantes).

Tan pronto como obtenga una expresión regular (o gramática / autómata) que acepte un lenguaje infinito (es decir, una expresión con el *operador o un autómata con un bucle), su construcción ya no funcionará (obtendrá una gramática / autómata infinito) )

La respuesta de David Richerby proporcionó un ejemplo de un lenguaje regular cuyo lenguaje de permutación ya no es regular; todos estos ejemplos son idiomas infinitos.

Paŭlo Ebermann
fuente
8

Sea un alfabeto de tamaño . Una expresión regular que describe todas las permutaciones de debe tener un tamaño exponencial. Esto se desprende del Teorema 9 en Límites inferiores para las gramáticas libres de contexto , que proporciona un límite inferior exponencial en el modelo mucho más fuerte de las gramáticas libres de contexto (una expresión regular de tamaño se puede convertir en una gramática libre de contexto de tamaño ).ΣnΣmO(m)

Entonces, en cierto sentido, no hay una forma sucinta de especificar todas las permutaciones de una palabra.


Aquí hay una prueba simple para un límite inferior en el tamaño de una expresión regular para el lenguaje de todas las permutaciones de un alfabeto de tamaño . Dado que una expresión regular de tamaño se puede convertir en un NFA con estados , es suficiente dar un límite inferior en los NFA.Ω~(2n)ΣnmO(m)

L(xi,yi)1iN

  • xiyiL
  • ijxiyjLxjyiL

LNLixiyiqixiqiqjijqi=qjxiyjxjyiL

Lnσ1,,σnnSσ1,,σnn/2xSSySSxSySLnSTxSyTLnLn(nn/2)=Ω(2n/n)

Yuval Filmus
fuente
¿Significa esto que 1) en teoría sería posible dejar que »abc« coincida con todos {abc, acb, bac, bca, cab, cba} pero simplemente no es eficiente y los haría demasiado lentos ya que »abc« se expandiría exponencialmente a (abc | acb | bac | bca | cab | cba)? o 2) ¿El tipo de autómata que necesito no puede especificar todas las permutaciones para una palabra dada?
Asqiir
1
Aquí hay una expresión regular que coincide con todas las permutaciones de : . Puede convertir esto fácilmente en un DFA que tenga estados. Lo mismo funciona para . a b c + a c d + b a c + b c a + c a b + c b a 1 + 3 + 6 + 6 + 1 = 17 a b c d e f g h i jabcabc+acd+bac+bca+cab+cba1+3+6+6+1=17abcdefghij
Yuval Filmus
1
Lo que entendí: en teoría, los lenguajes regulares pueden aceptar permutaciones (al igual que las expresiones regulares). Simplemente no hay una "forma simple" de escribir "permutación de abc" como »abc«. (Por cualquier razón.)
Asqiir
1
Sí, ese es un buen resumen. Veré si puedo encontrar un argumento más simple para las expresiones regulares.
Yuval Filmus
2
Para futuros lectores: ¡esta no es la respuesta correcta! (Corrígeme si me equivoco). Busca el aceptado.
Asqiir
0

¿Por qué no hay forma de escribir "permutación de" en expresiones regulares?

Una permutación de un lenguaje regular e infinito (cantidad infinita de palabras) no es necesariamente regular. Por lo tanto, no se puede escribir como expresión regular.

Prueba

Piensa en el lenguaje (ab)*. (Ejemplo inspirado en David Richerby .) Una de sus permutaciones es a*b*. Este no es un lenguaje normal. qed

Asqiir
fuente