Según la jerarquía de Chomsky , la gramática se divide en 4 tipos de la siguiente manera: El tipo 0 se conoce como gramática sin restricciones. El tipo 1 se conoce como gramática sensible al contexto. El tipo 2 se conoce como una gramática libre de contexto. Tipo 3 Gramática Regular. Tipo 0: Gramática sin … Continue reading «Jerarquía de Chomsky en teoría de la computación»
Requisito previo: problema de cobertura de vértices , problema de NP-completitud : dado un gráfico G (V, E) y un número entero positivo k, el problema es encontrar si hay un subconjunto V ‘de vértices de tamaño como máximo k, tal que cada borde en el gráfico está conectado a algún vértice en V’. Explicación: … Continue reading «Prueba de que la cobertura de vértices es NP completa»
Requisito previo: introducción a los autómatas finitos Todos los lenguajes de programación se pueden representar como autómatas finitos. C, Paskal, Haskell, C++, todos tienen una estructura específica, gramática, que se puede representar mediante un gráfico simple. La mayoría de los gráficos son NFA o DFA. Pero NFA y DFA determinan el grupo de idiomas más … Continue reading «Gráficos L y lo que representan en TOC – Part 1»
Problema: Construya un autómata finito determinista (DFA) para aceptar el lenguaje L = {w | victoria; {a,b}* y Na(w) mod 3 = Nb (w) mod 3}. Idioma L={w | Na(w) = Nb(w)mod 3} lo que significa que todas las strings contienen un módulo de conteo de a igual al módulo de conteo de b por … Continue reading «Construya un DFA que acepte el lenguaje L = {w | w ∈ {a,b}* y Na(w) módulo 3 = Nb (w) módulo 3}»
Conjunto contable es un conjunto que tiene cardinalidad igual a la de algún subconjunto de N el conjunto de números naturales . Un conjunto numerable es el que es enumerable. La cardinalidad de un conjunto contable puede ser un número finito. Por ejemplo, B: {1, 5, 4}, |B| = 3, en este caso se denomina … Continue reading «Determinación de la contabilidad en TOC»
Prerrequisito – Máquina de Turing En lenguaje dado L = {a i b j c k | i>j>k; k ≥ 1}, cada string de ‘a’, ‘b’ y ‘c’ tiene cierto número de a, luego cierto número de b y luego cierto número de c. La condición es que el conteo de los 3er símbolos debe … Continue reading «Construya una máquina de Turing para L = {aibjck | i>j>k; k ≥ 1}»
Prerrequisito: expresiones regulares, gramática regular y lenguajes regulares , lema de bombeo Existe un teorema bien establecido para identificar si un idioma es regular o no, basado en el principio del casillero, llamado lema de bombeo . Pero el lema de bombeo es una prueba de negatividad, es decir, si un idioma no satisface el … Continue reading «Cómo identificar si una lengua es regular o no»
La definición de gramáticas libres de contexto (CFGs) nos permite desarrollar una amplia variedad de gramáticas. La mayoría de las veces, algunas de las producciones de CFG no son útiles y son redundantes. Esto sucede porque la definición de CFG no nos restringe de hacer estas producciones redundantes. Al simplificar los CFG, eliminamos todas estas … Continue reading «Simplificación de gramáticas libres de contexto»
Requisito previo: autómatas pushdown , aceptación de autómatas pushdown por estado final Problema: diseñar un PDA no determinista para aceptar el lenguaje L = { | m + n = p + q : m, n, p, q>=1}, es decir, L = {abcd, abbcdd, abbccd, abbbccdd, ……} En cada string, el número total de ‘a’ … Continue reading «NPDA por aceptar el lenguaje L = {am bn cp dq | m+n=p+q; m,n,p,q>=1}»
Requisito previo: diseñar un autómata finito Entendamos la intersección de dos DFA con un ejemplo. Diseñar un DFA para el conjunto de strings sobre {0, 1} de modo que termine en 01 y tenga números pares 0f 1. Allí se formarán dos idiomas deseados: L1= {01, 001, 101, 0101, 1001, 1101, ….} L2= {11, 011, 101, 110, … Continue reading «Proceso de intersección de dos DFA»