Requisito previo: conversión de la gramática libre de contexto a la forma normal de Chomsky El algoritmo CYK es un algoritmo de análisis para la gramática libre de contexto. Para aplicar el algoritmo CYK a una gramática, debe estar en la forma normal de Chomsky. Utiliza un algoritmo de programación dinámica para saber si una … Continue reading «Algoritmo CYK para gramática libre de contexto»
Requisito previo: diseñar un autómata finito Supongamos que tenemos un DFA que está definido por ( Q, , , q0, F ) y acepta el lenguaje L 1 . Entonces, el DFA que acepta el lenguaje L 2 donde L 2 = ̅L 1 ‘, se definirá como sigue: ( Q, , , q0, Q-F … Continue reading «Proceso de complementación en DFA»
Requisito previo: autómatas pushdown , aceptación de autómatas pushdown por el estado final autómatas pushdown (PDA) juega un papel importante en el diseño del compilador. Por lo tanto, es necesario tener buenas manos en PDA. Nuestro objetivo es construir un PDA para L = {0 n 1 m 2 m 3 n | m, n … Continue reading «Construir autómatas pushdown para L = {0n1m2m3n | m, n ≥ 0}»
Ya hemos discutido los autómatas finitos . Pero los autómatas finitos se pueden usar para aceptar solo lenguajes regulares. Pushdown Automata es un autómata finito con memoria adicional llamada pila que ayuda a los autómatas Pushdown a reconocer lenguajes libres de contexto. Un Pushdown Automata (PDA) se puede definir como: Q es el conjunto de estados ∑ … Continue reading «Introducción de autómatas pushdown»
Prerrequisito – Máquina de Turing El lenguaje L = {0 n 1 n 2 n | n≥1} representa un tipo de lenguaje en el que usamos solo 3 caracteres, es decir, 0, 1 y 2. Al principio, el lenguaje tiene un número de 0 seguido de igual número de 1 y luego seguido de igual … Continue reading «Construya una máquina de Turing para el lenguaje L = {0n1n2n | n≥1}»
Prerrequisito: Autómatas finitos deterministas String dada, str consta de los caracteres ‘a’ y ‘b’. La tarea es verificar si la string str comienza y termina con caracteres diferentes o no. Si es así, imprima ‘SÍ’ con transiciones de estado, de lo contrario imprima ‘NO’. Ejemplos: Entrada: ababab Salida: SÍ Explicación: La string «ababab» comienza con ‘a’ … Continue reading «Programa para construir un DFA que acepte strings que comiencen y terminen con un carácter diferente»
Prerrequisito – Máquina de Turing El lenguaje L = {a n b m c nm | n >= 0 andm>=0} representa un tipo de lenguaje donde usamos solo 3 símbolos, es decir, a, b y c. Al principio, el lenguaje tiene un número n de a seguido de un número m de b y luego … Continue reading «Construya una máquina de Turing para el lenguaje L = {a^nb^mc^nm donde n >=0 y m >= 0}»
Requisito previo: máquinas de Mealy y Moore Un detector de secuencias es una máquina de estados secuenciales que toma una string de bits de entrada y genera una salida 1 cada vez que se detecta la secuencia de destino. En una máquina Mealy, la salida depende del estado actual y de la entrada externa (x). … Continue reading «Detector de secuencia de diseño 101 (máquina Mealy)»
Prerrequisito: Introducción a los autómatas finitos En este artículo, veremos algunos diseños de autómatas finitos no deterministas (NFA). Problema-1: Construcción de un NFA mínimo que acepta un conjunto de strings sobre {a, b} en el que cada string del idioma contiene ‘ab’ como substring. Explicación: El idioma deseado será como: L1 = {ab, abba, abaa, … Continue reading «Diseño de autómatas finitos no deterministas (Conjunto 5)»
Requisito previo: introducción del programa Finite Automata C++ para construir un NFA que acepte el conjunto de strings sobre un alfabeto {0, 1, 2} tal que el dígito final haya aparecido antes. Ejemplos: Input : 01101 Output : Accepted Input : 012 Output : Not Accepted Input : 2 Output : Not Accepted Input : … Continue reading «NFA que acepta un conjunto de strings sobre un alfabeto {0, 1, 2} tal que el dígito final ha aparecido antes»