Categoría: Theory of Computation & Automata

Requisito previo: Máquinas Mealy y Moore , diferencia entre la máquina Mealy y la máquina Moore En este artículo, veremos algunos diseños de autómatas finitos con salida, es decir, máquinas de Moore y Mealy. Problema: construcción de máquinas que toman un conjunto de todas las strings sobre {0, 1} como entrada y producen ‘A’ como … Continue reading «Autómatas finitos con salida (conjunto 5)»

Máquinas de Moore:  Las máquinas de Moore son máquinas de estado finito con valor de salida y su salida depende solo del estado actual. Se puede definir como (Q, q0,  ∑,  O, δ, λ) donde: Q es un conjunto finito de estados. q0 es el estado inicial. ∑  es el alfabeto de entrada. O es … Continue reading «Máquinas de Mealy y Moore en TOC»

Como se discutió en Jerarquía de Chomsky , los lenguajes regulares son los tipos de lenguajes más restringidos y son aceptados por autómatas finitos.  Expresiones regulares Las expresiones regulares se utilizan para indicar lenguajes regulares. Una expresión es regular si: ɸ es una expresión regular para el lenguaje regular ɸ. ɛ es una expresión regular … Continue reading «Expresiones regulares, gramática regular y lenguajes regulares»

Una gramática es un conjunto de reglas de producción que se utilizan para generar strings de un lenguaje. En este artículo, hemos discutido cómo encontrar el lenguaje generado por una gramática y viceversa. Lenguaje generado por una gramática – Dada una gramática G, su lenguaje correspondiente L(G) representa el conjunto de todas las strings generadas … Continue reading «Relación entre gramática y lenguaje en Teoría de la Computación – Part 1»

Tabla de transición: la función de transición (∂) es una función que mapea Q * ∑ en Q. Aquí ‘Q’ es un conjunto de estados y ‘∑’ es una entrada de alfabetos. Para mostrar esta función de transición usamos una tabla llamada tabla de transición. La tabla toma dos valores, un estado y un símbolo, … Continue reading «Tabla de transición en autómatas»