Preguntas sobre operaciones en objetos de algún tipo que resultan en objetos del mismo tipo.
Los lenguajes libres de contexto no están cerrados bajo complemento, lo sabemos. Por lo que yo entiendo, los lenguajes sin contexto que son un subconjunto de a∗b∗un∗si∗a^*b^* para algunas letras a,bun,sia,b están cerrados bajo el complemento (!?) Aquí está mi argumento. Cada lenguaje CF LLL tiene...
Esta es una pregunta de seguimiento de esta . En una pregunta anterior sobre máquinas de estado exóticas , Alex ten Brink y Raphael abordaron las capacidades computacionales de un tipo peculiar de máquina de estados: los autómatas de min-montón. Pudieron demostrar que el conjunto de idiomas...
Deje que GGG sea una gramática libre de contexto. Una serie de terminales y no terminales de GGG se dice que es una forma de frase de GGG si se puede obtener mediante la aplicación de las producciones de GGG cero o más veces al símbolo inicial de SSS . Deje SF(G)SF(G)\operatorname{SF}(G) el...
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...
¿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...
Me he encontrado con esa pregunta: "Dé ejemplos de dos idiomas regulares en los que su unión no genere un idioma regular". Esto es bastante impactante para mí porque creo que los idiomas regulares están cerrados bajo unión. Lo que significa para mí que si tomo dos idiomas regulares y los combino,...
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...
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...
Necesito saber bajo qué clase de CFL está cerrada, es decir, qué conjunto es complemento de CFL. Sé que CFL no está cerrado bajo complemento, y sé que P está cerrado bajo complemento. Dado que CFL PI puede decir que el complemento de CFL está incluido en P (¿verdad?). Todavía existe la duda de si...
El desplazamiento cíclico (también llamado rotación o conjugación ) de un lenguaje se define como . Según Wikipedia (y aquí ), los lenguajes libres de contexto se cierran bajo esta operación, con referencias a documentos de Oshiba y de Maslov. ¿Hay una prueba fácil de este hecho?{ y x ∣ x y ∈ L...
Una forma de ver las expresiones regulares es como una prueba constructiva del siguiente hecho: es posible construir los idiomas regulares comenzando con un pequeño conjunto de idiomas y combinándolos a través de un pequeño conjunto fijo de propiedades de cierre. Específicamente, si comenzamos con...
Estoy atrapado resolviendo el siguiente ejercicio: Argumenta que si tiene contexto y es regular, entonces (es decir, el cociente correcto ) no tiene contexto.R L / R = { w ∣ ∃ x ∈ RLLLRRRL / R = { w ∣ ∃ x ∈ RS tw x ∈ L }L/R={w∣∃x∈Rs.twx∈L}L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\}...
He estado leyendo algunos documentos de teoría del lenguaje formal y me he encontrado con un término que no entiendo. El documento a menudo se referirá a un conjunto que está "efectivamente cerrado bajo intersección" u otras operaciones. ¿Qué significa "efectivamente" aquí? ¿Cómo difiere esto del...
En la clase de esta semana hemos estado aprendiendo sobre las CFL y sus propiedades de cierre. He visto pruebas de unión, intersección y cumplido, pero para la reversión, mi profesor acaba de decir que está cerrado. Quería ver la prueba, así que he estado buscando durante los últimos días, pero...
He estado intentando durante bastante tiempo encontrar una construcción para poder demostrar formalmente que un PDA determinista está cerrado bajo complementación. Sin embargo, sucede que cada idea que tengo tiene algo que al final no encaja. ¿Me puedes dar una mano? El principal problema ocurre...
Dejar LLLser un lenguaje normal Es el idiomaL2={y:∃x,z s.t.|x|=|z| and xyz∈L}L2={y:∃x,z s.t.|x|=|z| and xyz∈L}L_2 = \{y : \exists x,z\ \ s.t.|x|=|z|\ and\ xyz \in L \} ¿regular? Sé que es muy similar a la pregunta aquí , pero el problema es que no es una simple subcadena de una palabra en un...
Tenemos dos idiomas: . Sabemos que es un lenguaje regular, por lo que mi pregunta es si es regular.L1,L2L1,L2L_1,L_2L1L2L1L2L_1L_2L2L1L2L1L_2L_1 Trato de encontrar una manera de demostrarlo ... No puedo suponer, por supuesto, que son regulares ... Así que busco una forma de demostrarlo....
Así que llevo unos días rascándome la cabeza sobre este problema. Dado un lenguaje y que es regular, demuestre que el lenguaje que consiste en todas las cadenas en cuya longitud es igual a alguna cadena en es un lenguaje regular.AAABBBLLLAAABBB En forma de
Tengo en unos días un examen y tengo problemas para resolver esta tarea. Dejar LLL ser un lenguaje regular sobre el alfabeto ΣΣ\Sigma. Tenemos la operacion cycle(L)={xy∣x,y∈Σ∗ and yx∈L}cycle(L)={xy∣x,y∈Σ∗ and yx∈L}\operatorname{cycle}(L) = \{ xy \mid x,y\in \Sigma^* \text{ and } yx\in L\} Y...