Categoría: Theory of Computation & Automata

Requisito previo: Introducción a los autómatas finitos , Diseño del problema de autómatas finitos 1: Construir DFA, que acepta un conjunto de todas las strings sobre {0, 1} que se interpreta como un número binario divisible por 2. Explicación: Considere las siguientes entradas, {0, 01, 10, 11, 100, 101, 110……..} El diagrama de transición de … Continue reading «Construir DFA que interpretado como un número binario es divisible por 2, 3, 4»

Prerrequisito: Autómatas finitos , Expresiones regulares, gramática y lenguaje , Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 2) En el siguiente artículo, veremos algunos diseños de autómatas finitos a partir de la expresión regular dada. Expresión regular 1: ‘ab*’ (‘a’ seguido de cualquier número de ‘b’). El lenguaje del RE dado es, … Continue reading «Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 3) – Part 1»

Un autómata pushdown (PDA) es como un autómata finito no determinista (NFA) épsilon con una pila infinita. PDA es una forma de implementar lenguajes libres de contexto. Por lo tanto, es importante aprender a dibujar PDA. Aquí, tomemos el ejemplo de un palíndromo de longitud impar: Que-1: Construya un PDA para el lenguaje L = … Continue reading «Construir autómatas pushdown para palíndromos de todas las longitudes»

Prerrequisito – Máquina de Turing Se dice que un problema es decidible si siempre podemos construir un algoritmo correspondiente que pueda responder el problema correctamente. Podemos entender intuitivamente los problemas decidibles considerando un ejemplo simple. Supongamos que se nos pide que calculemos todos los números primos en el rango de 1000 a 2000. Para encontrar … Continue reading «Problemas decidibles e indecidibles en Teoría de la Computación»

Requisito previo: máquina de Turing , complemento de 1 y 2 de un número binario   Problema-1: Dibuja una máquina de Turing para encontrar el complemento a 1 de un número binario.  El complemento a 1 de un número binario es otro número binario obtenido alternando todos los bits en él, es decir, transformando el bit … Continue reading «Máquina de Turing para complemento a 1 y complemento a 2»