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»
Requisitos previos: Gramáticas libres de contexto , Gramática ambigua , Diferencia entre gramática ambigua y no ambigua, Precedencia y asociatividad de operadores , Gramática recursiva En este artículo vamos a ver la eliminación de la ambigüedad de la gramática usando ejemplos adecuados. Gramática ambigua vs inequívoca: las gramáticas que tienen más de un árbol de … Continue reading «Eliminación de la ambigüedad (Conversión de una gramática ambigua en una gramática inequívoca)»
Prerrequisito – Clasificación de gramáticas libres de contexto , ambigüedad y analizadores Recursividad izquierda: gramática de la forma, S –> S / a / b Se llama recursivo por la izquierda, donde S es cualquier no Terminal y a, yb son cualquier conjunto de terminales. Problema con la recursión izquierda: si una recursión izquierda está … Continue reading «Eliminación de la recursión izquierda directa e indirecta en una gramática»
Requisito previo: Clique es NP A La reducción de tiempo polinomial es un método para resolver un problema usando otro. E-TM = {<M> : M es una TM y } CLIQUE = {<G, k> : el grafo G tiene una camarilla con al menos k vértices}. Nota: dado que CLIQUE es NP => algunos NDTM … Continue reading «Reducción de Polytime Manyone: Clique a E-TM»
Máquinas de Moore: una máquina de Moore es básicamente un DFA con una salida asociada con cada estado. Estas máquinas se pueden usar para una amplia variedad de tareas, como contar las ocurrencias de una substring particular en una string dada, encontrar el complemento a 2 de un número binario , etc. Funcionamiento de la … Continue reading «Implementación de Moore Machines en C++»
Que-1: Dibuje un autómata finito determinista y no determinista que acepte 00 y 11 al final de una string que contenga 0, 1, por ejemplo, 01010100 pero no 000111010. Explicación: diseñe un DFA y NFA de una misma string si el valor de entrada alcanza el estado final, entonces es aceptable; de lo contrario, no … Continue reading «Practicar problemas en autómatas finitos»
Diseñe un autómata finito determinista (DFA) para aceptar el lenguaje L = Para crear DFA para el lenguaje, L = { a^nb^m ; n+m=par } usa las matemáticas elementales, que dicen : par + par = par e impar + impar = par Ejemplos: Input: a a b b // n = 2, m = … Continue reading «DFA por aceptar el idioma L = { anbm | n+m=par }»
De acuerdo con la Jerarquía de Chomsky , el requisito de un cierto tipo de gramática para generar un idioma a menudo se enfrenta con una máquina adecuada que puede usarse para aceptar el mismo idioma. Cuando la gramática es simple, el lenguaje se vuelve más complejo, por lo que necesitamos una máquina más poderosa … Continue reading «Estudio Detallado de Autómatas PushDown»
Prerrequisito – Máquina de Turing El lenguaje L = {0 2n 1 n | n >= 0} representa un tipo de lenguaje en el que usamos solo 2 símbolos, es decir, 0 y 1. Al principio, el lenguaje tiene un número de 0 seguido de exactamente la mitad del número de 1. Cualquier string que … Continue reading «Construya una máquina de Turing para el lenguaje L = {02n1n | n>=0}»
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) – Part 1»