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 pensando en gramáticas para lenguajes sensibles a la indendación y parece que las gramáticas CF funcionarían si se combinaran con parámetros. Como ejemplo, considere este fragmento para la gramática simplificada de Python en formato ANTLR: // on top-level the statements have empty...
Hay muchos idiomas populares. Pero, los informáticos nos dicen que para comprender el comportamiento de los programas en esos lenguajes definitivamente y sin ambigüedades argumentan sobre el comportamiento del programa (por ejemplo, demostrar su identidad), necesitamos traducirlos a otro lenguaje...
Mientras realizaba la tarea actual para mis cursos formales de idiomas y autómatas, me quedé atascado en ejercicios que involucran idiomas unarios (espero que sea el término correcto), es decir, idiomas que se basan en una sola letra. Sin embargo, no quiero preguntar sobre los ejercicios...
Estoy buscando un algoritmo eficiente para el siguiente problema o una prueba de dureza NP. Sea ΣΣ\Sigma un conjunto y A ⊆ P ( Σ )A⊆P(Σ)A\subseteq\mathcal{P}(\Sigma) un conjunto de subconjuntos de ΣΣ\Sigma . Encuentre una secuencia w ∈ Σ ∗w∈Σ∗w\in \Sigma^* de menor longitud tal que para cada L ∈...
Sé que hay lenguajes no regulares, por lo que es regular, pero todos los ejemplos que puedo encontrar son sensibles al contexto pero no están libres de contexto.L∗L∗L^* En caso de que no haya ninguno, ¿cómo lo
Estoy estudiando lenguajes formales y sistemas de bases de producción (sistemas de bases de reglas) y estoy un poco confundido acerca de por qué estas dos palabras "producción" y "regla" significan lo mismo en tantos contextos en informática. En inglés no parecen significar lo mismo. No soy...
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...
LLL es un lenguaje regular sobre el alfabeto . El cociente izquierdo de respecto a w \ in \ Sigma ^ * es el lenguaje w ^ {- 1} L: = \ {v \ mid wv \ en L \}Σ={a,b}Σ={a,b}\Sigma = \{a,b\}LLLw∈Σ∗w∈Σ∗w \in \Sigma^*w−1L:={v∣wv∈L}w−1L:={v∣wv∈L}w^{-1} L := \{v \mid wv \in L\} ¿Cómo puedo probar que...
Realmente me encantaría tu ayuda con lo siguiente: Para cualquier fijo L2L2L_2, necesito decidir si hay un cierre bajo los siguientes operadores: Ar(L)={x∣∃y∈L2:xy∈L}Ar(L)={x∣∃y∈L2:xy∈L}A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\} Al(L)={x∣∃y∈L:xy∈L2}Al(L)={x∣∃y∈L:xy∈L2}A_l(L)=\{x \mid \exists...
Encontré esta figura que muestra que los lenguajes libres de contexto y regulares son subconjuntos (adecuados) de problemas eficientes (supuestamente ). Entiendo perfectamente que los problemas eficientes son un subconjunto de todos los problemas decidibles porque podemos resolverlos, pero podría...
¿Existen idiomas indecidibles tales que su lenguaje de unión / intersección / concatenado sea decidible? ¿Cuál es la interpretación física de tal ejemplo porque, en general, los lenguajes indecidibles no están cerrados bajo estas operaciones? ¿Qué podemos decir sobre el cierre de Kleene? ¿Tenemos...
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...
Entiendo que las gramáticas libres de contexto pueden usarse para representar lenguajes libres de contexto. Puede tener ambigüedades. También tenemos formas normales como Chomsky y Greibach . No pude entender la necesidad de eso. ¿Por qué son importantes en la teoría de los idiomas? Todos los...
Digamos, L⊆{0}∗L⊆{0}∗L \subseteq \{0\}^* . Entonces, ¿cómo podemos demostrar que L∗L∗L^* es regular? Si LLL es regular, entonces, por supuesto, L∗L∗L^* también es regular. Si LLL es finito, entonces es regular y nuevamente L∗L∗L^* es regular. También he notado que, para L={0p∣p is a...
Si es regular, ¿se deduce que es regular? AA2A2A^2AAA Mi intento de una prueba: Sí, por contradicción, suponga que no es regular. A continuación, .A 2 = A ⋅ AAAAA2=A⋅AA2=A⋅AA^2 = A \cdot A Dado que la concatenación de dos idiomas no regulares no es regular, no puede ser regular. Esto...
Me pregunto, ¿cuál es la complejidad temporal de determinar el vacío para los DFA de 2 vías? Es decir, autómatas finitos que pueden moverse hacia atrás en su cinta de entrada de solo lectura. Según Wikipedia, son equivalentes a los DFA, aunque el DFA equivalente podría ser exponencialmente más...
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...
Sea regular, L 1 ∩ L 2 regular, L 2 no regular. Demuestre que L 1 ∪ L 2 no es regular o dé un contraejemplo.L1L1L_1L1∩ L2L1∩L2L_1 \cap L_2L2L2L_2L1∪ L2L1∪L2L_1 \cup L_2 Intenté esto: Mira . Este es regular. Puedo construir un autómata finito para esto: L 1 es regular, L 2 ∩ L 1 es regular, así...
Quiero demostrar que el complemento de no es regular usando las propiedades de cierre.{0n1n∣n≥0}{0n1n∣n≥0}\{0^n1^n \mid n \geq{} 0\} Entiendo que el lema de bombeo se puede usar para demostrar que no es un lenguaje normal. También entiendo que los idiomas regulares están cerrados bajo la operación...