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:
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 \) |