Problema – Implementar un reconocedor de identificadores pascales basado en un DFA que acepte strings pertenecientes a la definición del lenguaje del mismo. Aquí hay una definición regular para el conjunto de identificadores de Pascal que se definen como el conjunto de strings de letras y dígitos que comienzan con una letra. letter : A … Continue reading «DFA (Reconocedor) para identificadores Pascal válidos»
1. Complejidad computacional: Complejidad computacional, una medida de la cantidad de recursos informáticos (tiempo y espacio) que consume un algoritmo en particular cuando se ejecuta. La complejidad temporal de una máquina de Turing viene dada por la función T(n), donde T(n) = Número máximo de movimientos realizados por la TM para procesar una … Continue reading «Complejidad Computacional v/s Jerarquía de Chomsky»
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»
El teorema de Arden establece que: «Si P y Q son dos expresiones regulares sobre , y si P no contiene , entonces la siguiente ecuación en R dada por R = Q + RP tiene una solución única, es decir, R = QP*». Eso significa que, siempre que obtengamos una ecuación en la forma … Continue reading «Teorema de Arden en Teoría de la Computación – Part 1»
La máquina de Turing fue inventada por Alan Turing en 1936 y se utiliza para aceptar lenguajes enumerables recursivos (generados por gramática de tipo 0). Una máquina de turing consta de una cinta de longitud infinita en la que se pueden realizar operaciones de lectura y escritura. La cinta consta de celdas infinitas en las … Continue reading «Máquina de Turing en TOC – Part 1»
Requisito previo: 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 – Part 1»
Funciones recursivas totales: una función recursiva se llama función recursiva total si está definida para todos sus argumentos . Sea f (a1, a2, … an) una función definida en la función g (b1, b2, … bn). Entonces f es una función total si cada elemento de f se asigna a algún elemento único de la … Continue reading «Funciones recursivas totales y funciones recursivas parciales en autómatas»
Prerrequisito: Autómatas finitos , Expresiones regulares, gramática y lenguaje , Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 5) 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: Lenguaje regular, L1 = a(a+b)* El lenguaje del RE dado es, {aaa, aba, baa, … Continue reading «Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 6)»
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 ≥ 1} Las strings de lenguaje dado serán: L = {abbc, abbbcc, abbbcc, aabbbbcc, ……} En cada una de las strings, la suma total del número de … Continue reading «NPDA por aceptar el lenguaje L = {amb(m+n)cn | m, n ≥ 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 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)»