Autómata con pila

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Sistema combinacional Autómata finito Autómata con pila Máquina de Turing Teoría de autómatasTeoría de autómatas.svg
Acerca de esta imagen


Un autómata con pila, autómata a pila o autómata de pila es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce. El lenguaje que reconoce un autómata con pila pertenece al grupo de los lenguajes libres de contexto en la clasificación de la Jerarquía de Chomsky.

Definición formal[editar]

Formalmente, un autómata con pila puede ser descrito como una séptupla  M = (S, \Sigma, \Gamma, \delta, s, Z, F) donde:

  • S un conjunto finito de estados;
  • \Sigma y \Gamma son alfabetos (símbolos de entrada y de la pila respectivamente);
  • \delta: S \times (\Sigma \cup \{\epsilon \} )  \times \Gamma \rightarrow \mathcal{P} ( S \times \Gamma^*)
  • s \in S es el estado inicial;
  • Z\ \in \Gamma es el símbolo inicial de la pila;
  • F \subseteq S es un conjunto de estados de aceptación o finales;


La interpretación de \delta (q, a, b) = \{ (q_1, \gamma_1), (q_2, \gamma_2), \ldots, (q_n, \gamma_n) \}, con q, q_i \in S, a \in (\Sigma \cup \{ \epsilon \} ), b \in \Gamma, y  \gamma_i \in \Gamma^* es la siguiente:

Cuando el estado del autómata es q, el símbolo que la cabeza lectora está inspeccionando en ese momento es a, y en la cima de la pila nos encontramos el símbolo b, se realizan las siguientes acciones:

  • Si  a \in \Sigma, es decir no es la cadena vacía, la cabeza lectora avanza una posición para inspeccionar el siguiente símbolo.
  • Se elimina el símbolo b de la pila del autómata.
  • Se selecciona un par  (q_i, \gamma_i ) de entre los existentes en la definición de \delta(q, a, b), la función de transición del autómata.
  • Se apila la cadena  \gamma_i = c_1 c_2 \ldots c_k, con  c_i \in \Gamma en la pila del autómata, quedando el símbolo c_1 en la cima de la pila.
  • Se cambia el control del autómata al estado q_i.


Funcionamiento[editar]

Los autómatas de pila, en forma similar a como se usan los autómatas finitos, también se pueden utilizar para aceptar cadenas de un lenguaje definido sobre un alfabeto A. Los autómatas de pila pueden aceptar lenguajes que no pueden aceptar los autómatas finitos. Un autómata de pila cuenta con una cinta de entrada y un mecanismo de control que puede encontrarse en uno de entre un número finito de estados. Uno de estos estados se designa como estado inicial, y además algunos estados se llaman de aceptación o finales. A diferencia de los autómatas finitos, los autómatas de pila cuentan con una memoria auxiliar llamada pila. Los símbolos (llamados símbolos de pila) pueden ser insertados o extraídos de la pila, de acuerdo con el manejo last-in-first-out (LIFO). Las transiciones entre los estados que ejecutan los autómatas de pila dependen de los símbolos de entrada y de los símbolos de la pila. El autómata acepta una cadena x si la secuencia de transiciones, comenzando en estado inicial y con pila vacía, conduce a un estado final, después de leer toda la cadena x.[1]

Representación[editar]

Una máquina de este tipo se representa de la siguiente forma

Representacion.gif

Al igual que un autómata finito un autómata de pila cuenta con un flujo de entrada y un flujo de control que puede encontrarse en uno de entre un número finito de estados. Uno de estos estados se designa como el inicial y por lo menos un estado es de aceptación.

La principal diferencia es que los autómatas de pila cuentan con una pila en donde pueden almacenar información para recuperarla más tarde.

Los símbolos que pueden almacenarse en esta pila se conocen como símbolos de pila de la máquina, constituyen un conjunto finito que puede incluir algunos símbolos definiendo el alfabeto de la máquina y quizá algunos símbolos adicionales que se utilizan como marcas internas. Si una máquina inserta un símbolo especial en la pila antes de efectuar algún otro cálculo, entonces ese símbolo en la cima de la pila puede usarse como indicador de pila vacía para cálculos posteriores, dicho símbolo es #.[2]

Ejemplo[editar]

Sea el siguiente LLC  L = \{a^kb^k | k \ge 0 \}; formado por las cadenas  L = \{ \epsilon , ab, aabb, aaabbb, aaaabbbb, \ldots \}

Dicho lenguaje puede ser reconocido por el siguiente autómata con pila:

M = (\{q_0, q_1, q_2, q_3\}, \{a,b\}, \{A,\underline{A}\}, \delta, q_0, \{q_0, q_3 \}),

donde las transiciones son:

\delta(q_0, a, \epsilon) = \{(q_1, \underline{A})\}

\delta(q_1, a, \epsilon) = \{(q_1, \underline{A})\}

\delta(q_1, b, \underline{A}) = \{(q_2, \epsilon)\}

\delta(q_1, b, \underline{A}) = \{(q_3, \epsilon)\}

\delta(q_2, b, \underline{A}) = \{(q_2, \epsilon)\}

