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) – Part 1»
Requisito previo: lema de bombeo , cómo identificar si un idioma es regular o noPor lo general, nos enfrentamos a preguntas para identificar cuáles de los idiomas dados están libres de contexto. En el caso de los lenguajes regulares, es comparativamente fácil responder esto, pero para los lenguajes libres de contexto, a veces es complicado. … Continue reading «Compruebe si el idioma es libre de contexto o no»
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.»
Los autómatas finitos no deterministas (NFA) son autómatas finitos que tienen cero, uno o más de un movimiento desde un estado dado en un símbolo de entrada dado. Epsilon NFA es el NFA que contiene movimiento(s) epsilon/movimiento(s) nulo(s). Para eliminar el movimiento epsilon/movimiento nulo de epsilon-NFA y convertirlo en NFA, seguimos los pasos que se … Continue reading «Conversión de Epsilon-NFA a NFA»
Prerrequisito – Máquina de Turing Las máquinas de Turing se pueden clasificar en términos generales en dos tipos, los aceptores y los transductores. Acceptor Turing Machine es un autómata utilizado para definir lenguajes aceptables para Turing. Tal máquina se puede usar para verificar si una string dada pertenece a un idioma o no. Se define … Continue reading «Construcción de la máquina de Turing (máquina de Turing de transductores) en Java»
El lenguaje libre de contexto (CFL) es un lenguaje generado por una gramática libre de contexto o gramática de tipo 2 (según la clasificación de Chomsky) y es aceptado por un autómata pushdown. Algunas propiedades muy importantes de un lenguaje libre de contexto son: Los lenguajes libres de contexto de regularidad son lenguajes PDA no … Continue reading «Varias propiedades de los lenguajes libres de contexto (CFL)»
Los lenguajes libres de contexto (CFL) son aceptados por autómatas pushdown . Los lenguajes libres de contexto pueden ser generados por gramáticas libres de contexto, que tienen producciones (reglas de sustitución) de la forma: A -> ρ (donde A ∈ N y ρ ∈ (T ∪ N)* y N es un no terminal y T … Continue reading «Propiedades de cierre de los lenguajes libres de contexto»
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 = { | m, n>=1}, es decir, L = { abc, abcc, abccc, aabbc, aaabbbcc, aaaabbbbccccc, …… } En cada una de las strings, el número de a es igual al … Continue reading «NPDA por aceptar el lenguaje L = {an bn cm | m,n>=1}»
La minimización de DFA significa convertir un DFA determinado en su DFA equivalente con un número mínimo de estados. Minimización de DFA Supongamos que hay un DFA D < Q, Σ, q0, δ, F > que reconoce un idioma L. Entonces se puede construir el DFA minimizado < Q’, Σ, q0, δ’, F’ > para … Continue reading «Minimización de DFA»
Requisito previo: autómatas finitos Dada una string S de tamaño N , la tarea es diseñar un autómata finito determinista (DFA) para aceptar el lenguaje L = {a N | norte ≥ 1} . El lenguaje regular L es {a, aa, aaa, aaaaaaa…, }. Si la string dada sigue el idioma dado L , imprima … Continue reading «Programa para construir un DFA que acepte el lenguaje L = {aN | norte ≥ 1}»