miércoles, 26 de febrero de 2020

Unidad 1 automatas de pila


Autómatas de Pilas
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.

Los autómatas finitos reconocen lenguajes regulares. En cambio, los autómatas con pila sirven para reconocer lenguajes incontextuales.
Un autómata con pila (AP) puede recordar cantidad de información sin límite pero no puede acceder a ella en cualquier orden.
$\displaystyle AP \quad\approx$   AFN-$\displaystyle \lambda +$   pila auxiliar (información potencialmente infinita)

Lenguaje aceptado por un autómata con pila

Hay dos tipos de AP:
  1. Aceptación por estado final
    • $ \vdash_P^*$ : se puede llegar a través de P con 0 o más pasos.
    Siendo

    $\displaystyle P=(Q,\Sigma,\underbrace{\Gamma}_{\mbox{s\'imbolos de la pila}},\delta,q_0,\underbrace{z_0}_{\mbox{s?mbolo inicial de la pila vac\'ia}},F)$

    el lenguaje aceptado por P por estado final es

    $\displaystyle L(P) =\{ w \vert (q_0,w,z_0) \vdash_P^* (q, \lambda, \gamma), q \in F \}$
  2. Aceptación por pila vacíaSiendo

    $\displaystyle P=(Q,\Sigma,\Gamma,\delta,q_0,z_0)$

    el lenguaje acpetado por P por pila vacía es
    $\displaystyle N(P) = \{ w \vert (q_0, w, z_0) \vdash_P^* (q, \lambda, \lambda)\}$

Observaciones

  • Al reconocer por pila vacía, la pila se queda vacía del todo, sin $ z_0$ .
  • $ L(P) \neq N(P)$ . Antes de diseñar un AP, hay que decir si queremos que acepte por estado final o por pila vacía, pues el AP deberá ser distinto.

Ejemplo

$ PAL_{par}$ , con AP por pila vacía

\begin{picture}(60,60)(0,-40) \node[Nmarks=i](q0)(0,0){$q_0$} \node(q1)(30,0){$q... ...in{array}{l} a , a / \lambda \\ b , b / \lambda \\ \end{array}$} \end{picture}

Aceptación por estado final es "equivalente" a aceptación por pila vacía

Th   Si existe un AP $ P$ que reconoce un lenguaje por estado final, entonces existe otro AP $ P$ ' que reconoce el mismo lenguaje por pila vacía:
$\displaystyle L(P) = N(P')$
En general, $ P\neq P'$
En general, $ L(P) \neq N(P')$
Th   Si existe un AP $ P$ que reconoce un lenguaje por pila vacía, entonces existe otro AP $ P'$ que reconoce el mismo lenguaje por estado final:
$\displaystyle N(P) = L(P')$

Traducción pila vacía $ \rightarrow $ estado final

Sea $ P_V$ un AP que acepta por pila vacía
$\displaystyle P_V = (Q, \Sigma, \Gamma, \delta, q_0, z_0) $
entonces diseñamos
$\displaystyle P_F = \big (Q \cup \{q_{0F},q_F\}, \Sigma, \Gamma \cup \{z_{0F}\}, \delta, q_{0F}, z_{0F}, \{q_F\} \big ) $
que acepta por estado final las mismas cadenas que $ P_V$ por pila vacía
  • Nuevo estado inicial: añadir un nuevo símbolo a la pila
  • Procesar como si estuviéramos en $ P_V$
  • Si llegamos a tener $ z_{0F}$ en la cima: $ P_V$ ha vaciado su pila $ \Rightarrow$ debemos aceptar $ \Rightarrow$ transición a $ q_F$

\begin{picture}(60,60)(0,-26) \node[Nmarks=i](q0f)(0,10){$q_{0F}$} \node(q0)(30,... ...awedge[curvedepth=-28,ELside=r](q0,qf){$\lambda, z_{0F} / z_{0F}$} \end{picture}

Traducción estado final $ \rightarrow $ pila vacía

Sea $ P_F$ un AP que acepta por estado final
$\displaystyle P_F = ( Q, \Sigma, \Gamma, \delta, q_0, z_0, F) $
entonces diseñamos
$\displaystyle P_V = \big ( Q \cup \{ q_{0V}, q_{VV} \}, \Sigma, \underbrace{\Gamma \cup \{z_{0V}\}}_{\Gamma_V}, \delta_V, q_{0V}, z_{0V} \big ) $
que acepta el mismo lenguaje pero por pila vacía, donde $ \delta_v$ extiende a $ \delta $ con las transiciones
  • $ (q_{0V}, \lambda, z_{0V}) \rightarrow (q_0, z_0 z_{0V})$
  • $ \forall q \in F, \forall a \in \Gamma_V : (q,\lambda,a) \rightarrow (q_{VV}, \lambda)$
  • $ \forall a \in \Gamma_V : (q_{VV}, \lambda,a) \rightarrow (q_{VV}, \lambda)$
  • Nuevo estado inicial: Meter nuevo símbolo inicial objetivo, para que la pila no se vacíe accidentalmente
  • Nuevo estado "vaciador" $ q_{VV}$ : Vacía la pila sin consumir entradas
  • Desde cada estado de aceptación: Transición al estado "vaciador"
  • Si $ P_F$ aceptaba en $ P_V$ vaciamos la pila y también aceptamos.

\begin{picture}(60,60)(0,-26) \node[Nmarks=i](q0v)(0,10){$q_{0V}$} \node(q0)(30,... ...\drawloop[loopangle=0,ELside=l](qw){$\lambda, \Gamma_V / \lambda$} \end{picture}

Equivalencia entre GI y AP

Th   Dada una GI $ G$ , existe un AP $ P$ que reconoce por pila vacía el mismo lenguaje que genera $ G$ .
Th   Dado un AP P, existe una GI G que genera el mismo lenguaje que reconoce P por pila vacía.
Lógicamente, ambos teoremas también se cumplen para los AP que aceptan por estado final
$\displaystyle GI \rightleftarrows AP$    pila vacía $\displaystyle \rightleftarrows AP$    estado final

De GI a AP

Sea $ G=(\Sigma, V, I, P)$ una GI, entonces el lenguaje que genera es el mismo que reconoce por pila vacía el siguiente AP
$\displaystyle P = \big ( \{q\}, \Sigma, \Sigma \cup V, q, I \big ) $
donde
\begin{displaymath} \begin{array}{l} \forall A \in V : \delta(q,\lambda,A) = \b... ... \in \Sigma : (q,a,a) = \big \{ (q, \lambda)\big\} \end{array}\end{displaymath}

De AP a GI

  • Definir el conjunto de variables con símbolos de la forma $ [pXq]$ : "desde el estado $ p$ se puede ir al estado $ q$ consumiendo $ X$ en la pila, con $ X \in \Gamma$ ".
  • Por cada transición \begin{picture}(60,10)(-10,0) \node(p)(0,0){p} \node(q)(40,0){q} \drawedge(p,q){$a,A/B_1 B_2 \ldots B_m$} \end{picture} introducimos producciones
    $\displaystyle [p A p_m] \rightarrow a [q B_1 p_1 ] [ p_1 B_2 p_2 ] \ldots [p_{m-1} B_m p_m ] $

    para toda secuencia posible de $ m$ estados $ p_1,\ldots,p_m$ .
  • Para todo estado $ q$ del AP creamos la regla $ I \rightarrow [ q_0 Z_0 q ] $ donde $ I$ es el símbolo inicial de la gramática.

Autómatas con pila deterministas (APD)

$\displaystyle APD \subset AP $
Los autómatas con pila deterministas son un subconjunto estricto de los autómatas con pila. Nos interesan porque los analizadores sintácticos suelen ser autómatas con pila deterministas.
Def (Autómata con pila determinista)   Un AP es determinista si en cada situación es posible realizar una única transición y no más.
$\displaystyle P = (Q, \Sigma, \Gamma, \delta, q_0, z_0, F ) $

es determinista si y sólo si
  1. $ \forall q \in Q, \forall a \in \Sigma \cup \{ \lambda \}, \forall x \in \Gamma: \underbrace{\vert\delta(q,a,x)\vert}_{\mbox{n? de situaciones}} \leq 1 $
  2. Si $ \delta(q,a,x)\neq \varnothing$    y $ a \neq \lambda$    entonces $ \delta(q,\lambda,x)=\varnothing$

-
Etiquetas:

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)

Codigo y Video final de la evidencia del Carrito

El carrito pudimos hacerlo con un arduino para quese mueva , nos faltaron sensores pero es lo que pudimos pagar en el video se muestra que q...