Requisito previo: autómatas pushdown , aceptación de autómatas pushdown por estado final Problema: diseñar un PDA no determinista para aceptar el lenguaje L = {a 2m b 3m | m ≥ 1}, es decir, L = {aabbb, aaaabbbbbb, aaaaaabbbbbbbbb, aaaaaaaabbbbbbbbbbbb, ……} En cada una de las strings, por cada 2 ‘a’ hay 3 ‘b’. Explicación: … Continue reading «NPDA por aceptar el lenguaje L = {a2mb3m | metro ≥ 1}»
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)»
Requisito previo: autómatas pushdown , aceptación de autómatas pushdown por estado final Problema: diseñe un PDA no determinista para aceptar el lenguaje L = { [Tex]b^{2m} [/Tex]: m>=1}, es decir, L = {abb, aabbbb, aaabbbbbb, aaaabbbbbbbb, ……} En cada una de las strings, el número de a es seguido por el doble de b. Explicación: … Continue reading «NPDA por aceptar el lenguaje L = {am b(2m) | m>=1}»
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 cada ‘a’ va seguida de una ‘bb’. Explicación: El idioma deseado será como: L1 = {ε, abb, abbabb, … Continue reading «Diseño de autómatas finitos deterministas (Conjunto 5)»
Transductores en autómatas finitos (FA) significa FA con salida. Hay dos tipos de Máquinas para FA con Salida. 1. Mealy Machine: Es la FA en la que se asocia la salida a cada transición. (Eso significa que la salida depende del estado y la entrada). 2. Máquina de Moore: Es una FA en la que … Continue reading «Diseño de autómatas finitos para varias operaciones como complemento a 1, complemento a 2»
Dada una string binaria str , la tarea es crear un DFA que acepte los idiomas que terminan en «01» sobre los caracteres {0, 1} . Ejemplos: Entrada: str = “00011101” Salida: String aceptada Explicación: Como la string dada termina en “01”, por lo tanto, se acepta. Entrada: str = “00001111” Salida: String rechazada Explicación: … Continue reading «Programa para compilar DFA que acepta los idiomas que terminan en «01» sobre los caracteres {0, 1}»
Prerrequisito: Autómatas finitos , Expresiones regulares, gramática y lenguaje , Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 3) 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 = (a+b)(a+b) El lenguaje del RE dado es, {aa, ab, ba, … Continue reading «Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 4)»
Dada una string binaria S , la tarea es escribir un programa para DFA Machine que acepte una string con números impares de 0 y 1 . Ejemplos: Entrada: S = “010011” Salida: Aceptada Explicación: La string dada S contiene un número impar de ceros y unos. Entrada: S = “00000” Salida: No aceptado Explicación: … Continue reading «Programa para construir DFA aceptando un número impar de 0 y un número impar de 1»
Requisito previo: Introducción a los autómatas finitos deterministas Construya un DFA que acepte strings str que comiencen con el alfabeto de entrada ‘a’ pero que no contengan ‘aab’ como una substring sobre la entrada {a, b} . Ejemplos: Entrada: str = “babba” Salida: No aceptado Explicación: La string dada no comienza con ‘a’. Entrada: str … Continue reading «DFA que comienza con ‘a’ pero no contiene la substring ‘aab’»
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 máquinas que toman un conjunto de todas las strings sobre {0, 1} como entrada y producen ‘A’ como salida … Continue reading «Autómatas finitos con salida (Set 6)»