Categoría: Theory of Computation & Automata

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 un conjunto de todas las strings sobre {0, 1} como entrada y producen ‘A’ como salida si la entrada termina con ’10’ o producir ‘B’ como salida si la entrada termina con ’11’; … Continue reading «Las máquinas de Moore y Mealy para producir ‘A’, ‘B’, ‘C’ dependen de las entradas que terminan con ’10’ o con ’11’, de lo contrario, otros»

Requisito previo: introducción de autómatas finitos Los autómatas finitos no deterministas y los autómatas finitos no deterministas ∈ son casi lo mismo excepto por su función de transición y existen algunas reglas especiales para la construcción de ∈-NFA. En ∈-NFA, los siguientes son los estados de la siguiente manera. ∈-NFA is defined in 5 tuple … Continue reading «∈-NFA de L = (a* + b*)»

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}, es decir, L = {abcc, aabccc, abbbcccc, aaabbccccc, ……} En cada una de las strings, la suma total del número de ‘a’ y ‘b’ es … Continue reading «NPDA por aceptar el lenguaje L = {ambnc(m+n) | m, n ≥ 1}»

Requisito previo: autómatas pushdown , aceptación de autómatas pushdown por estado final  Un autómata pushdown es similar a un autómata finito determinista excepto que tiene algunas propiedades más que un DFA. La estructura de datos utilizada para implementar un PDA es stack. Una PDA tiene una salida asociada con cada entrada. Todas las entradas se … Continue reading «Construir autómatas pushdown para idiomas dados»

Problema: Construya un DFA que acepte el lenguaje L = {a n b m | n > =1, (m) módulo 3 = 1}. Explicación: Para construir el DFA, se deben recordar las siguientes cosas: which means any no of elements, and = which means any no of elements greater than 1. Ejemplos: Input: a a … Continue reading «Construya un DFA que acepte el lenguaje L = {anbm | n > =1, (m) módulo 3 = 1}»

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 contiene ‘a’ como substring. Explicación: El idioma deseado será como: L1 = {ab, abba, abaa, … Continue reading «Diseño de autómatas finitos no deterministas (Conjunto 4)»