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\sum .
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:

FA < DPDA < PDA < LBA < TM

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.

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *