Prerrequisito: Introducción a los autómatas finitos En este artículo, veremos algunos diseños de autómatas finitos no deterministas (NFA). Problema-1: Construcción de un NFA mínimo que acepta un conjunto de strings sobre {a, b} en el que cada string del lenguaje comienza con ‘ab’. Explicación: El idioma deseado será como: L1 = {ab, abba, abaa, ………..} Aquí, … Continue reading «Diseño de autómatas finitos no deterministas (Conjunto 3)»
Prerrequisito: Máquinas Mealy y Moore , Diferencia entre la máquina Mealy y la máquina Moore Problema: Construcción de las máquinas que toman el conjunto de todas las strings sobre {a, b} como entrada y cuentan el número de substrings ‘ab’ Suponga, Ε = {a, b} and Δ = {0, 1} donde Ε y Δ son … Continue reading «Máquinas de Moore y Mealy para contar el número de substrings ‘ab’»
Requisito previo: introducción de autómatas finitos , DFA de una string en la que el segundo símbolo de RHS es ‘a’ Problema: dibujar autómatas finitos deterministas (DFA) del lenguaje que contiene el conjunto de todas las strings sobre {a, b} en el que el tercer símbolo de RHS es un’. Las strings en las que … Continue reading «DFA de una string en la que el tercer símbolo de RHS es ‘a’»
Requisito previo: autómatas pushdown , aceptación de autómatas pushdown por estado final . Problema: diseñar un PDA no determinista para aceptar el idioma. Las strings del idioma dado serán: L = {aabc, aaabcc, aaabbc, aaaabbcc, ……} En cada una de las strings, la suma total del número de ‘b’ y ‘c’ es igual al número … Continue reading «NPDA por aceptar el lenguaje L = {a(m+n)bmcn | m, n ≥ 1}»
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) – Part 1»
Para resolver problemas complejos necesitamos un algoritmo eficiente. Nos enfrentamos a tantos problemas y algunos de ellos se pueden resolver mediante el uso de un algoritmo y cada algoritmo requiere algo de espacio y tiempo. Para un mejor rendimiento del programa, necesitamos reducir la complejidad espacial y temporal del algoritmo. En este artículo discutiremos brevemente … Continue reading «NL-Integridad y PSPACE-Integridad»