Prerrequisito: diseñar autómatas finitos . Problema: construir una máquina DFA sobre el alfabeto de entrada = {0, 1}, que acepte: Número impar de 0 o número par de 1 Número impar de 0 y número par de 1 Ya sea un número impar de 0 o un número par de 1, pero no los dos … Continue reading «Máquinas DFA que aceptan un número impar de 0 o un número par de 1»
Requisito previo: máquina de Turing Problema: Dibuja una máquina de turing que compare dos números. Uso del formato unario para representar el número. Por ejemplo, 4 está representado por 4 = 1 1 1 1 or 0 0 0 0 Usemos uno para la representación. Ejemplo: Acercarse: Comparar dos números comparando el número de ‘1’. … Continue reading «Máquina de Turing como comparador»
En 1936, Alonzo Church creó un método denominado cálculo lambda en el que los números de Iglesia están bien definidos, es decir, la codificación de números naturales. También en 1936, Alan Turing creó las máquinas de Turing (anteriormente llamadas modelo teórico para máquinas), que se utilizan para manipular los símbolos de cuerdas con la ayuda … Continue reading «Tesis de Church para la máquina de Turing»
Requisito previo: diseño de autómatas finitos Comprendamos el proceso de unión en autómatas finitos deterministas (DFA) con la ayuda del siguiente ejemplo. Diseñar un DFA para el conjunto de strings sobre {a, b} de modo que la string del idioma comience y termine con diferentes símbolos. Allí se formarán dos idiomas deseados: L1 = {ab, … Continue reading «Proceso de unión en DFA – Part 1»
Requisito previo: diseño de autómatas finitos En este artículo, veremos algunos diseños de autómatas finitos deterministas (DFA). Problema-1: Construcción de un DFA mínimo que acepta un conjunto de strings sobre {a} en el que {a n | n≥0, n≠2 es decir, ‘n’ debe ser mayor que 0 y no igual a 2}. Explicación: El idioma deseado … Continue reading «Diseño de autómatas finitos deterministas (Conjunto 10)»
Los autómatas finitos deterministas (DFA) se definen como un concepto matemático abstracto que se utiliza para resolver varios problemas específicos en diferentes software y hardware. En este tipo de problemas tenemos algunos parámetros dados según los cuales debemos diseñar DFA. En este artículo, se dan dos instrucciones: DFA debe tener uno de DFA debe tener … Continue reading «DFA para exactamente uno de a y al menos uno de b»
En este artículo, discutiremos cómo puede resolver el problema, y también verá cómo puede diseñar problemas relacionados con DFA en código LEX para identificar e imprimir constantes e identificadores enteros y flotantes. Discutámoslo uno por uno. Descripción general del problema: diseñe un DFA en código LEX para identificar e imprimir constantes e identificadores enteros y … Continue reading «Código LEX para identificar e imprimir constantes enteras y flotantes e identificador»
Antes de leer este artículo, le recomendamos que primero lea sobre Pushdown Automata y Context Free Languages . Supongamos que tenemos una gramática G libre de contexto con reglas de producción: S -> aSb | b Sa | SS | e Derivación más a la izquierda (LMD) y árbol de derivación: La derivación más a … Continue reading «Ambigüedad en gramática libre de contexto y lenguajes libres de contexto – Part 1»
Prerrequisito: indecidibilidad , problemas decidibles e indecidibles La identificación de lenguajes (o problemas*) como decidibles, indecidibles o parcialmente decidibles es una pregunta muy común en GATE. Con el conocimiento correcto y una amplia experiencia, esta pregunta se vuelve muy fácil de resolver. Una lengua es indecidible si no es decidible. Un lenguaje indecidible tal vez … Continue reading «Tabla de Decidibilidad en Teoría de la Computación»
La máquina de Turing fue descrita por primera vez por Alan Turing en el año 1936. Fue inventada principalmente para investigar la computabilidad de un problema determinado. Acepta gramática de tipo 0, que es un lenguaje recursivamente enumerable. La máquina de Turing tiene una cinta de longitud infinita donde podemos realizar operaciones de lectura y … Continue reading «Diferencia entre la máquina de Turing y la máquina de Turing Universal»