Aplicaciones de varios autómatas. – Part 1

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:

1. Autómatas finitos (FA) –

• 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.

4. Máquina de Turing (TM) –

• 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.