Categoría: Theory of Computation & Automata

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 – Part 1»

Prerrequisito: Autómatas finitos , Expresiones regulares, gramática y lenguaje , Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 6) 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 = b*aa(a+b)*+b*ab*aa(a+b*) El lenguaje del RE dado es- {aaa, baa, baa, … Continue reading «Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 7)»

Prerrequisito – Teoría de la Computación Gramática: Es un conjunto finito de reglas formales para generar oraciones sintácticamente correctas u oraciones significativas correctas. Constituir de gramática: la gramática se compone básicamente de dos elementos básicos: Símbolos terminales: los símbolos terminales son aquellos que son los componentes de las oraciones generadas usando una gramática y se … Continue reading «Introducción a la gramática en la teoría de la computación»

Se dice que un lenguaje es regular si se puede representar usando un autómata finito o si se puede generar una expresión regular para él. Esta definición nos lleva a la definición general que; Por cada Expresión Regular correspondiente al lenguaje, se puede generar un Autómata Finito. Para ciertas expresiones como :- (a+b), ab, (a+b)* … Continue reading «Teorema de Kleene en TOC | Parte 1»

Requisito previo: autómatas finitos , expresiones regulares, gramática y lenguaje . Diseño de autómatas finitos a partir de expresiones regulares En el siguiente artículo, veremos algunos diseños de autómatas finitos a partir de expresiones regulares dadas: Expresión regular 1: Φ (Phi). El idioma del RE dado es L1 = {} es decir, string vacía. Sus … Continue reading «Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 2) – Part 1»

Prerrequisito – Problema de la máquina de Turing -1: Dibuje una máquina de Turing que reste dos números. Ejemplo: Pasos: Paso 1. Si encuentra 0, convierta 0 en X y vaya a la derecha, luego convierta todos los 0 en 0 y vaya a la derecha. Paso 2. Luego convierta C en C y vaya … Continue reading «Máquina de Turing para sustracción | Serie 1»