Autómata de empuje empotrado

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 gramáticas sensibles al contexto y libres de 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 anidados 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 un papel importante en el refinamiento de la jerarquía de Chomsky . Por tanto, se pueden definir varias subgramáticas, como la gramática indexada lineal . ^{[2] Las} EPDA también están comenzando a desempeñar un papel importante en el procesamiento del lenguaje natural.

Si bien los lenguajes naturales se han analizado tradicionalmente utilizando gramáticas libres de contexto (ver gramática transformacional-generativa y lingüística computacional ), este modelo no funciona bien para idiomas con dependencias cruzadas, como el holandés, situaciones para las que una EPDA es adecuada. 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 incrustada . Cada pila contiene elementos del alfabeto de pila , por lo que definimos un elemento de una pila por , donde la estrella es el cierre de Kleene del alfabeto.${\displaystyle \,\Gamma }$${\displaystyle \,\sigma _{i}\in \Gamma ^{*}}$

Cada pila se puede definir en términos de sus elementos, por lo denotamos la ésimo de pila en el autómata mediante un símbolo de la doble daga: , ^{[ aclaración necesaria ]} donde sería el siguiente símbolo accesible en la pila. La pila incrustada de pilas puede, por lo tanto, 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 septuple (7-tuple)

${\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 de inicio ;
• ${\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 empujarán y colocarán en la pila incrustada , el empuje y el estallido 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 incrustada se empuja y se abre, la pila actual se devuelve opcionalmente a la pila incrustada , y cualquier otra pila que se desee se coloca encima de ella, siendo la última pila de la que se lee en la siguiente iteración . Por lo tanto, las pilas se pueden colocar tanto por encima como por debajo de la pila actual.

Una configuración dada está definida 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, los s son las pilas en la pila incrustada , con la pila actual, y para una cadena de entrada , es la parte de la cadena ya procesada por la máquina y es la parte que se procesará, con su cabeza siendo el símbolo actual leído. Tenga en cuenta 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, de lo contrario, 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] Sección 7, p. 23-25.

k -orden EPDA y la jerarquía de Weir

Esta sección puede requerir una limpieza para cumplir con los estándares de calidad de Wikipedia . El problema específico es: es necesario reescribir en base a Kallmeyer p. 199 . Si puede, ayude a mejorar esta sección . ( Agosto de 2014 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

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

A continuación se muestran algunas de las propiedades de los lenguajes de Level- k en la jerarquía:

• Los idiomas de Level- k están contenidos correctamente en la  clase de idiomas de Level- ( k + 1)
• Los idiomas de nivel k se pueden analizar a tiempo${\displaystyle O(n^{3\cdot 2^{k-1}})}$
• El nivel k contiene el idioma , 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 idioma , 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  > 1 pequeño ) a las condiciones de los lenguajes levemente sensibles al contexto impuestas por Joshi, y a medida que k crece, la clase de lenguaje se vuelve, en cierto sentido, menos sensible al contexto.

Ver también

• gramática categorial combinatoria

Referencias

1. Vijay-Shanker, K. (enero de 1988). "Un estudio de gramáticas contiguas a los árboles" . Doctor. Tesis . Universidad de Pensilvania .
2. Weir, David J. (1994). "Pushdowns lineales iterados" (PDF) . Inteligencia computacional . 10 (4): 431–439. doi : 10.1111 / j.1467-8640.1994.tb00007.x . Consultado el 20 de octubre de 2012 .
3. Joshi, Aravind K .; Yves Schabes (1997). "Gramáticas adyacentes al árbol" (PDF) . Manual de lenguajes formales . Saltador. 3 : 69-124. doi : 10.1007 / 978-3-642-59126-6_2 . ISBN  978-3-642-63859-6. Consultado el 7 de febrero de 2014 .
4. Weir, DJ (1992), "Una jerarquía geométrica más allá de los lenguajes libres de contexto", Informática teórica , 104 (2): 235-261, doi : 10.1016 / 0304-3975 (92) 90124-X .
5. Nabil Anton Khabbaz (1972). Lenguajes libres de contexto generalizados (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 .

Otras lecturas

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