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 = { [Tex]b^n [/Tex]| n>=1}, es decir, L = {ab, aabb, aaabbb, aaaabbbb, ……} En cada una de las strings, el número de a es seguido por el mismo número de … Continue reading «NPDA por aceptar el lenguaje L = {an bn | n>=1}»
Expresiones regulares : Es una forma de representar lenguajes regulares. La descripción algebraica de los lenguajes regulares se realiza mediante expresiones regulares. Pueden definir el mismo lenguaje que pueden describir varias formas de autómatas finitos. Las expresiones regulares ofrecen algo que los autómatas finitos no ofrecen, es decir, es una forma declarativa de expresar las … Continue reading «Propiedades de las expresiones regulares»
Requisito previo: gramática regular, expresiones regulares, jerarquía de Chomsky Descripción general: en este artículo, discutiremos la descripción general de la gramática regular que puede ser lineal derecha o lineal izquierda, y se centrará principalmente en la relación entre la gramática y el lenguaje. Discutámoslo uno por uno. Tipos: Hay dos tipos de gramática de la … Continue reading «Relación entre la gramática y el lenguaje»
Prerrequisito: Diseño de autómatas finitos , Diseño de autómatas finitos deterministas (Conjunto 2) 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 aceptación de DFA sobre {a, b} donde cada string contiene ‘a’ como substring. Explicación: El idioma deseado será como: L1 = … Continue reading «Diseño de autómatas finitos deterministas (Conjunto 3)»
Prerrequisito: Autómatas finitos , Expresiones regulares, gramática y lenguaje , Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 7) 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 = {an | n≥ 1} El lenguaje del RE dado es- … Continue reading «Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 8)»
Requisito previo: Introducción a los autómatas finitos Problema-1: Construcción de un NFA mínimo que acepta un conjunto de strings sobre {a, b} en el que cada string del lenguaje termina con ‘ab’. Explicación: El idioma deseado será como: L1 = {ab, abbab, abaab, ………..} Aquí, como podemos ver, cada string del idioma anterior termina con … Continue reading «Máquinas NFA que aceptan todas las strings que terminan o no terminan con la substring ‘ab’»
Las expresiones regulares son capaces de describir la sintaxis de los tokens. Cualquier construcción sintáctica que pueda ser descrita por la expresión regular también puede ser descrita por la gramática libre de contexto. Expresión regular: (a|b)(a|b|01) Gramática libre de contexto: S –> aA|bA A –> aA|bA|0A|1A|e *e denota épsilon. La gramática libre de contexto forma … Continue reading «Expresión Regular Vs Gramática Libre de Contexto»
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 {a, b} como entrada y cuentan el número de … Continue reading «Autómatas finitos con salida (Conjunto 3)»
Descripción general: De acuerdo con los aspectos teóricos de Automata , una operación de cociente se puede definir como la técnica que reconoce un superconjunto de la automatización dada, particularmente para la string dada de lenguaje formal (Un lenguaje formal es un conjunto de strings de símbolos extraídos de un finito alfabeto (puede tener reglas … Continue reading «Operación cociente en autómatas»
Minimización de DFA usando el teorema de Myhill-Nerode: Se requiere la minimización de DFA para obtener la versión mínima y equivalente de cualquier DFA que consista en el mínimo número de estados posibles. El teorema de Myhill-Nerode se puede utilizar para convertir un DFA en su DFA equivalente con un número mínimo de estados. Este … Continue reading «Minimización de DFA utilizando el teorema de Myhill-Nerode»