Categoría: Theory of Computation & Automata

Altura de la estrella de la expresión regular y el lenguaje regular

Posted on by Rudeus Greyrat

La altura de la estrella se relaciona con el campo de la teoría de la computación (TOC). Se utiliza para indicar la complejidad estructural de las expresiones regulares y los lenguajes regulares. Aquí la complejidad se relaciona con la máxima profundidad de anidamiento de las estrellas Kleene presentes en una expresión regular. Cabe señalar aquí … Continue reading «Altura de la estrella de la expresión regular y el lenguaje regular»

Gramática sensible al contexto (CSG) y lenguaje (CSL)

Posted on by Rudeus Greyrat

Gramática sensible al contexto: una gramática sensible al contexto es una gramática sin restricciones en la que todas las producciones son de forma, donde α y β son strings de no terminales y terminales. Las gramáticas sensibles al contexto son más poderosas que las gramáticas libres de contexto porque hay algunos lenguajes que pueden ser … Continue reading «Gramática sensible al contexto (CSG) y lenguaje (CSL)»

Aceptación de autómatas pushdown por estado final

Posted on by Rudeus Greyrat

Hemos discutido Pushdown Automata (PDA) y su aceptación por el artículo de pila vacía. Ahora, en este artículo, discutiremos cómo la PDA puede aceptar una CFL según el estado final. Dado un PDA P como: P = (Q, Σ, Γ, δ, q0, Z, F) El lenguaje aceptado por P es el conjunto de todas las … Continue reading «Aceptación de autómatas pushdown por estado final»

DFA de una string en la que el segundo símbolo de RHS es ‘a’

Posted on by Rudeus Greyrat

Requisito previo : problema de introducción a los autómatas finitos: dibujar autómatas finitos deterministas (DFA) del lenguaje que contiene el conjunto de todas las strings sobre {a, b} en el que el segundo símbolo de RHS es ‘a’. Las strings en las que el penúltimo símbolo es «a» son: aa, ab, aab, aaa, aabbaa, bbbab … Continue reading «DFA de una string en la que el segundo símbolo de RHS es ‘a’»

Variación de la máquina de Turing

Posted on by Rudeus Greyrat

Prerrequisito – Máquina de Turing  1. Máquina de Turing de múltiples vías:   Una máquina de Turing con k-pistas (para algunos k>0) tiene k-pistas y un cabezal R/W que las lee y escribe todas una por una. Una máquina de Turing de k-pista puede ser simulada por una máquina de Turing de una sola pista 2. … Continue reading «Variación de la máquina de Turing»

Unión e Intersección de Lenguas Regulares con CFL

Posted on by Rudeus Greyrat

Requisito previo: jerarquía de Chomsky , lenguajes regulares Como todos sabemos, los lenguajes aceptados por autómatas finitos se denominan lenguajes regulares y los que son aceptados por autómatas pushdown se denominan lenguajes libres de contexto. Pero, cuando se trata de la unión o intersección de estos dos lenguajes, a algunas personas les resulta difícil de … Continue reading «Unión e Intersección de Lenguas Regulares con CFL»

Diferencia entre Pushdown Automata y Finite Automata

Posted on by Rudeus Greyrat

Autómatas Pushdown :  Un autómata Pushdown (PDA) es una máquina de estado finito con un almacenamiento de pila adicional. Se utiliza una pila adicional para tomar la decisión de las transiciones además de los símbolos de entrada y el estado actual. Contiene las siguientes 7 tuplas:  Autómatas finitos :  un autómata finito es un modelo … Continue reading «Diferencia entre Pushdown Automata y Finite Automata»

∈-NFA de Lenguaje Regular L = 0(0+1)*1 y L = (00)*1(11)*

Posted on by Rudeus Greyrat

Los autómatas finitos no deterministas y los autómatas finitos no deterministas ∈ son casi lo mismo excepto por su función de transición y existen algunas reglas especiales para la construcción de ∈-NFA. ∈-NFA is defined in 5 tuple representation {Q, q0, Σ, δ, F} where – Q is the set of all states, q0 is … Continue reading «∈-NFA de Lenguaje Regular L = 0(0+1)*1 y L = (00)*1(11)*»

Programa LEX para imprimir la string más larga y encontrar el promedio de números dados

Posted on by Rudeus Greyrat

Lex: El programa Lex tiene el propósito de generar un analizador léxico. Los analizadores Lex son un programa que transforma los flujos de entrada en una secuencia de tokens. El programa AC implementa el analizador léxico para leer el flujo de entrada y generar una salida como código fuente.  Comandos a utilizar – lex file_name.l … Continue reading «Programa LEX para imprimir la string más larga y encontrar el promedio de números dados»

NPDA por aceptar el lenguaje L = {anbm | n,m ≥ 1 y n ≠ m}

Posted on by Rudeus Greyrat

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 , es decir, L = {aab, abb, aaab, abbb, aaaab, aaabb, aabbb, abbbb ……} En cada una de las strings, el número de a es seguido por un número desigual de b. Explicación … Continue reading «NPDA por aceptar el lenguaje L = {anbm | n,m ≥ 1 y n ≠ m}»