Propiedades necesarias de las lenguas formales en ciertas clases que se basan en el cierre frente a la repetición de ciertas palabras secundarias. Asegúrese de que su pregunta no esté cubierta aplicando las técnicas en https://cs.stackexchange.com/q/1031/755.
¿El siguiente contexto de lenguaje es gratuito? L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} Como señaló sdcvvc, una palabra en este lenguaje también se puede...
Wikipedia tiene la siguiente definición del lema de bombeo para idiomas regulares ... Deje que sea un lenguaje regular. Entonces existe un número entero ≥ 1 que depende solo de modo que cada cadena en de longitud al menos ( se llama "longitud de bombeo") se puede escribir como = (es decir, se...
Estoy tratando de usar el lema de bombeo para demostrar que no es regular.L={(01)m2m∣m≥0}L={(01)m2m∣m≥0}L = \{(01)^m 2^m \mid m \ge0\} Esto es lo que tengo hasta ahora: suponga que es regular y deje que p sea la longitud de bombeo, entonces w = ( 01 ) p 2 p . Considere cualquier descomposición...
Entonces, básicamente, L satisface las condiciones del lema de bombeo para los CFL pero no es un CFL (eso es posible de acuerdo con la definición del
Me preguntaba cuándo los idiomas que contenían el mismo número de instancias de dos subcadenas serían regulares. Sé que el idioma que contiene el mismo número de 1s y 0s no es regular, pero es un lenguaje como , donde L = { w ∣ número de instancias de la subcadena "001" es igual al número de...
Tengo el siguiente idioma { 0yo1j2k∣ 0 ≤ i ≤ j ≤ k }{0i1j2k∣0≤i≤j≤k}\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\} Estoy tratando de determinar en qué clase de idioma Chomsky encaja. Puedo ver cómo se podría hacer usando una gramática sensible al contexto, así que sé que al menos es sensible...
El lema de bombeo para los idiomas regulares se puede usar para demostrar que ciertos idiomas no son regulares, y el lema de bombeo para los idiomas sin contexto (junto con el lema de Ogden) se puede usar para demostrar que ciertos idiomas no están libres de contexto. ¿Existe un lema de bombeo...
Describa un idioma normal que no pueda ser aceptado por ningún DFA que tenga solo tres estados. No estoy realmente seguro de por dónde empezar con esto y me preguntaba si alguien podría darme algunos consejos o sugerencias. Entiendo que el lema de bombeo se puede usar para probar que un idioma...
Dado un lenguaje , ¿cómo puedo decir directamente, sin mirar las reglas de producción, que este lenguaje no es regular?L = { anortesinorteCnorte}L={anbncn} L= \{a^n b^n c^n\} Podría usar el lema de bombeo, pero algunos chicos dicen simplemente mirando la gramática que este no es uno normal. ¿Como...
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...
Muestra esa L = {unanorte2El | n≥0}L={unanorte2El |norte≥0 0}L=\{a^{n^2} | n \geq 0\} no es regular Hola chicos. Estoy tomando una clase de CS y estas cosas son realmente nuevas para mí, así que tengan paciencia conmigo. Traté de mirar si obtengo alguna contradicción al usar el lema de bombeo...
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...
Se sabe que existe una propiedad de "bombeo" (las palabras de cierta longitud implican la existencia de bucles en el mecanismo de definición del lenguaje) para los lenguajes regulares y libres de contexto y algunos más (generalmente utilizados para refutar la pertenencia de un idioma a una...