Enumerable recursivo (RE) o Tipo -0 Idioma Los lenguajes RE o lenguajes de tipo 0 son generados por gramáticas de tipo 0. La máquina de Turing puede aceptar o reconocer un idioma RE, lo que significa que entrará en el estado final para las strings de idioma y puede o no entrar en el estado … Continue reading «Lenguajes recursivos y recursivos enumerables en TOC – Part 1»
El algoritmo de votación de Boyer-Moore es uno de los algoritmos óptimos populares que se utiliza para encontrar el elemento mayoritario entre los elementos dados que tienen más de N/2 ocurrencias. Esto funciona perfectamente bien para encontrar el elemento mayoritario que toma 2 recorridos sobre los elementos dados, lo que funciona en complejidad de tiempo … Continue reading «Algoritmo de votación mayoritaria de Boyer-Moore»
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 Moore y Mealy. Problema: Construcción de las máquinas que toman el número binario {0, 1} como entrada y producen el complemento a 1 de ese … Continue reading «Autómatas finitos con salida (Conjunto 11)»
Finite Automata (FA) es la máquina más simple para reconocer patrones. El autómata finito o máquina de estados finitos es una máquina abstracta que consta de cinco elementos o tuplas. Tiene un conjunto de estados y reglas para pasar de un estado a otro, pero depende del símbolo de entrada aplicado. Básicamente, es un modelo … Continue reading «Introducción de autómatas finitos – Part 1»
Requisito previo: diseñar autómatas finitos . Diseñar un DFA para el conjunto de strings sobre {a, b} de modo que las strings del lenguaje comiencen con «a» y terminen con «b». Allí se formarán dos idiomas deseados: L1 = {a, aab, aabab, …….} L2 = {b, bbab, bbabab, …….} En L1, el elemento inicial es … Continue reading «Proceso de concatenación en DFA»
Requisito previo: diseño de autómatas finitos , artículo anterior: Diseño de autómatas finitos deterministas (conjunto 1) 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| es divisible por 2, es decir, |w| … Continue reading «Diseño de autómatas finitos deterministas (Conjunto 2)»
La teoría de los autómatas (también conocida como teoría de la computación ) es una rama teórica de las ciencias de la computación y las matemáticas, que se ocupa principalmente de la lógica de la computación con respecto a las máquinas simples, denominadas autómatas. Automata* permite a los científicos comprender cómo las máquinas calculan las … Continue reading «Introducción a la Teoría de la Computación»
La máquina Mealy es una máquina de estado finito , su estado actual y las entradas actuales determinan la salida de esta máquina. Complemento a 2 : Es la operación matemática sobre números binarios. Se utiliza para el cálculo como un método de representación de números con signo. Su complemento con respecto a 2 N … Continue reading «Diseñe una máquina harinosa para el complemento de 2»
La siguiente tabla muestra las propiedades de cierre de los lenguajes formales: REG = lenguaje regular DCFL = lenguajes deterministas libres de contexto, CFL = lenguajes libres de contexto, CSL = lenguajes sensibles al contexto, RC = recursivo. RE = Enumerable recursivo Considere que L y M son lenguajes regulares: La estrella de Kleene – … Continue reading «Tabla de propiedades de cierre en TOC»
Prerrequisito: Diseño de autómatas finitos , Diseño de autómatas finitos deterministas (Conjunto 3) En este artículo, veremos algunos diseños de Autómatas finitos deterministas (DFA). Problema 1: construcción de un conjunto mínimo de strings de caracteres que acepta DFA sobre {a, b} en el que cada ‘a’ va seguida de una ‘b’. Explicación: El idioma deseado … Continue reading «Diseño de autómatas finitos deterministas (Conjunto 4)»