Requisito previo: autómatas pushdown , la aceptación de autómatas pushdown por parte del PDA de estado final juega un papel muy importante en la tarea de diseño del compilador. Por eso es necesario tener una buena práctica en PDA. Nuestro objetivo es construir un PDA para L = {a (2*m) c (4*n) d n b … Continue reading «Construir autómatas pushdown para L = {a(2*m)c(4*n)dnbm | m, n ≥ 0}»
Requisito previo: autómatas finitos , gráficos L y lo que representan Los gráficos L pueden generar lenguajes sensibles al contexto, pero es mucho más difícil programar un lenguaje sensible al contexto que programar uno normal. Es por eso que se me ocurrió una hipótesis sobre qué tipo de L-graphs pueden generar un lenguaje regular. Pero … Continue reading «Hipótesis (regularidad del lenguaje) y algoritmo (L-graph a NFA) en TOC»
Automata es una máquina que puede aceptar las Strings de un Lenguaje L sobre un alfabeto de entrada . Hasta ahora estamos familiarizados con los Tipos de Autómatas. Ahora, analicemos el poder expresivo de los autómatas y comprendamos mejor sus aplicaciones. Poder expresivo de varios autómatas : el poder expresivo de cualquier máquina se puede … Continue reading «Aplicaciones de varios autómatas. – Part 1»
Requisito previo: diseñar autómatas finitos . Diseñar un DFA para el conjunto de strings sobre {a, b} de modo que las strings del lenguaje comiencen con «a» y terminen con «b». Allí se formarán dos idiomas deseados: L1 = {a, aab, aabab, …….} L2 = {b, bbab, bbabab, …….} En L1, el elemento inicial es … Continue reading «Proceso de concatenación en DFA – Part 1»
Dada la string binaria str , la tarea es crear un DFA que acepte la string si la string comienza con «01» o termina con «01». Entrada: str = “010000” Salida: Aceptada Explicación: La string dada comienza con “01”. Entrada: str = “1100111” Salida: No aceptado Explicación: La string dada no comienza ni termina con … Continue reading «Cree un DFA para aceptar strings binarias que comiencen o terminen con «01»»
Prerrequisito: Autómatas finitos , Expresiones regulares, gramática y lenguaje , Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 2) 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: ‘ab*’ (‘a’ seguido de cualquier número de ‘b’). El lenguaje del RE dado es, … Continue reading «Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 3)»
Problema: Diseñe un PDA no determinista que acepte el lenguaje L = {wwR w ∈ (a, b) + }, es decir, L = {aa, bb, abba, aabbaa, abaaba, ……} Requisito previo: autómatas pushdown , aceptación de autómatas pushdown por estado final Explicación: en este tipo de string de entrada, una entrada tiene más de un … Continue reading «NPDA por aceptar el lenguaje L = {wwR | w ∈ (a,b)*}»
Teorema de reducción: una reducción de A a B es una función H acepta w si R acepta f(w) si f(w)∈ B si w ∈ A Todo w ∈ A corresponde a algún f(w) ∈ B. Todo w ∉ A corresponde a algún f(w) ∉ B. f no tiene … Continue reading «Teorema de reducción en TOC»
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 las máquinas que toman el número binario {0, 1} como entrada y producen residuo módulo ‘2’ como salida, es … Continue reading «Construcción de las máquinas para producir residuo módulo ‘2’ de números binarios»
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 DFA mínimo que acepta un conjunto de strings sobre {a, b} en el que el segundo símbolo del lado izquierdo siempre es ‘b’. Explicación: El idioma deseado será como: L1 = {ab, aba, abaa, … Continue reading «Diseño de autómatas finitos deterministas (Conjunto 8) – Part 1»