☰

¿Es posible separar estas expresiones simétricas sobre {0,1}

tag-icon • tag-icon grep
¿Es posible separar estas expresiones simétricas sobre {0,1}

El objetivo es utilizar únicamente egrep para hacer coincidir expresiones dondenortelas apariciones de 0 van seguidas exactamente denorteapariciones de 1 y donde ningún 0 sigue a un 1.

p.ej

01
000111
000000111111

pero no:

001
011
00011

etc.

Intuitivamente, esto no parece posible debido a que las expresiones coincidentes no tienen una longitud fija. ¿Pero tal vez me falta una característica de egrep que podría ser útil con esto?

Respuesta1

Descripción general rápida de algunos conceptos de informática:

  • Autómatasaceptar cadenas que pertenecen a un "idioma",generado por una "gramática".
  • Las expresiones regulares (en teoría) son equivalentes a (deterministas o no deterministas)autómatas finitos(DFA/NFA). Entonces, dada una expresión regular como 0*1*, existen DFA y NFA que pueden aceptar cadenas que coincidan con esa expresión regular.
  • Los autómatas finitos son estrictamente menos poderosos queautómatas de empuje(PDA). La clase de lenguajes que acepta el PDA son generados porgramáticas libres de contexto (CFG).
  • Las cadenas que estás viendo son generadas por el CFG: (en términos generales, dada una cadena inicial, puedes generar una cadena con y a cualquier lado de la cadena original, o nada, por lo que te permite generar , etc. ).0n1nS -> 0S1 | ε01010011

Si bien grep (extendido o no) tiene características que van más allá de las "expresiones regulares" mencionadas anteriormente, como referencias anteriores, no creo que ninguna de ellas lo extienda hasta ser tan poderoso como una PDA.

Se puede comprobar que S -> 0S1 | εno es regular utilizandoel lema del bombeo, pero no tengo pruebas de que las características de grep le permitan (o no) aceptar CFG. Sin embargo, el artículo de Wikipedia sobreExpresiones regularestiene esto que decir (negrita mía):

Muchas características que se encuentran en prácticamente todas las bibliotecas de expresiones regulares modernas proporcionan un poder expresivo que supera con creces los lenguajes regulares. Por ejemplo, muchas implementaciones permiten agrupar subexpresiones con paréntesis y recuperar el valor que coinciden en la misma expresión (referencias inversas). Esto significa que, entre otras cosas, un patrón puede coincidir con cadenas de palabras repetidas como "papá" o "WikiWiki", llamadas cuadrados en la teoría del lenguaje formal. El patrón de estas cuerdas es (.+)\1.

El lenguaje de los cuadrados no es regular,ni está libre de contexto, debido al lema de bombeo. Sin embargo, la coincidencia de patrones con un número ilimitado de referencias anteriores, respaldada por numerosas herramientas modernas, sigue siendo sensible al contexto. [33]

[33]: Cezar Câmpeanu y Kai Salomaa, y Sheng Yu (diciembre de 2003). "Un estudio formal de expresiones regulares prácticas". Revista internacional de fundamentos de la informática. 14 (6): 1007–1018. doi:10.1142/S012905410300214X. Teorema 3 (p.9)

Entonces, diría que es seguro decir grepque no puede coincidir por sí solo.0n1n

información relacionada