Por lo general, veo que en la representación semántica operacional estructural para el ciclo while, el estado del programa no cambia: (whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(while \> B \> do \>S, \sigma) \rightarrow (if \>B \> then \>S; (while...
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 estado: los autómatas de min-montón. Pudieron demostrar que el conjunto de idiomas...
Quiero contar el número de cadenas sobre un alfabeto finito , que no contiene repeticiones, y con eso me refiero a cualquier subcadena de ,, no hay una copia disjunta de en . Por ejemplo, deje . Entonces es una de las cadenas que quiero contar, ya que para la subcadena , no hay copias disjuntas....
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...
Es el idioma L = { a , b}∗∖ { (unanortesinorte)norte∣ n ≥ 1 }L={una,si}∗∖{(unanortesinorte)norte∣norte≥1}L = \{a,b\}^* \setminus \{(a^nb^n)^n\mid n \geq1 \} sin contexto? Creo que la respuesta es que no es una CFL, pero no puedo probarlo con el lema de Ogden o el lema de...
Estoy a punto de implementar un lenguaje de dominio específico para la representación de convenciones de aprendizaje social. Parte de la implementación es una descripción formal de un lenguaje: su 'cálculo', símbolos y expresiones lógicas. Mi enfoque sería describir el lenguaje describiendo su...
Estoy tratando de enseñarme la teoría de la computabilidad con un libro de texto. Según mi libro, una funciónFff sobre un alfabeto A = { a , b , c , d, e , f, g, h , i , j , k , l , m , n , o , p , q, r , s , t , u , v , w , x , y, z}A={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}A=\{a, b,...
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
¿Cómo demuestro que el problema de decidir si un PDA acepta alguna cadena de la forma es indecidible?{w!w∣w∈{0,1}∗}{w!w∣w∈{0,1}∗}\{ w!w \mid w \in \{ 0, 1 \}^*\} He tratado de reducir este problema a otro indecidible, como si dos gramáticas libres de contexto aceptan el mismo lenguaje. Sin...
Tengo dos preguntas: Considero que el siguiente idioma En otras palabras, no es palíndromo con una longitud uniforme. Probé que este lenguaje NO es regular al demostrar que su complemento no es regular. Mi pregunta es cómo probarlo usando el lema de bombeo sin usar el
Es el idioma L={0n1m∣n and m are co-prime}L={0n1m∣n and m are co-prime} L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\} sin contexto? Supongo que no está libre de contexto porque parece demasiado complicado para que un PDA decida si 2 números son primos o no. Traté de usar el lema de...
Estoy tratando de entender (intuitivamente) los dos términos "capacidad de decisión" y "capacidad de verificación". He realizado una cantidad razonable de búsqueda y revisión de los diversos textos que puedo tener en mis manos. Sin embargo, su comprensión intuitiva parece escapar de mí,...
Considere el siguiente problema del universo . El problema del universo. Dado un conjunto finitoΣΣ\Sigma para una clase de idiomas y un autómata que acepta el idioma LLL, decidir si L=Σ∗L=Σ∗L=\Sigma^*. En [1], se afirma y prueba que el problema del universo es indecidible para una clase...
Estas diapositivas de la conferencia bosquejan una prueba de queL = {unanortesinorte∣ n ≥ 0 } ∪ {unanortesi2 n| N ≥ 0 }L={unanortesinorte∣norte≥0 0}∪{unanortesi2norte∣norte≥0 0}L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \} no puede ser aceptado por ningún autómata determinista...
Defina la equivalencia de Nerode sobre un idioma como iff para cada .L⊆Σ∗L⊆Σ∗L \subseteq \Sigma^{*}u∼Lvu∼Lvu \sim_L vuw∈L⇔vw∈Luw∈L⇔vw∈Luw \in L \Leftrightarrow vw \in Lw∈Σ∗w∈Σ∗w \in \Sigma^{*} La equivalencia de Nerode tiene finitamente muchas clases de equivalencia precisamente cuando puede ser...
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...
Como he estudiado, decidir la regularidad de los lenguajes libres de contexto es indecidible. Sin embargo, podemos probar la regularidad utilizando el teorema de Myhill-Nerode que proporciona una condición necesaria y suficiente. Entonces el problema debería ser decidible. ¿Dónde está mi...
Deje , donde y para todo .L={an∣n≥0}L={an∣n≥0}L = \{a^n \mid n \ge 0\}a0=ϵa0=ϵa^0 = \epsilonan=an−1aan=an−1aa^n = a^{n-1}an≥1n≥1n \ge 1 Por lo tanto, consiste en secuencias de de todas las longitudes, incluida una secuencia de longitud . Deje ser cualquier subconjunto infinito de . Necesito...
Dejar METROMETROM ser un NFA acíclico. Ya que METROMETROM es acíclico L ( M)L(METRO)L(M) es finito Podemos calcular El | L(M) |El |L(METRO)El ||L(M)| en tiempo polinomial? Si no, ¿podemos aproximarlo? Tenga en cuenta que el número de palabras no es el mismo que el número de rutas de...
Según este gráfico , los DCFL se cierran por reversión. Sin embargo, no estoy convencido de que la prueba intuitiva (que invierte las flechas de la máquina de estados finitos de control y cambie los empujes y estallidos) para esto parece depender del no determinismo en la elección de la transición...