Preguntas sobre la teoría de las expresiones regulares, tanto en el sentido de la definición original de Kleene como de las expresiones regulares POSIX.
Estoy pensando en el siguiente problema: quiero encontrar una expresión regular que coincida con un conjunto particular de cadenas (por ejemplo, direcciones de correo electrónico válidas) y que no coincida con otras (direcciones de correo electrónico no válidas). Supongamos que por expresión...
Pregúntele incluso a alguien con experiencia en informática qué es una expresión regular, y es probable que la respuesta vaya más allá de la restricción de estar al alcance de un autómata de estado finito. Por ejemplo, la "expresión regular" /^1?$|^(11+?)\1+$/ creado por la destacada...
Es bien sabido que una expresión regular puede ser reconocida por un autómata finito no determinista de tamaño proporcional a la expresión regular, o por un FA determinista que es potencialmente exponencialmente más grande. Además, dada una cadena una expresión regular , la NFA puede probar la...
Me preguntaba si hay un algoritmo `` mejor '' (explicaré en qué sentido) comenzar desde un DFA y construir una expresión regular r tal que L ( A ) = L ( r ) , que la del libro de Hopcroft y Ullman (1979). Allí, los conjuntos R k i j se utilizan para representar conjuntos de cadenas que llevan el...
¿Por qué los lenguajes regulares (y de esas expresiones regulares) se llaman "regulares"? Hay mucha regularidad también en los idiomas sin contexto de otros tipos de idiomas. Supongo que, al principio, el adjetivo "regular" se ha utilizado para diferenciar ese tipo de idiomas de otros lenguajes...
Además de la complejidad de comunicación (determinista) de una relación , otra medida básica para la cantidad de comunicación necesaria es el número de partición de protocolo . La relación entre estas dos medidas se conoce hasta un factor constante. La monografía de Kushilevitz y Nisan (1997) daRc...
Es bien sabido que el siguiente problema es PSPACE-complete: Dada la expresión regular , ¿ ?L ( β ) = Σ ∗ββ\betaL ( β) = Σ∗L(β)=Σ∗L(\beta) = \Sigma^* ¿Qué pasa con la determinación de equivalencia a otras expresiones regulares (fijas) ?αα\alpha Dada la expresión regular , ¿ ?L ( β ) = L ( α...
La mayoría de las implementaciones modernas de expresiones regulares, como las de perl o .NET, van más allá de la definición informática clásica de REGEXes con características como mirar hacia adelante y mirar hacia atrás. ¿Estas características les permiten analizar declaraciones que no se pueden...
Me preguntaba si la especificación JSON definía un lenguaje regular. Parece bastante simple, pero no estoy seguro de cómo demostrarlo yo mismo. La razón por la que pregunto es porque me preguntaba si uno podría usar expresiones regulares para analizar JSON de manera efectiva. ¿Podría alguien con...
Hace veinte años, creé un paquete de expresiones regulares que incluía conversiones de expresiones regulares a una máquina de estados finitos (DFA) y soportaba una gran cantidad de operaciones de expresiones regulares cerradas (estrella de Kleene, concatenación, operaciones inversas, de...
La altura de estrella (generalizada) de un idioma es la anidación mínima de estrellas de Kleene requerida para representar el idioma mediante una expresión regular extendida. Recuerde que una expresión regular extendida sobre un alfabeto finito AAA satisface lo siguiente: (1) ∅,1∅,1\emptyset, 1 y...
Se sabe que minimizar el tamaño de una expresión regular es completo para PSPACE, incluso si tenemos un DFA como la especificación del lenguaje . ¿Cuáles son los resultados si el idioma es finito? Uno puede considerar este problema en dos modelos: La entrada es todas las cadenas en el idioma,...
¿Hay alguna jerarquía "agradable" conocida L0⊆L1⊆L2⊆…L0⊆L1⊆L2⊆…L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots (puede ser finita) dentro de la clase de lenguajes regulares LLL ? Por bueno aquí, las clases en cada jerarquía capturan diferente expresividad / poder / complejidad. Además, la membresía...
Inspirado por esta pregunta , tengo curiosidad por lo siguiente: ¿Cuál es la complejidad del peor caso de verificar si un DFA determinado acepta el mismo lenguaje que una expresión regular dada? ¿Se sabe esto? La esperanza sería que este problema esté en P, que exista un algoritmo polinomial...
Estoy interesado en el problema clásico INCLUSIÓN DE IDIOMAS REGULARES. Dada una expresión regular , denotamos por L ( E ) el lenguaje regular asociado a ella. (Las expresiones regulares están en un alfabeto fijo Σ , con la unión de operaciones, Kleene-star y concatenación).miEEL (...
Todos mis libros de texto usan el mismo algoritmo para producir un DFA dado un regex: primero, haga un NFA que reconozca el idioma del regex, luego, usando la construcción del subconjunto (también conocido como "powerset"), convierta el NFA en un DFA equivalente ( opcionalmente minimizando el DFA)....
Estoy tratando de elaborar una taxonomía de algoritmos para transformar expresiones regulares en autómatas para realizar algunas pruebas empíricas de sus propiedades de complejidad en dominios específicos. Soy consciente de varios de los nombres 'más grandes', por ejemplo, Thompson "Algoritmo...
Me preguntaba qué conjuntos de idiomas se generan por restricciones de expresiones regulares. Supongamos que todas las restricciones tienen un símbolo constante para cada elemento de y concatenación. Entonces se pueden formar ocho clases por la presencia o ausencia de complemento / negación,...
Estaba leyendo sobre el problema de la altura de las estrellas y noté que la familia de expresiones regulares de Eggan sigue un patrón simple que puede describirse mediante una expresión regular. Mi pregunta es: ¿hay resultados interesantes sobre expresiones regulares que describan familias de...
¿Existe un algoritmo para verificar si una expresión regular de tamaño n coincide con una cadena de tamaño m , suponiendo un alfabeto de tamaño fijo si eso importa?O ( n + m )O(norte+metro)O(n+m)nortenortenmetrometrom El algoritmo estándar de NFA es peor de los casos. Groz y col. lograr tiempo...