Categoría: Theory of Computation & Automata

Diseñe DFA en código LEX que acepte la string con un número binario par sobre el alfabeto de entrada {0,1}

Posted on by Rudeus Greyrat

Descripción general del problema:  diseñe un DFA en código LEX que acepte la string que tiene un número binario par sobre el alfabeto de entrada {0,1}. Ejemplo –  Input : 1010 Output: Accepted Input : 1001 Output: Not Accepted Input: 23ab Output:Invalid Input:ab345 Output:Invalid Input:010101 Output:Not Accepted Enfoque: LEX nos proporciona un estado INICIAL por … Continue reading «Diseñe DFA en código LEX que acepte la string con un número binario par sobre el alfabeto de entrada {0,1}»

Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 5) – Part 1

Posted on by Rudeus Greyrat

Prerrequisito: Autómatas finitos , Expresiones regulares, gramática y lenguaje , Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 4)  En el siguiente artículo, veremos algunos diseños de autómatas finitos no deterministas a partir de la expresión regular dada: Como NFA se puede cambiar a DFA correspondiente.  Expresión regular 1: Lenguaje regular,   L1 = … Continue reading «Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 5) – Part 1»

Gráficos L y lo que representan en TOC

Posted on by Rudeus Greyrat

Requisito previo: introducción a los autómatas finitos Todos los lenguajes de programación se pueden representar como autómatas finitos. C, Paskal, Haskell, C++, todos tienen una estructura específica, gramática, que se puede representar mediante un gráfico simple. La mayoría de los gráficos son NFA o DFA. Pero NFA y DFA determinan el grupo de idiomas más … Continue reading «Gráficos L y lo que representan en TOC»

Optimización de la tabla de estados de una máquina completamente especificada

Posted on by Rudeus Greyrat

Optimice la tabla de estado de una tabla de estado dada de una máquina completamente especificada utilizando un algoritmo basado en partición. Ejemplos:  Input : 6 E 0 D 1 F 0 D 0 E 0 B 1 F 0 B 0 C 0 F 1 B 0 C 0 Output : A E, 0 … Continue reading «Optimización de la tabla de estados de una máquina completamente especificada»

Diferencia entre la máquina Mealy y la máquina Moore

Posted on by Rudeus Greyrat

Mealy Machine se define como una máquina en la teoría de la computación cuyos valores de salida están determinados tanto por su estado actual como por las entradas actuales. En esta máquina es posible como máximo una transición. Tiene 6 tuplas: (Q, q0, ∑, O, δ, λ’)  Q es un conjunto finito de estados  q0 es … Continue reading «Diferencia entre la máquina Mealy y la máquina Moore»

Relación entre gramática y lenguaje en Teoría de la Computación

Posted on by Rudeus Greyrat

Una gramática es un conjunto de reglas de producción que se utilizan para generar strings de un idioma. 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»

Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 1) – Part 1

Posted on by Rudeus Greyrat

En este artículo, veremos algunas expresiones regulares populares y cómo podemos convertirlas en autómatas finitos. Número par de a: la expresión regular para un número par de a es (b|ab*ab*)* . Podemos construir un autómata finito como se muestra en la Figura 1. Los autómatas anteriores aceptarán todas las strings que tengan un número par … Continue reading «Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 1) – Part 1»

Turing Machine para verificar si la string dada es Even Palindrome o no

Posted on by Rudeus Greyrat

Una string w se llama palíndromo si leer w de izquierda a derecha da el mismo resultado que leer w de derecha a izquierda. Un palíndromo par tiene un número par de símbolos. Ejemplos: Input : abaaba Output :YES Input :abba Output :YES Input :abbaba Output :NO Input :Empty String or Output :YES Representación básica: … Continue reading «Turing Machine para verificar si la string dada es Even Palindrome o no»

Diferencia entre gramática ambigua e inequívoca

Posted on by Rudeus Greyrat

Requisito previo: gramáticas libres de contexto 1. Gramática ambigua : una gramática libre de contexto se llama gramática ambigua si existe más de un árbol de derivación o árbol de análisis. Ejemplo – S -> S + S / S * S / S / a 2. Gramática inequívoca: una gramática libre de contexto se … Continue reading «Diferencia entre gramática ambigua e inequívoca»

Diseño de autómatas finitos deterministas (Conjunto 6)

Posted on by Rudeus Greyrat

Requisito previo: diseño de autómatas finitos 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 a n b m , donde n y m son mayores o iguales a 1. Explicación: el lenguaje … Continue reading «Diseño de autómatas finitos deterministas (Conjunto 6)»