\delta(q_2, b, \underline{A}) = \{(q_3, \epsilon)\}

\delta(q, \theta, \rho) = \empty para cualquier (q, \theta, \rho)

El significado de las transiciones puede ser explicado analizando la primera transición:

\delta(q_0, a, \epsilon) = \{(q_1, \underline{A})\}

donde q_0 es el estado actual, a es el símbolo en la entrada y \epsilon se extrae de la cima de la pila. Entonces, el estado del autómata cambia a q_1 y el símbolo \underline{A} se coloca en la cima de la pila.

La idea del funcionamiento del autómata es que al ir leyendo los diferentes símbolos a, estos pasan a la pila en forma de símbolos A. Al aparecer el primer símbolo b en la entrada, se comienza el proceso de desapilado, de forma que coincida el número de símbolos b leídos con el número de símbolos A que aparecen en la pila.

Autómata con pila determinista[editar]

Nótese que, a diferencia de un autómata finito o una máquina de Turing, la definición básica de un autómata con pila es de naturaleza no determinista, pues la clase de los autómatas con pila deterministas, a diferencia de lo que ocurría con aquellos modelos, tiene una potencia descriptiva estrictamente menor. Para calificar a un autómata con pila como determinista deben darse dos circunstancias; en primer lugar, por supuesto, que en la definición de cada componente de la función de transición existan un único elemento lo que da la naturaleza determinista. Pero eso no es suficiente, pues además puede darse la circunstancia de que el autómata esté en el estado  s y en la pila aparezca el símbolo  sZ, entonces, si existe una definición de transición posible para algún símbolo cualquiera  a del alfabeto de entrada, pero, además existe otra alternativa para la palabra vacía  \epsilon, también esto es una forma de no determinismo, pues podemos optar entre leer un símbolo o no hacerlo. Por eso, en autómata determinista no debe existir transición posible con lectura de símbolo si puede hacerse sin ella, ni al contrario.

Para cada q \in Q, Z \in \Gamma, se dé que: \mid \delta(q,\epsilon,Z)\mid + \mid \delta(q,a,Z)\mid \le 1 , para cada a \in \Sigma

Definición[editar]

Un autómata de pila determinista (AFPD) es una 7-upla,

P = (Q, Σ, Г,Δ, q0, T,Z) donde:

  • Q es un conjunto finito de estados.
  • Σ es el alfabeto de entrada.
  • Г es el alfabeto de la pila.
  • q0 є Q es el estado inicial.
  • Z є Г símbolo inicial de la pila.
  • T es subconjunto de Q (conjunto de estados finales).
  • Δ es la función de transición tal que:
         Δ: Q × (Σ U { ε }) × Г → (Q × Г *)

Observación

En un momento, la unidad de control del autómata escanea un símbolo ‘a’ sobre la cinta de entrada y el símbolo ‘s’ en el tope de la pila.

Automata con pila determinista.JPG

Este paso computacional representa: La unidad de control pasa a ‘q0’ y se mueve a la derecha en la cinta de entrada, borra el símbolo ‘s’ del tope, escribe en la cadena y pasa a escanear el nuevo tope.[3]

Autómata con pila no determinista[editar]

Un autómata finito con pila no determinista (AFPN) consta de los mismos parámetros de un AFPD.

P = (Q, Σ, Г, Δ, q0, T,Z):

Donde la función de transición Δ es de la forma:

       Δ: Q × (Σ U { ε }) × Г→ Pf(Q × Г*)

Donde Pf (Q× Г *) es un conjunto de subconjuntos finitos de Q × Г*

Para q є Q, a є Σ U {ε} y s є Г

       Δ (q, a, s) = {(q1, γ1), (q2, γ 2), . . . , (qn, γ n)}

Donde γi є Г*

Ejemplo[editar]

Diseñar un AFPN que acepte el lenguaje \{a^ib^i: i\geq 0\}[4]

Sobre:

Σ = {a, b}

  • Δ (q0, a, Z) = (q0, AZ)
  • Δ (q0, ε, Z) = (q2, Z) (acepta ε)
  • Δ (q0, a, A) = (q0, AA)
  • Δ (q0, b, A) = (q1, ε)
  • Δ (q1, b, A) = (q1, ε)
  • Δ (q1, ε, Z) = (q2, Z)


Ejemplo 1 AFPN.JPG

El no determinismo se da por la presencia simultánea de:

    Δ (q0, a, Z) y Δ (q0, ε, Z)

Véase también[editar]

Referencias[editar]

  1. Libro Teoría de autómatas y lenguajes Formales, paginas 210-211
  2. Curso universidad de Guadalajara [1]
  3. Universidad del Valle, Cursos dictados e información [2]
  4. Universidad del Valle, Ejemplos [3]

Bibliográfica[editar]

  • Teoría de autómatas y lenguajes formales.

Autómatas y complejidad. Kelly Dean Editorial Prentice Hall

  • Introducción a la teoría de autómatas, lenguajes y computación

John E. Hopcroft; Jeffrey D. Ullman Editorial Cecsa

  • Teoría de la computación

J. Gleuu Brokshear Editorial Addison Wesley Iberoamericana

Enlaces externos[editar]