Preguntas sobre los idiomas formales que pueden describirse mediante expresiones regulares (en el sentido de Kleene) o, de manera equivalente, los idiomas que pueden ser aceptados por autómatas finitos.
En el prefacio de sus libros muy influyentes Automata, Languages and Machines (Volúmenes A, B), Samuel Eilenberg prometió tentadoramente que los Volúmenes C y D se ocupan de "una jerarquía (llamada la jerarquía racional) de los fenómenos no racionales ... utilizando relaciones racionales como una...
¿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...
Definimos un lenguaje de árbol regular como en el libro TATA : es el conjunto de árboles aceptado por un autómata de árbol finito no determinista (Capítulo 1) o, de manera equivalente, el conjunto de árboles generado por una gramática de árbol regular (Capítulo 2). Ambos formalismos se parecen...
Dado un lenguaje regular (NFA, DFA, gramática o expresión regular), ¿cómo se puede contar el número de palabras aceptadas en un idioma determinado? Tanto "con exactamente n letras" como "con como máximo n letras" son de interés. Margareta Ackerman tiene dos documentos sobre el tema relacionado de...
Fijo un lenguaje regular LLL en un alfabeto ΣΣ\Sigma , y considero que el siguiente problema al que llamo programación carta de LLL . Informalmente, la entrada me da nnn letras y un intervalo para cada letra (es decir, una posición mínima y máxima), y mi objetivo es colocar cada letra en su...
Deje que sean dos lenguajes regulares dados por NFA M 1 , M 2 como entrada.L1, L2L1,L2L_1,L_2METRO1, M2M1,M2M_1,M_2 Supongamos que nos gustaría verificar si . Esto puede hacerse claramente mediante un algoritmo cuadrático que computa el autómata del producto de M 1 , M 2 , pero me preguntaba si se...
Me di cuenta de que los idiomas regulares sobre el alfabeto pueden considerarse naturalmente como un poset, y de hecho una red. Además, la concatenación junto con el lenguaje vacío ϵ define una estructura monoidal estricta en esta categoría que es distributiva sobre las uniones (no estoy seguro...
Defina la siguiente clase de idiomas "circulares" sobre un alfabeto finito Sigma. En realidad, el nombre ya existe para denotar una cosa diferente que parece, utilizada en el campo de la computación de ADN. AFAICT, esa es una clase diferente de idiomas. Un lenguaje L es circular si todas las...
Dadas las expresiones regulares , ¿existen límites no triviales en el tamaño de la gramática libre de contexto más pequeña para ?R 1R1, ... , RnorteR1,…,RnR_1, \dots, R_nR1∩ ⋯ ∩ RnorteR1∩⋯∩RnorteR_1 \cap \cdots \cap
Deje que sea la clase de todos los idiomas regulares.R E GREG\mathsf{REG} Se conoce y \ mathsf {REG} \ not \ subset \ mathsf {AC} ^ 0 . Pero, ¿hay alguna caracterización de idiomas en \ mathsf {AC} ^ 0 \ cap \ mathsf {REG} ?A C0 0⊄ R E GAC0⊄REG\mathsf{AC}^0 \not\subset \mathsf{REG}A C 0 ∩ R E GR...
La pregunta es simple y directa: para un fijo , ¿cuántos idiomas (diferentes) son aceptados por un DFA de tamaño (es decir, estados)? Declararé formalmente esto:nortennnortennnortenn Defina un DFA como , donde todo está como de costumbre y es una función (posiblemente parcial). Necesitamos...
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...
¿Es posible probar algorítmicamente si un número computable es racional o entero? En otras palabras, ¿sería posible que una biblioteca que implementa números computables proporcione las funciones isIntegero isRational? Supongo que no es posible, y que esto está relacionado de alguna manera con el...
Considere el lenguaje consiste en todas las cadenas -letter sobre modo que no haya dos letras iguales: k ΣLk−distinctLk−distinctL_{k-distinct}kkkΣΣ\Sigma Lk−distinct:={w=σ1σ2...σk∣∀i∈[k]:σi∈Σ and ∀j≠i:σj≠σi}Lk−distinct:={w=σ1σ2...σk∣∀i∈[k]:σi∈Σ and ∀j≠i:σj≠σi} L_{k-distinct} :=\{w =...
Contexto: relaciones entre lógica y autómatas El teorema de Büchi establece que la lógica de segundo orden monádico sobre cadenas (MSO) captura la clase de lenguajes regulares. La prueba muestra que en realidad existencial MSO ( o EMSO ) sobre cadenas es suficiente para capturar los lenguajes...
En la teoría de los autómatas (autómatas finitos, autómatas pushdown, ...) y en la complejidad, existe una noción de "ambigüedad". Un autómata es ambiguo si hay una palabra www con al menos dos ejecuciones de aceptación distintas. Una máquina es kkk ambigua si por cada palabra www aceptada por la...
Decimos que NFA MMM es constantemente ambiguo si existe k∈Nk∈Nk\in \mathbb{N} tal que cualquier palabra w∈Σ∗w∈Σ∗w\in \Sigma^* sea aceptada por 000 o (exactamente) caminos.kkk Si el autómata es constantemente ambiguo para , entonces se llama FA inequívoca (UFA).k = 1 MMMMk=1k=1k=1MMM Deje que...
Los autómatas finitos no ambiguos (UFA) son un tipo especial de autómatas finitos no deterministas (NFA). Un NFA se llama inequívoco si cada palabra tiene como máximo una ruta de aceptación.w ∈ Σ∗w∈Σ∗w\in \Sigma^* Esto significa .D FA ⊂ UFA ⊂ NFUNreFUN⊂UFUN⊂norteFUNDFA\subset UFA\subset...
Sería bueno recopilar una lista de condiciones que impliquen que un lenguaje L sin contexto es regular, es decir, condiciones de la forma: "si un CFG / PDA dado tiene la propiedad P, entonces sus idiomas son regulares" La propiedad P no tiene que caracterizar los CFG que generan lenguajes...
Estoy leyendo " Concatenación de idiomas regulares y complejidad descriptiva " de Galina Jiraskova, 2009 sobre la complejidad del estado resultante de la concatenación de dos idiomas regulares (por Galina Jiraskova), pero no puedo entender cuáles serían las implicaciones prácticas de la complejidad...