Fundamentos de la Teoría de Autómatas: Definición y Estructura de AFD, AFN y Autómatas de Pila

Conceptos Fundamentales de Autómatas Finitos (AFD y AFN)

Autómata Finito (AF): Los autómatas finitos consisten en ir pasando de un estado a otro. Los estados son el único medio que disponen los AF para recordar los eventos que ocurren. Los estados finales indican que, al llegar a ellos, la secuencia de eventos que condujo hasta ese punto puede considerarse como aceptable, siempre y cuando se hayan consumido todos los caracteres de la cadena de entrada.

Autómata Finito Determinista (AFD)

Una máquina de estados finitos determinista $M$ se define formalmente como un quíntuplo:

$$M = (K, \Sigma, \delta, q_0, F)$$

Componentes del AFD

• K: Es un conjunto finito de estados.
• $\Sigma$: Es el alfabeto de entrada.
• $q_0$: Es el estado inicial, donde $q_0 \in K$.
• $\delta$: Es la función de transición, definida como $\delta: K \times \Sigma \to K$.
• F: Es un conjunto de estados finales ($F \subseteq K$).

El lenguaje aceptado por un AFD está compuesto por las cadenas pertenecientes al alfabeto que permiten la transición desde el estado inicial hasta un estado final.

Autómata Finito No Determinista (AFN)

Los AFN son una extensión de los autómatas finitos deterministas. Permiten que de cada nodo del diagrama de estados salga un número de transiciones mayor o menor que $|\Sigma|$. Se puede permitir que falte la transición correspondiente a alguno de los símbolos del alfabeto, o bien que existan transiciones que salgan del mismo estado con las mismas etiquetas o con la palabra vacía (transiciones $\epsilon$).

Un AFN se define como una quíntupla:

$$M = (K, \Sigma, \Delta, q_0, F)$$

Donde $K, \Sigma, q_0$ y $F$ tienen el mismo significado que para el caso de los autómatas determinísticos. La diferencia radica en $\Delta$, denominada la relación de transición, que es un subconjunto finito de $K \times \Sigma^* \times K$.

El Autómata de Pila (AP) y su Funcionamiento

El Autómata de Pila (AP) es inherentemente un dispositivo no determinista. Su versión determinista solo acepta un subconjunto de los Lenguajes Libres de Contexto (LLC). Este subconjunto es crucial, ya que incluye la sintaxis de la mayoría de los lenguajes de programación.

Características y Estructura del AP

El AP es esencialmente un Autómata Finito (AF) complementado con un almacenamiento auxiliar denominado pila.

• Principio de Operación: Su funcionamiento se basa en el principio LIFO (Last In, First Out): el último carácter almacenado en la pila es el primero en salir.
• Tope de la Pila: El tope de la pila (el extremo por donde entran o salen los caracteres) puede ser modificado durante la operación.
• Estado Inicial: Al iniciar su funcionamiento, la pila del AP se encuentra vacía.