Requisito previo: diseño de autómatas finitos En este artículo, veremos un diseño de autómatas finitos deterministas (DFA). Problema: construcción de un DFA mínimo que acepta un conjunto de strings sobre {a, b} en el que Número de a(w) mod 2 = 0 o Número de b(w) mod 2 = 0, es decir, el número de … Continue reading «Diseño de autómatas finitos deterministas (Conjunto 11)»
Requisito previo: Introducción a los autómatas finitos , Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 1) ∈-NFA es similar a NFA pero tiene una diferencia menor por movimiento épsilon. Este autómata reemplaza la función de transición por la que permite que la string vacía ∈ como posible entrada. Las transiciones que no … Continue reading «Expresión regular a ∈-NFA»
En este artículo, analizaremos el DFA en código LEX que acepta una string que contiene el penúltimo elemento ‘a’ sobre el alfabeto de entrada {a, b} con la ayuda de un ejemplo. Discutámoslo uno a uno. Requisito previo: diseño de autómatas finitos Descripción general del problema: diseñe un DFA en código LEX que acepte una … Continue reading «Código LEX que acepta una string que contiene el tercer último elemento ‘a’ sobre el alfabeto de entrada {a, b}»
Prerrequisito – Máquina de Turing El lenguaje L = {a i b j c k | i < j < k o i > j > k} es lo mismo que la unión de dos lenguas L1={a i b j c k | yo < j < k } y L2={a yo segundo j c … Continue reading «Construya una máquina de Turing para L = {aibjck | yo < j < k o yo > j > k}»
Ya conocemos Finite Automata que se puede usar para aceptar lenguajes regulares y Pushdown Automata que se pueden usar para reconocer Context Free Languages. Queue Automata (QDA) es un autómata no determinista que es similar a Pushdown Automata pero tiene una cola en lugar de una pila que ayuda a Queue automata a reconocer idiomas … Continue reading «Introducción a los autómatas de cola»
S , t Autómatas finitos deterministas (DFA) L = {a N b M | N ≥ 0, M ≥ 0, N+M ≥ 1} L la ocurrencia L “Aceptado” “No aceptado” Ejemplos Entrada: S = “aabbb” Salida: Aceptada Explicación: Todas las ‘a’ vienen antes de las ‘b’. Entrada: S = “ba” Salida: No aceptada Explicación: ‘b’ … Continue reading «Programa para construir un DFA que acepta el idioma que tiene todo ‘a’ antes de todo ‘b’»
Requisito previo: máquina de Turing , máquina de Turing para sustracción | Conjunto 1 Un número se representa en formato binario en diferentes autómatas finitos como 5 se representa como (101) pero en caso de resta se sigue el formato unario de la Máquina de Turing. En formato unario, un número se representa ya sea … Continue reading «Máquina de Turing para sustracción | conjunto 2»
Hay dos lemas de bombeo, que se definen para 1. Lenguajes regulares y 2. Contexto: lenguajes libres Lema de bombeo para lenguajes regulares Para cualquier lenguaje regular L, existe un entero n, tal que para todo x ∈ L con |x| ≥ n, existe u, v, w ∈ Σ∗, tal que x = uvw, y … Continue reading «Lema de bombeo en la teoría de la computación – Part 1»
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 – Part 1»
Problemas computables: está familiarizado con muchos problemas (o funciones) que son computables (o decidibles), lo que significa que existe algún algoritmo que calcula una respuesta (o salida) para cualquier instancia del problema (o para cualquier entrada a la función) en un número finito de pasos simples. Un ejemplo simple es la operación de incremento de … Continue reading «Problemas computables y no computables en TOC – Part 1»