Autómata con pila

De Wikipedia, la enciclopedia libre

Un autómata con pila o autómata a 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 a pila pertenece al grupo de los lenguajes de contexto libre en la clasificación de la Jerarquía de Chomsky.

[editar] Definición formal

Formalmente, un autómata con pila puede ser descrito como una séptupla $M = (S,Σ,Γ,δ, s, Z, F)$ donde:

Σ y $Γ$ son alfabetos de entrada, de la cadena y de la pila respectivamente;
S un conjunto de estados;
$\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 (s, a, Z) = \{ (s_1, \gamma_1), (s_2, \gamma_2), \ldots, (s_n, \gamma_n) \},$ con $s, p_i \in Q, a \in (\Sigma \cup \{ \epsilon \} ), \gamma_i \in \Gamma$ es la siguiente:

Cuando el estado del autómata es $s$ , 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 $Z$ , se realizan las siguientes acciones:

Si $a \in \Sigma$ , es decir no es la palabra vacía, se avanza una posición la cabeza lectora para inspeccionar el siguiente símbolo.
Se elimina el símbolo Z de la pila del autómata.
Se selecciona un par $(p i,γ i)$ de entre los existentes en la definición de $δ(s, A, Z)$ , la función de transición del autómata.
Se apila la cadena $\gamma_i = A_1 A_2 \ldots A_k$ en la pila del autómata, quedando el símbolo $A 1$ en la cima de la pila.
Se cambia el control del autómata al estado $p i$ .

[editar] Ejemplo

Sea el siguiente lenguaje libre del contexto $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,θ,ρ)$

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 $ε$ se extrae de la cima de la pila. Entonces, el estado del automata 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.

[editar] Autómata determinista

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 $s Z$ , 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 $ε$ , 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.

Categoría: Lenguajes formales

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Autómata con pila

De Wikipedia, la enciclopedia libre

[editar] Definición formal

[editar] Ejemplo

[editar] Autómata determinista

Views

Navegación

Buscar

En otros idiomas