Prerrequisito: Máquina de Turing Tarea: Nuestra tarea es diseñar una máquina de Turing para invertir una string que consta de a y b. Ejemplos: Input-1 : aabb Output-1 : bbaa Input-2 : abab Output-2 : baba Enfoque: la idea básica es leer la entrada de derecha a izquierda y reemplazar Blank(B) con el alfabeto y … Continue reading «Diseñe la máquina de Turing para invertir la string que consta de a y b»
El teorema de Arden establece que: «Si P y Q son dos expresiones regulares sobre , y si P no contiene , entonces la siguiente ecuación en R dada por R = Q + RP tiene una solución única, es decir, R = QP*». Eso significa que, siempre que obtengamos una ecuación en la forma … Continue reading «Teorema de Arden en Teoría de la Computación»
Requisito previo: autómatas finitos , expresiones regulares, gramática y lenguaje . Diseño de autómatas finitos a partir de expresiones regulares 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: Φ (Phi). El idioma del RE dado es L1 = {} es decir, string vacía. … Continue reading «Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 2)»
Declaración del problema: Diseñe y construya una máquina autómata finita no determinista que acepte la string sobre los alfabetos de entrada (a, b, c) con al menos uno de los (símbolos de entrada) que tenga un número impar de presencia en la string. Ejemplo : aaabbbb, ababac, ababababccc … Acercarse: Construya Estado inicial con la … Continue reading «NFA para el idioma al menos uno de los símbolos que aparece un número impar de veces»
En este artículo, discutiremos la descripción general del Código LEX que acepta la string con 0 solamente. Y también implementaremos con código LEX, entenderemos el enfoque. Discutámoslo uno por uno. Descripción general del problema: Código LEX que acepta la string con 0 solamente. Ejemplo – Input : 00 Output : Accepted Input : 1000 Output … Continue reading «Código LEX que acepta la string con 0 solamente»
Supongamos que tenemos una pregunta: Que: Construct minimal state DFA that accepts set of all binary no. which is 2 mod 5(say) Ans: 5 states Para resolver este tipo de preguntas existe una forma tradicional de construir el DFA respectivo para ese problema. El problema en ese enfoque tradicional es que requiere mucho tiempo y … Continue reading «Truco corto para encontrar el número de estados en DFA que acepta un conjunto de todos los números binarios que están modificados por n»
Historia: En 1960, Myhill introdujo el modelo de autómata de grado asociado y en la actualidad este modelo de automatización se entiende como un autómata lineal determinista limitado. Después de esto, otro científico llamado Landweber trabajó en esto y propuso que los lenguajes aceptados por un LBA determinista son lenguajes continuamente sensibles al contexto. En … Continue reading «Introducción a los autómatas acotados lineales (LBA)»
Como las expresiones regulares se pueden construir a partir de autómatas finitos utilizando el método de eliminación de estados, el método inverso, el método de descomposición de estados, se puede utilizar para construir autómatas finitos a partir de las expresiones regulares dadas. Nota: este método construirá NFA (con o sin transiciones ε, según la expresión) … Continue reading «Conversión de expresiones regulares a autómatas finitos»
Autómatas finitos no deterministas (NFA): NFA es un autómata finito en el que, en algunos casos, cuando se proporciona una sola entrada a un solo estado, la máquina pasa a más de 1 estado, es decir, algunos de los movimientos no pueden determinarse de forma única por el presente. estado y el símbolo de entrada … Continue reading «Programa para implementar NFA con paso de épsilon a DFA Conversion»
Un NFA puede tener cero, uno o más de un movimiento desde un estado dado en un símbolo de entrada dado. Un NFA también puede tener movimientos NULL (movimientos sin símbolo de entrada). Por otro lado, DFA tiene un solo movimiento desde un estado dado en un símbolo de entrada dado. Conversión de NFA a … Continue reading «Conversión de NFA a DFA»