Autómata con pilas.
- No podemos representarlo con un autómata finito
- Controlar la cantidad que ingresan con un autómata finito no es posible
- Necesitamos una estructura adicional para controlar cuántas letras van ingresando.
- Una memoria adicional. Implementada con la estructura de pila (estructura de tipo pila)
Cómo usar la pila para reconocer ,
- Elegir los símbolos de la pila
- Estrategia para apilar (push)
- Estrategia para desapilar (pop)
- Condiciones de aceptación
-
Ya no trabajamos con un elemento, trabajamos con 3 elementos.
- Se especifica el símbolo de entrada
- Especifico el símbolo con el cual ese elemento que ingreso, lo ingreso en la pila
- Elemento que voy a tomar para sacar de la pila Si no saco o meto nada, entonces uso el símbolo de la palabra vacía
-
Los AP pertenecen a los lenguajes independientes del contexto y ocupan una posición intermedia entre los AF y las máquinas de Turing, los AP responden al procedimiento LIFO
-
Aplicaciones
- Los AP pueden describir la sintaxis de muchos lenguajes de programación.
- Análisis de clases gramaticales.
- Análisis de cadenas, palabras, oraciones.
-
Características
- Flujo de entrada y mecanismo de control.
- Estado inicial y al menos uno de aceptación.
- Existe una pila para almacenar información que puede utilizarse posteriormente.
Definición formal de un autómata a pila
- : Conjunto de finito de estados
- : Conjunto finito de símbolos de entrada
- Alfabeto de pila finito
- Función de transición
- Estado inicial
- Fondo de la pila
- Conjunto de estados de aceptación