Please enable JavaScript.

Coggle requires JavaScript to display documents.

Teoría de autómatas, Conceptos clave - Coggle Diagram

- - - - Reconocidos por una máquina universal o una gramática irrestricta
        
        Ejemplo: El lenguaje universal U = {| M es una máquina de Turing válida y M acepta la cadena w}
    - - Reconocidos por una máquina linealmente acotada o una gramática sensible al contexto.
        
        Ejemplo: El lenguaje {ww^R | w ∈ {a, b}*} y el lenguaje {a^n b^n c^n | n ≥ 0}.
        
        Utilizados en varias áreas de la informática y la teoría de la computación
      - Son un tipo de lenguaje formal que se encuentra en un nivel más alto de complejidad que los lenguajes regulares pero por debajo de los lenguajes recursivamente enumerables
    - - Reconocidos por una gramática libre de contexto o por un autómata de pila
        
        Ejemplo: El lenguaje {a^n b^n | n ≥ 0} y el lenguaje {a^n b^m c^k | n, m, k ≥ 0}.
      - Son un nivel más alto en la jerarquía de Chomsky que los lenguajes regulares y contextuales.
      - Se describen mediante gramáticas libres de contexto
    - - Reconocidos por un autómata finito determinista (AFD) o un autómata finito no determinista (AFND).
        
        Ejemplo: El lenguaje de las cadenas binarias con un número par de unos y el lenguaje de las cadenas que terminan en 0.
      - Son el nivel más básico de los lenguajes formales según la jerarquía de Chomsky
    - - Además del estudio sobre los autómatas, también se analizan los lenguajes formales mediante las gramáticas formales, que son conjuntos predefinidos estrictamente regulados por reglas gramaticales específicas.
      - Son conjuntos de reglas que describen la estructura y composición de lenguajes, ya sean lenguajes naturales o lenguajes de programación
      - Usadas en sistemas de diálogo y reconocimiento de voz para interpretar comandos y respuestas de los usuarios
    - - Es un modelo discreto utilizado para simular sistemas dinámicos complejos mediante la división del espacio en células interconectadas que evolucionan a través del tiempo según reglas locales simples.
        
        Suelen aplicarse en
        
        Simulación en videojuegos
        
        Modelado de reacciones químicas
        
        Diseño de chips y hardware
        
        Modelado de flujo de tráfico
        
        Simulación de fenómenos naturales
    - - Es uno de los modelos más poderosos dentro de la teoría de autómatas y lenguajes formales. Una máquina de Turing consta de una cinta infinita dividida en casillas donde se pueden escribir y leer símbolos, así como moverse a lo largo de la cinta según ciertas reglas predefinidas.
      - Pueden simular el funcionamiento de cualquier algoritmo computacional
      - Usos y aplicación
        
        En la inteligencia artificial, son utilizadas en el modelado de algoritmos de aprendizaje automático y en la comprensión de la capacidad de los sistemas para simular la inteligencia humana.
        
        Se aplican en la simulación de procesos naturales y sistemas físicos, como la propagación de ondas, la difusión de sustancias químicas y el comportamiento de fluidos.
    - - Conocido como autómata de pila o AP, utiliza una pila como memoria auxiliar para almacenar información sobre los símbolos procesados anteriormente. Esto le da al autómata una mayor capacidad expresiva y la posibilidad de reconocer lenguajes más complejos.
        
        Un ejemplo de autómata con pila es un autómata de pila que reconoce el lenguaje de cadenas del tipo "anbn", es decir, cadenas que consisten en una secuencia de "a" seguida de la misma cantidad de "b".
      - Están en capacidad para reconocer lenguajes contextuales y realizar análisis más avanzados de estructuras sintácticas y comportamientos
    - - Un AFND puede tener múltiples transiciones definidas para el mismo símbolo de entrada en un estado dado, lo que permite la existencia de ambigüedad.
      - Pueden ser utilizados en sistemas de reconocimiento de voz y visión para tratar con patrones y contextos variables.
    - - Es un tipo de autómata que solo tiene una transición definida para cada símbolo de entrada en cada estado, es decir, no puede haber ambigüedad en las transiciones.
        
        En los autómatas determinísticos para cada entrada, hay sólo un estado al que el autómata puede ir desde el estado en que se encuentre.
        
        Un tipo interesante de autómatas finitos deterministas son los llamados acíclicos y un ejemplo de estos son los tries.