Autómata pushdown integrado

Un autómata pushdown incorporado o EPDA es un modelo computacional para analizar lenguajes generados por gramáticas contiguas 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, dando a los TAG una capacidad generativa entre gramáticas libres de contexto y 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 anidados que tienen más potencia computacional. ^{[ cita necesaria ]}

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 . 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 libres de contexto (ver gramática generativa transformacional y lingüística computacional ), este modelo no funciona bien para lenguajes con dependencias cruzadas, como el holandés, situaciones para las cuales 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 integrada . Cada pila contiene elementos del alfabeto de la 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 ^{*}}$

Luego, cada pila se puede definir en términos de sus elementos, por lo que denotamos la enésima pila en el autómata usando un símbolo de doble daga: , ^{[ se necesita aclaración ]} donde estaría el siguiente símbolo accesible en la pila. La pila de pilas incrustada puede, por tanto, denotarse por . ^{[ se necesita aclaración ]} ${\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 la séptupla (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 la pila inicial
• ${\displaystyle \,\delta :Q\times \Sigma \times \Gamma \rightarrow S}$es la función de transición , donde hay 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 colocarán en la pila incrustada , el empuje y la extracción de la pila actual. y las pilas que se considerarán las pilas actuales en la próxima transición. Más conceptualmente, la pila incrustada se empuja y se extrae, la pila actual se vuelve a colocar opcionalmente en la pila incrustada y cualquier otra pila que se desee se coloca encima de ella, siendo la última pila la que se lee en la siguiente iteración. . Por lo tanto, las pilas se pueden empujar 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 está el estado actual, los 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, con su cabeza siendo se lee el símbolo actual. 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, si no, se rechaza . Estas 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.

k-orden EPDA y la jerarquía de Weir

David J. Weir definió una jerarquía de lenguajes definida con mayor precisión que corresponden 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 lenguaje ^{[ aclarar ]} donde el Nivel 1 se define como libre de contexto y el Nivel -2 es la clase de árbol contiguo y las otras tres gramáticas.

Las siguientes son algunas de las propiedades de los lenguajes de nivel k en la jerarquía:

• Los idiomas de nivel k están contenidos correctamente en la clase de idioma 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 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 se corresponden bien (al menos para k  > 1 pequeño) con 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 árboles". Doctor. Tesis . Universidad de Pennsylvania .
2. Weir, David J. (1994). "Ejecuciones iteradas lineales" (PDF) . Inteligencia Computacional . 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 Schábes (1997). "Gramáticas contiguas a árboles" (PDF) . Manual de lenguajes formales . vol. 3. Saltador. págs. 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 generalizados libres de contexto (Ph.D.). Universidad de Iowa.
6. Nabil Anton Khabbaz (1974). "Una jerarquía geométrica de lenguas". J. Computación. Sistema. Ciencia . 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 . Medios de ciencia y negocios de Springer. ISBN 978-3-642-14846-0.