A continuación, supongamos que estamos trabajando con una máquina Turing de cinta infinita. Al explicar la noción de la complejidad del tiempo a alguien, y por qué se mide en relación con el tamaño de entrada de una instancia, me topé con la siguiente afirmación: [..] Por ejemplo, es natural...
Considere una gráfica G(V,E)G(V,E)G(V,E) . Cada borde eee tiene dos pesos AeAeA_e y BeBeB_e . Encuentre un árbol de expansión que minimice el producto (∑e∈TAe)(∑e∈TBe)(∑e∈TAe)(∑e∈TBe)\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in T}{B_e}\right) . El algoritmo debe ejecutarse en tiempo polinómico...
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...
Recientemente estoy estudiando sobre el diseño de compiladores. Llegué a conocer dos tipos de gramática, una es la gramática LL y la otra es la gramática LR. También conocemos los hechos de que cada gramática LL es LR, es decir, la gramática LL es un subconjunto adecuado de la gramática LR. El...
Estaba revisando la definición de Wikipedia de lenguaje sensible al contexto y encontré esto: Cada categoría de idiomas es un subconjunto apropiado de la categoría directamente encima de ella. Cualquier autómata y cualquier gramática en cada categoría tiene un autómata o gramática equivalente en...
Dados a,b,c,d∈Na,b,c,d∈Na,b,c,d \in \mathbb N y b,d∉{0}b,d∉{0}b,d \notin \{0\} , ab<cd⟺ad<cbab<cd⟺ad<cb \begin{eqnarray*} \frac a b < \frac c d &\iff& ad < cb \end{eqnarray*} Mis preguntas son: Dado a,b,c,da,b,c,da,b,c,d Suponiendo que podemos decidir x<y∈Zx<y∈Zx < y \in...
Esta es una pregunta del Libro del Dragón. Esta es la gramática: S→AaAb∣BbBaS→AaAb∣BbBaS \to AaAb \mid BbBa B → εA→εA→εA \to \varepsilon B→εB→εB \to \varepsilon La pregunta pregunta cómo mostrar que es LL (1) pero no SLR (1). Para demostrar que es LL (1), intenté construir su tabla de...
Escuché mucho esta pregunta de la entrevista y esperaba obtener algunas opiniones sobre cuáles podrían ser buenas respuestas: tiene un archivo grande de más de 10 GB y desea saber qué elemento se produce más, cuál es una buena manera ¿para hacer esto? Iterar y realizar un seguimiento en un mapa...
Considere una secuencia de lanzamientos de una moneda imparcial. Let denotan el valor absoluto del exceso del número de cabezas sobre las colas visto en la primera lanzamientos. Defina . Muestre que y .nnnHiHiH_iiiiH=maxiHiH=maxiHiH=\text{max}_i H_iE[Hi]=Θ(i√)E[Hi]=Θ(i)E[H_i]=\Theta ( \sqrt{i}...
¿Cuáles son las diferencias clave entre estos tres términos isomorfismo, automorfismo y homomorfismo en lenguaje simple y laico y por qué hacemos isomorfismo, automorfismo y
Estoy tratando de entender las gramáticas sensibles al contexto. Entiendo por qué a los idiomas les gusta { w w ∣ w ∈ A∗}{ww∣w∈A∗}\{ww \mid w \in A^*\} { anortesinorteCnorte∣ n ∈ N }{anbncn∣n∈N}\{a^n b^n c^n \mid n\in\mathbb{N}\} no están libres de contexto, pero me gustaría saber si un...
Se dice que la teoría de la computabilidad también se llama teoría de la recursividad. ¿Por qué se llama así? ¿Por qué la recursión tiene tanta
Primero, déjame escribir la definición de grande OOOsolo para hacer las cosas explícitas. f(n)∈O(g(n))⟺∃c,n0>0f(n)∈O(g(n))⟺∃c,n0>0f(n)\in O(g(n))\iff \exists c, n_0\gt 0 tal que0≤f(n)≤cg(n),∀n≥n00≤f(n)≤cg(n),∀n≥n00\le f(n)\le cg(n), \forall n\ge n_0 Digamos que tenemos un número finito de...
Me pregunto esto basado en varios lugares en línea que llaman a co- un problema abierto importante ... pero no puedo encontrar ninguna indicación de si esto es lo mismo que Problema ...NP=NP=\sf NP=NPNP\sf NPP=NPP=NP\sf
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...
Entonces, sé que probar si un lenguaje regular es un subconjunto del lenguaje regular S es decidible, ya que podemos convertirlos a ambos en DFA, calcular R ∩ ˉ S y luego probar si este idioma está vacío.RRRSSSR∩S¯R∩S¯R \cap \bar{S} Sin embargo, dado que esto requiere la conversión a DFA, es...
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...
Creo que entiendo cómo la deforestación consume y produce una lista al mismo tiempo (desde una función de plegado y desplegado; vea esta buena respuesta en CodeReview aquí ), pero cuando comparé eso con la entrada de wikipedia sobre la técnica que habló sobre 'eliminar árboles 'de un...
¿Alguien podría explicarme las diferencias y similitudes entre el aprendizaje automático y las identificaciones del sistema? ¿Son estos solo dos nombres de la misma cosa? En esta página , dicen: El aprendizaje automático y las comunidades de identificación del sistema se enfrentan a problemas...
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...