Prerrequisito – Problema de la máquina de Turing : Dibuje una máquina de Turing que multiplique dos números. Ejemplo: Pasos: Paso 1. Primero ignore los 0, C y vaya a la derecha y luego, si B encontró, conviértalo en C y vaya a la izquierda. Paso 2. Luego ignore los 0 y vaya a la … Continue reading «Máquina de Turing para la multiplicación»
Autómatas finitos Expresiones regulares, gramática y lenguaje . Descripción general: Sean a y b símbolos de entrada y r la expresión regular. Ahora tenemos que diseñar NFA y DFA para cada expresión regular. Diseño de autómatas finitos a partir de la expresión regular: aquí, discutiremos el diseño de autómatas finitos a partir de la expresión … Continue reading «Diseñe autómatas finitos a partir de expresiones regulares»
Requisito previo: Diseño de autómatas finitos Comprendamos la operación de productos cruzados en Deterministic Finite Automata (DFA) con la ayuda del siguiente ejemplo: Al diseñar un DFA para el conjunto de strings sobre {a, b}, de modo que la string del idioma contenga un número par de a y b, entonces el idioma deseado será … Continue reading «Operación de productos cruzados en DFA»
Requisito previo: autómatas finitos (FA) El compuesto FA es el DFA resultante que se forma después de realizar la operación (∪, ∩, -) en los DFA dados D1 y D2. D1 = (Q1, ∑, δ, q1, F1) and D2 = (Q2, ∑, δ, q2, F2) Donde, Q 1 y Q 2 : Conjunto de estados … Continue reading «Autómatas finitos compuestos (FA)»
Requisito previo: gramáticas libres de contexto , simplificación de gramáticas libres de contexto Una gramática libre de contexto (CGF) está en forma normal de Greibach (GNF) si todas las reglas de producción satisfacen una de las siguientes condiciones: Un no-terminal que genera un terminal (p. ej., X->x) Un no terminal que genera un terminal seguido … Continue reading «Conversión de la gramática libre de contexto a la forma normal de Greibach»
Ver notas de última hora sobre todos los temas aquí . Φ + R = R + Φ = R Φ * R = R * Φ = Φ ε * R = R * ε = R ε* = ε Φ* = ε ε + RR* = R*R + ε = R* (a+b)* … Continue reading «Notas de Último Minuto – Teoría de la Computación»
Problema: dibujar autómatas finitos deterministas (DFA) de una string con al menos dos 0 y al menos dos 1. Lo primero que me viene a la mente después de leer esta pregunta es que contamos el número de 1 y 0. A partir de entonces, si ambos son al menos 2, la string se acepta; … Continue reading «DFA de una string con al menos dos 0 y al menos dos 1»
Problemas decidibles Un problema es decidible si podemos construir una máquina de Turing que se detenga en una cantidad finita de tiempo para cada entrada y responda como ‘sí’ o ‘no’. Un problema decidible tiene un algoritmo para determinar la respuesta para una entrada dada. Ejemplos Equivalencia de dos idiomas regulares: dados dos idiomas regulares, … Continue reading «Indecidibilidad y Reducibilidad en TOC – Part 1»
Prerrequisito – Máquina de Turing Tarea: Tenemos que diseñar una máquina de Turing para a^ib^j donde i<j e i>0. Análisis : Aquí lo principal es notar que i<j. Significa que el conteo de ‘b’ en la string siempre es mayor que el conteo de ‘a’. Por lo tanto podemos escribir a^ib^j así – a^i b^j … Continue reading «Construya la Máquina de Turing para L = {a^ib^j | i<j, i>0}»
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 para el conjunto de strings sobre {a, b} tal que la longitud de la string |w|=2, es decir, la longitud de la string es exactamente 2. Explicación: el idioma deseado será como: … Continue reading «Diseño de autómatas finitos deterministas (Conjunto 1) – Part 1»