Autómata de pila integrado

Un autómata de pila embebido ( EPDA ) es un modelo computacional para analizar lenguajes generados por gramáticas de adjunción de árboles (TAG). Es similar al autómata de pila para el análisis de gramáticas libres de contexto , pero en lugar de usar una pila simple para almacenar símbolos, utiliza una pila de pilas iteradas que almacenan símbolos, lo que confiere a las TAG una capacidad generativa intermedia entre gramáticas libres de contexto y sensibles al contexto , o un subconjunto de gramáticas ligeramente sensibles al contexto . Los autómatas de pila embebidos no deben confundirse con los autómatas de pila anidados, que poseen mayor capacidad computacional.

Las EPDA fueron descritas por primera vez por K. Vijay-Shanker en su tesis doctoral de 1988. ^{[ 1 ]} Desde entonces, se han aplicado a descripciones más completas de clases de gramáticas ligeramente sensibles al contexto y han desempeñado un papel importante en el refinamiento de la jerarquía de Chomsky . De este modo, se pueden definir varias subgramáticas, como la gramática indexada lineal . ^{[ 2 ]}

Si bien las lenguas naturales se han analizado tradicionalmente utilizando gramáticas libres de contexto (véase gramática transformacional-generativa y lingüística computacional ), este modelo no funciona bien para lenguas con dependencias cruzadas, como el neerlandés, situaciones para las que un EPDA resulta muy adecuado. Un análisis lingüístico detallado está disponible en Joshi, Schabes (1997). ^{[ 3 ]}

Un EPDA es una máquina de estados finitos con un conjunto de pilas a las que se puede acceder a través de la pila integrada . Cada pila contiene elementos del alfabeto de pila.${\displaystyle \,\Gamma }$y así definimos un elemento de una pila mediante${\displaystyle \,\sigma _{i}\in \Gamma ^{*}}$donde la estrella es el cierre de Kleene del alfabeto.

Cada pila se puede definir entonces en términos de sus elementos, por lo que denotamos la${\displaystyle \,j}$la pila en el autómata usando un símbolo de doble daga:${\displaystyle \,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}}$, dónde${\displaystyle \,\sigma _{j,k}}$sería el siguiente símbolo accesible en la pila. La pila incrustada de${\displaystyle \,m}$Las pilas pueden denotarse de la siguiente manera:${\displaystyle \,\{\Upsilon _{j}\}=\{\ddagger \sigma _{m},\ddagger \sigma _{m-1},\ldots ,\ddagger \sigma _{1}\}\in (\ddagger \Gamma ^{+})^{*}}$.

Definimos un EPDA mediante la séptima (séptima tupla)

${\displaystyle \,M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Q_{\textrm {F}},\sigma _{0})}$dónde

• ${\displaystyle \,Q}$es un conjunto finito de estados ;
• ${\displaystyle \,\Sigma }$es el conjunto finito del alfabeto de entrada ;
• ${\displaystyle \,\Gamma }$es el alfabeto de pila finito ;
• ${\displaystyle \,q_{0}\in Q}$es el estado inicial ;
• ${\displaystyle \,Q_{\textrm {F}}\subseteq Q}$es el conjunto de estados finales ;
• ${\displaystyle \,\sigma _{0}\in \Gamma }$es el símbolo de pila inicial
• ${\displaystyle \,\delta :Q\times \Sigma \times \Gamma \rightarrow S}$es la función de transición , donde${\displaystyle \,S}$son subconjuntos finitos de${\displaystyle \,Q\times (\ddagger \Gamma ^{+})^{*}\times \Gamma ^{*}\times (\ddagger \Gamma ^{+})^{*}}$.

Así, la función de transición toma un estado, el siguiente símbolo de la cadena de entrada y el símbolo superior de la pila actual, y genera el siguiente estado, las pilas que se insertarán y extraerán de la pila incrustada , la inserción y extracción de la pila actual, y las pilas que se considerarán las pilas actuales en la siguiente transición. De forma más conceptual, la pila incrustada se inserta y extrae, la pila actual se inserta opcionalmente de nuevo en la pila incrustada , y cualquier otra pila que se desee se inserta encima de esta, siendo la última pila la que se leerá en la siguiente iteración. Por lo tanto, las pilas se pueden insertar tanto por encima como por debajo de la pila actual.

