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 determinar a partir de la clase o conjunto de lenguajes aceptados por ese tipo particular de máquina. Aquí está la secuencia creciente del poder expresivo de las máquinas:
Como podemos observar, FA es menos potente que cualquier otra máquina. Es importante tener en cuenta que DFA y NFA tienen la misma potencia porque cada NFA se puede convertir en DFA y cada DFA se puede convertir en NFA.
La Turing Machine ie TM es más poderosa que cualquier otra máquina.
(i) Equivalencia de autómatas finitos (FA):
Finite Automata ≡ PDA with finite Stack ≡ TM with finite tape ≡ TM with unidirectional tape ≡ TM with read only tape
(ii) Equivalencia de Pushdown Automata (PDA):
PDA ≡ Finite Automata with Stack
(iii) Equivalencia de Turing Machine (TM):
Turing Machine ≡ PDA with additional Stack ≡ FA with 2 Stacks
Las aplicaciones de estos autómatas son las siguientes:
- Para el diseño del análisis léxico de un compilador.
- Para reconocer el patrón usando expresiones regulares.
- Para el diseño de los circuitos combinados y secuenciales utilizando Máquinas de Mealy y Moore.
- Se utiliza en editores de texto.
- Para la implementación de correctores ortográficos.
2. Autómatas de empuje hacia abajo (PDA) –
- Para diseñar la fase de análisis de un compilador (Análisis de sintaxis).
- Para la implementación de aplicaciones de pila.
- Para evaluar las expresiones aritméticas.
- Por resolver el problema de la Torre de Hanoi.
3. Autómatas acotados lineales (LBA) –
- Para la implementación de la programación genética.
- Para construir árboles de análisis sintáctico para el análisis semántico del compilador.
- Para resolver cualquier problema recursivamente enumerable.
- Para comprender la teoría de la complejidad.
- Para implementación de redes neuronales.
- Para la implementación de Aplicaciones Robóticas.
- Para implementación de inteligencia artificial.
Publicación traducida automáticamente
Artículo escrito por shreya garg 4 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA