Preguntas sobre expresiones regulares, un formalismo para describir lenguajes regulares.
Convertir expresiones regulares en NFA (mínimo) que acepten el mismo lenguaje es fácil con algoritmos estándar, por ejemplo, el algoritmo de Thompson . Sin embargo, la otra dirección parece ser más tediosa, y a veces las expresiones resultantes son desordenadas. ¿Qué algoritmos existen para...
Como se ve en esta reciente tira de XKCD y esta reciente publicación de blogde Peter Norvig (y una historia de Slashdot con este último), "regex golf" (que podría llamarse el problema de separación de expresiones regulares) es el rompecabezas de definir la expresión regular más corta posible que...
Esta pregunta se migró de Stack Overflow porque se puede responder en Computer Science Stack Exchange. Migrado hace 7 años . Creé un simple lexer y analizador de expresiones regulares para tomar una expresión regular y generar su árbol de análisis. Crear un autómata de...
Aquí hay una conjetura para expresiones regulares: Para la expresión regular , deje que la longitudser el número de símbolos que contiene, ignorando paréntesis y operadores. Ej.| R | El | 0 ∪ 1 | = | ( 0 ∪ 1 ) ∗ | = 2RRR|R||R||R||0∪1|=|(0∪1)∗|=2|0∪1|=|(0∪1)∗|=2|0 \cup 1| = |(0 \cup 1)^*| = 2...
He buscado en la red una respuesta a esta pregunta y parece que todos saben implícitamente la respuesta, excepto yo. Presumiblemente esto se debe a que las únicas personas que se preocupan son aquellas que han recibido educación terciaria sobre el tema. Yo, por otro lado, he sido arrojado al fondo...
Como dice el título, pasé un par de horas el fin de semana pasado tratando de aclarar mi mente sobre la clase de idiomas que coinciden con las expresiones regulares compatibles con Perl, excluyendo cualquier operador coincidente que permita ejecutar código arbitrario dentro del patrón . Si no sabe...
Ajuste: expresiones regulares con referencias lenguaje unario (alfabeto de 1 símbolo) ¿Se puede resolver el siguiente problema en esta configuración: Dada una expresión regular con referencias inversas, ¿define un lenguaje regular? Por ejemplo, (aa+)\1define un lenguaje regular, mientras...
Si tengo una gramática de tipo 3, se puede representar en un autómata pushdown (sin realizar ninguna operación en la pila) para poder representar expresiones regulares utilizando lenguajes libres de contexto. Pero, ¿puedo saber si una gramática de tipo 3 es , , , etc. sin construir tablas de...
Aparentemente, los ataques ReDos explotan las características de algunas expresiones regulares (de otro modo útiles) ... esencialmente causando una explosión de posibles caminos a través del gráfico definido por la NFA. ¿Es posible evitar tales problemas escribiendo una expresión regular 'no...
Parece que las "Expresiones regulares básicas" según lo definido por POSIX.1-2008 no admiten la alternancia a|b(aunque algunas implementaciones grep reconocen la versión escapada \|). Dado que los lenguajes regulares están cerrados bajo unión por definición, ¿significa esto que POSIX BRE tiene...
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=x1…xnw=x1…xnw=x_1…x_n Regex: expresión regular. Para verificar: "Permutaciones de expresiones...
Estaba jugando el otro día en este sitio web: http://regexcrossword.com/ y me pregunté cuál era la mejor manera de resolverlo. ¿Puedes resolver el siguiente problema en tiempo polinómico o es NP-hard? Dada una cuadrícula NxM con N expresiones regulares para las columnas y M para las filas,...
Descubrí que si no entiendo la etimología detrás de un término cs / programación, generalmente significa que he perdido o malinterpretado algún concepto subyacente importante. No entiendo por qué la estrella de Kleene también se llama cierre de Kleene. ¿Está relacionado con los cierres en la...
Quiero convertir una expresión regular ingresada por el usuario en un NFA para que luego pueda ejecutar el NFA en una cadena con fines coincidentes. ¿Cuál es la máquina mínima que se puede usar para analizar las expresiones regulares? Supongo que debe ser un autómata push down porque la presencia...
El objetivo es crear DFA a partir de una expresión regular y usar "Exp. Regular> NFA> Conversión de DFA" no es una opción. ¿Cómo debería uno hacer eso? Le hice esta pregunta a nuestro profesor, pero él me dijo que podemos usar la intuición y amablemente se negó a dar ninguna explicación....
Soy nuevo en los autómatas, y ayer me dieron una breve introducción a las expresiones regulares. He leído las diversas reglas para definir una expresión regular. Pero no puedo diferenciar entre las expresiones regulares y la gramática de un idioma (no me han enseñado la gramática de las expresiones...
Pensé que todos los idiomas regulares podrían expresarse con expresiones regulares (si un idioma es regular, puede expresarse con expresiones regulares), pero me han dicho que necesita las tres operaciones regulares (concatenación, unión y estrella) para eso sostener. Por ejemplo, me han dicho que...
En el trabajo, se me ha encomendado la tarea de inferir cierta información sobre un lenguaje dinámico. Reescribo secuencias de declaraciones en letexpresiones anidadas , así: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x...
Dadas dos expresiones regulares arbitrarias, ¿existe un algoritmo "eficiente" para determinar si coinciden con el mismo conjunto de cadenas? De manera más general, ¿podemos calcular el tamaño de la intersección de los dos conjuntos de coincidencias? ¿Qué algoritmos existen para hacer esto y en...
Si entiendo correctamente, NFA tiene el mismo poder expresivo que las expresiones regulares. A menudo, leer expresiones regulares equivalentes de NFA es fácil: traduce ciclos a estrellas, uniones como alternativas, etc. Pero qué hacer en este caso: [ fuente ] Los ciclos superpuestos hacen que...