Automata Lineal con Frontera

La máquina que puede reconocer lenguajes dependiente del contexto se denomina Autómata Lineal con Frontera (ALF); sin embargo, no se ahondará con ejemplo ya que se optará con el Autómata de Doble Pila (ADP) para reconocer a estos lenguajes. Lo anterior es por una razón didáctica, ya que el funcionamiento de los ALF están más cercanos a la MT que se verá en las siguientes secciones; mientras que ADP resultará más poderoso que un ALF pero su funcionamiento relaciona mejor con AP.

ALF #

Un Autómata de Lineal con Frontera (ALF) es una tupla \((Q,\Sigma,\Gamma,q_0,B,A, \delta )\) donde:
  • \(Q\) es un conjunto de estados finitos
  • \(\Sigma\) es un alfabeto de símbolos terminales
  • \(\Gamma\) es un alfabeto de la cinta tal que \(\Sigma \subset \Gamma \)
  • \(q_0\) es un estado que denominaremos inicial donde \(q_0 \in Q\)
  • \(B\) es un símbolo de espacio en blanco
  • \(A\) es un conjunto de estados que denominaremos finales donde \(A \subset Q\)
  • \(\delta\) es una función de transición que cumple con:
\[\delta:Q \times (\Gamma\cup \{<, >\}) \rightarrow Q \times (\Gamma\cup \{<, >\}) \times \{left,right\} \]

Donde < y > son marcas sobre la cinta que marcan el final de esta; y left y right son acciones de moverse una celda a la izquierda y a la derecha respectivamente.

Lo que sabemos #

Con lo dicho para ALF esto es lo que sabemos:

Lenguaje Gramática Máquina Ejemplo
?? ?? Autómata de Doble Pila ??
Lenguaje Dependientes del Contexto \( \gamma A \beta \rightarrow \gamma \alpha \beta \) Autómata Lineal con Frontera \( a^nb^nc^n \)
Lenguaje Independiente del Contexto \( A \rightarrow \alpha \) Autómata de Pila \( a^nb^n \)
Lenguaje Regular \( A \rightarrow bC | d \) AF, AFND y AFND-ε \( a^n \)
comments powered by Disqus