Una configuración dada se define por

${\displaystyle \,C(M)=\{q,\Upsilon _{m}\ldots \Upsilon _{1},x_{1},x_{2}\}\in Q\times (\ddagger \Gamma ^{+})^{*}\times \Sigma ^{*}\times \Sigma ^{*}}$

dónde${\displaystyle \,q}$es el estado actual, el${\displaystyle \,\Upsilon }$s son las pilas en la pila incrustada , con${\displaystyle \,\Upsilon _{m}}$la pila actual y para una cadena de entrada${\displaystyle \,x=x_{1}x_{2}\in \Sigma ^{*}}$,${\displaystyle \,x_{1}}$es la porción de la cadena ya procesada por la máquina y${\displaystyle \,x_{2}}$es la porción a procesar, siendo su cabeza el símbolo leído actualmente. Tenga en cuenta que la cadena vacía${\displaystyle \,\epsilon \in \Sigma }$se define implícitamente como un símbolo de terminación, donde si la máquina está en un estado final cuando se lee la cadena vacía, se acepta toda la cadena de entrada , y si no, se rechaza . Dichas cadenas aceptadas son elementos del lenguaje.

${\displaystyle \,L(M)=\left\{x|\{q_{0},\Upsilon _{0},\epsilon ,x\}\rightarrow _{M}^{*}\{q_{\textrm {F}},\Upsilon _{m}\ldots \Upsilon _{1},x,\epsilon \}\right\}}$

dónde${\displaystyle \,q_{\textrm {F}}\in Q_{\textrm {F}}}$y${\displaystyle \,\rightarrow _{M}^{*}}$define la función de transición que se aplica tantas veces como sea necesario para analizar la cadena.

También se puede encontrar una descripción informal de EPDA en Joshi, Schabes (1997), ^{[ 3 ]} Sect.7, págs.  23-25.

David J. Weir definió una jerarquía de lenguajes definida con mayor precisión que corresponde a la clase ligeramente sensible al contexto. ^{[ 4 ]} Basada en el trabajo de Nabil A. Khabbaz, ^{[ 5 ] [ 6 ]} la jerarquía de lenguajes de control de Weir es una jerarquía de contención de un conjunto contable de clases de lenguajes donde el Nivel 1 se define como libre de contexto, y el Nivel 2 es la clase de adjunción de árboles y las otras tres gramáticas.

A continuación se presentan algunas de las propiedades de los lenguajes de nivel k en la jerarquía:

• Los lenguajes de nivel k están contenidos propiamente en la clase de lenguaje de nivel ( k  +  1).
• Los lenguajes de nivel k se pueden analizar en${\displaystyle O(n^{3\cdot 2^{k-1}})}$tiempo
• El nivel k contiene el lenguaje${\displaystyle \{a_{1}^{n}\dotso a_{2^{k}}^{n}|n\geq 0\}}$pero no${\displaystyle \{a_{1}^{n}\dotso a_{2^{k+1}}^{n}|n\geq 0\}}$
• El nivel k contiene el lenguaje${\displaystyle \{w^{2^{k-1}}|w\in \{a,b\}^{*}\}}$pero no${\displaystyle \{w^{2^{k-1}+1}|w\in \{a,b\}^{*}\}}$

Esas propiedades se corresponden bien (al menos para valores pequeños de k  >  1) con las condiciones de los lenguajes ligeramente sensibles al contexto impuestas por Joshi, y a medida que k aumenta, la clase de lenguajes se vuelve, en cierto sentido, menos sensible al contexto.

• Gramática categorial combinatoria

• Laura Kallmeyer (2010). Análisis sintáctico más allá de las gramáticas libres de contexto . Springer Science & Business Media. ISBN 978-3-642-14846-0.