Autómata pushdown integrado

Un autómata pushdown integrado o EPDA es un modelo computacional para analizar lenguajes generados por gramáticas adyacentes a árboles (TAG). Es similar al autómata pushdown de análisis de gramática libre de contexto , pero en lugar de usar una pila simple para almacenar símbolos, tiene una pila de pilas iteradas que almacenan símbolos, lo que le da a los TAG una capacidad generativa entre las gramáticas libres de contexto y las gramáticas sensibles al contexto , o un subconjunto de gramáticas ligeramente sensibles al contexto . Los autómatas pushdown integrados no deben confundirse con los autómatas de pila anidada que tienen más poder computacional. ^{[ cita requerida ]}

Historia y aplicaciones

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 tenido papeles importantes 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 los lenguajes naturales se han analizado tradicionalmente utilizando gramáticas independientes del contexto (ver gramática transformacional-generativa y lingüística computacional ), este modelo no funciona bien para lenguajes con dependencias cruzadas, como el holandés, situaciones para las cuales un EPDA es adecuado. Un análisis lingüístico detallado está disponible en Joshi, Schabes (1997). ^[3]

Teoría

Una 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 incorporada . Cada pila contiene elementos del alfabeto de pila , por lo que definimos un elemento de una pila como , donde la estrella es el cierre de Kleene del alfabeto. ${\displaystyle \,\Gamma }$ ${\displaystyle \,\sigma _{i}\in \Gamma ^{*}}$

Cada pila puede definirse en términos de sus elementos, por lo que denotamos la pila n. º en el autómata utilizando un símbolo de doble daga: , ^{[ aclaración necesaria ]} donde sería el siguiente símbolo accesible en la pila. La pila de pilas incrustada puede denotarse por . ^{[ aclaración necesaria ]} ${\displaystyle \,j}$ ${\displaystyle \,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}}$ ${\displaystyle \,\sigma _{j,k}}$ ${\displaystyle \,m}$ ${\displaystyle \,\{\Upsilon _{j}\}=\{\ddagger \sigma _{m},\ddagger \sigma _{m-1},\ldots ,\ddagger \sigma _{1}\}\in (\ddagger \Gamma ^{+})^{*}}$

Definimos una EPDA por el séptuplo (7-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 finita ;
• ${\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 son subconjuntos finitos de . ${\displaystyle \,S}$ ${\displaystyle \,Q\times (\ddagger \Gamma ^{+})^{*}\times \Gamma ^{*}\times (\ddagger \Gamma ^{+})^{*}}$

Por lo tanto, 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 incorporada , 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 manera más conceptual, la pila incorporada se inserta y extrae, la pila actual se inserta opcionalmente de nuevo en la pila incorporada y cualquier otra pila que se desee se inserta encima de esa, siendo la última pila la que se lea 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 ^{*}}$

donde es el estado actual, las s son las pilas en la pila incrustada , con la pila actual, y para una cadena de entrada , es la porción de la cadena ya procesada por la máquina y es la porción a procesar, siendo su cabeza el símbolo actual leído. Nótese que la cadena vacía 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 . Tales cadenas aceptadas son elementos del lenguaje ${\displaystyle \,q}$ ${\displaystyle \,\Upsilon }$ ${\displaystyle \,\Upsilon _{m}}$ ${\displaystyle \,x=x_{1}x_{2}\in \Sigma ^{*}}$ ${\displaystyle \,x_{1}}$ ${\displaystyle \,x_{2}}$ ${\displaystyle \,\epsilon \in \Sigma }$

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

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

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

a-Orden EPDA y la jerarquía de Weir

David J. Weir definió una jerarquía más precisa de lenguajes que corresponden a la clase ligeramente sensible al contexto. ^[4] Basado en el trabajo de Nabil A. Khabbaz, ^{[5] [6]} La jerarquía de lenguaje de control de Weir es una jerarquía de contención de un conjunto contable de clases de lenguaje ^{[ aclarar ]} donde el Nivel 1 se define como libre de contexto, y el Nivel 2 es la clase adyacente al árbol 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 idiomas de nivel k están contenidos adecuadamente en la clase de idiomas de nivel ( k  + 1)
• Los idiomas de nivel k se pueden analizar en el tiempo ${\displaystyle O(n^{3\cdot 2^{k-1}})}$
• El nivel k contiene el lenguaje , pero no ${\displaystyle \{a_{1}^{n}\dotso a_{2^{k}}^{n}|n\geq 0\}}$ ${\displaystyle \{a_{1}^{n}\dotso a_{2^{k+1}}^{n}|n\geq 0\}}$
• El nivel k contiene el lenguaje , pero no ${\displaystyle \{w^{2^{k-1}}|w\in \{a,b\}^{*}\}}$ ${\displaystyle \{w^{2^{k-1}+1}|w\in \{a,b\}^{*}\}}$

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

Véase también

• gramática categorial combinatoria

Referencias

1. Vijay-Shanker, K. (enero de 1988). "Un estudio de gramáticas contiguas a árboles". Tesis doctoral . Universidad de Pensilvania .
2. Weir, David J. (1994). "Linear Iterated Pushdowns" (PDF) . Computational Intelligence . 10 (4): 431–439. doi :10.1111/j.1467-8640.1994.tb00007.x. S2CID  205570628 . Consultado el 20 de octubre de 2012 .
3. Joshi, Aravind K.; Yves Schabes (1997). "Gramáticas contiguas a árboles" (PDF) . Manual de lenguajes formales . Vol. 3. Springer. págs. 69–124. doi :10.1007/978-3-642-59126-6_2. ISBN . 978-3-642-63859-6. Recuperado el 7 de febrero de 2014 .
4. Weir, DJ (1992), "Una jerarquía geométrica más allá de los lenguajes libres de contexto", Theoretical Computer Science , 104 (2): 235–261, doi :10.1016/0304-3975(92)90124-X.
5. Nabil Anton Khabbaz (1972). Lenguajes generalizados libres de contexto (Ph.D.). Universidad de Iowa.
6. Nabil Anton Khabbaz (1974). "Una jerarquía geométrica de lenguajes". J. Comput. Syst. Sci . 8 (2): 142–157. doi :10.1016/s0022-0000(74)80052-8.

Lectura adicional

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