En informática , más específicamente en autómatas y teoría del lenguaje formal , las palabras anidadas son un concepto propuesto por Alur y Madhusudan como una generalización conjunta de palabras , como se usa tradicionalmente para modelar estructuras ordenadas linealmente , y de árboles ordenados sin clasificar , como se usa tradicionalmente para modelar. estructuras jerárquicas. Los aceptadores de estado finito para palabras anidadas, los llamados autómatas de palabras anidadas , dan una generalización más expresiva de autómatas finitos en palabras. Las codificaciones lineales de lenguajes aceptadas por autómatas de palabras finitas anidadas dan la clase deidiomas visiblemente pushdown . La última clase de lenguaje se encuentra propiamente entre los lenguajes regulares y los lenguajes deterministas libres de contexto . Desde su introducción en 2004, estos conceptos han provocado mucha investigación en esa área. [1]
Definicion formal
Para definir palabras anidadas , primero defina relaciones de coincidencia . Para un número entero no negativo , la notación denota el conjunto , con el caso especial .
Una relación de coincidencia ↝ de longitud es un subconjunto de tal que:
- todos los bordes de anidamiento están hacia adelante, es decir, si i ↝ j entonces i < j ;
- los bordes de anidamiento nunca tienen una posición finita en común, es decir, para −∞ < i <∞ , hay como máximo una posición h tal que h ↝ i , y hay como máximo una posición j tal que i ↝ j ; y
- Los bordes de anidamiento nunca se cruzan, es decir, no hay i < i ′ ≤ j < j ′ tal que tanto i ↝ j como i ′ ↝ j ′ .
Una posición i se conoce como
- una posición de llamada , si i ↝ j para algunos j ,
- una llamada pendiente si yo ↝ ∞,
- una posición de retorno , si h ↝ i por algún h ,
- una devolución pendiente si −∞ ↝ i , y
- una posición interna en todos los casos restantes.
Una palabra anidada de longitudsobre un alfabeto Σ es un par ( w , ↝), donde w es una palabra o cadena de longitud sobre Σ y ↝ es una relación de coincidencia de longitud .
Codificación de palabras anidadas en palabras ordinarias
Palabras anidadas sobre el alfabeto se puede codificar en palabras "ordinarias" sobre el alfabeto etiquetado , en el que cada símbolo a de Σ tiene tres contrapartes etiquetadas: el símbolo ⟨a para codificar una posición de llamada en una palabra anidada etiquetada con a , el símbolo a⟩ para codificar una posición de retorno etiquetada con a , y finalmente el símbolo a sí mismo para que representa una posición interna etiquetada con a . Más precisamente, sea φ la función que asigna palabras anidadas sobre Σ a palabras sobre tal que cada palabra anidada (, ↝) se asigna a la palabra , donde la letra es igual a ⟨a , a , y a⟩ , siy i es A (posiblemente en espera) posición llamada, una posición interna, y una (posiblemente en espera) posición de retorno, respectivamente.
Ejemplo
A modo de ilustración, sea n = ( w , ↝) la palabra anidada sobre un alfabeto ternario con w = abaabccca y una relación coincidente ↝ = {(−∞, 1), (2, ∞), (3,4), (5 , 7), (8, ∞) }. Entonces su codificación como palabra lee como φ ( n ) = un ⟩⟨ b ⟨ aa ⟩⟨ bcc ⟩⟨ ca .
Autómatas
Autómata de palabras anidadas
Un autómata de palabras anidadas tiene un número finito de estados y funciona casi de la misma manera que un autómata finito determinista en cadenas clásicas: un autómata finito clásico lee la palabra de entradade izquierda a derecha, y el estado del autómata después de leer la j- ésima letra depende del estado en el que se encontraba el autómata antes de leer .
En un autómata de palabras anidadas, la posición en la palabra anidada (w, ↝) podría ser una posición de retorno; si es así, el estado después de leerno solo dependerá del estado lineal en el que se encontraba el autómata antes de leer, sino también en un estado jerárquico propagado por el autómata en el momento en que se encontraba en la posición de llamada correspondiente. En analogía con los lenguajes regulares de palabras, un conjunto L de palabras anidadas se llama regular si es aceptado por algún autómata de palabras anidadas (de estado finito).
Autómata de empuje visible
Los autómatas de palabras anidadas son un modelo de autómatas que aceptan palabras anidadas. Existe un modelo de autómata equivalente que opera con palabras (ordinarias). Es decir, la noción de un autómata de empuje visible determinista es una restricción de la noción de un autómata de empuje determinista .
Siguiendo a Alur y Madhusudan, [2] un autómata determinista visiblemente pushdown se define formalmente como una tupla de 6 dónde
- es un conjunto finito de estados ,
- es el alfabeto de entrada , que, en contraste con el de los autómatas pushdown ordinarios, está dividido en tres conjuntos, , y . El alfabetodenota el conjunto de símbolos de llamada ,contiene los símbolos de retorno y el conjuntocontiene los símbolos internos ,
- es un conjunto finito que se llama alfabeto de pila , que contiene un símbolo especial que denota la pila vacía,
- es la función de transición , que se divide en tres partes correspondientes a las transiciones de llamada, las transiciones de retorno y las transiciones internas, a saber
- , la función de transición de llamada
- , la función de transición de retorno
- , la función de transición interna ,
- es el estado inicial , y
- es el conjunto de estados de aceptación .
La noción de cálculo de un autómata de empuje visible es una restricción de la utilizada para los autómatas de empuje . Los autómatas pushdown visibles solo agregan un símbolo a la pila cuando se lee un símbolo de llamada, solo eliminan el elemento superior de la pila al leer un símbolo de retorno y no alteran la pila al leer un evento interno . Un cálculo que termina en un estado de aceptación es un cálculo de aceptación .
Como resultado, un autómata de empuje visible no puede empujar y salir de la pila con el mismo símbolo de entrada. Así el idioma no puede ser aceptado por un autómata visiblemente pushdown para cualquier partición de , sin embargo, hay autómatas pushdown que aceptan este idioma.
Si un idioma sobre un alfabeto etiquetado es aceptado por un autómata determinista visiblemente pushdown, entonces se llama un lenguaje visiblemente pushdown .
Autómatas visiblemente pushdown no deterministas
Los autómatas visiblemente pushdown no deterministas son tan expresivos como los deterministas. Por tanto, uno puede transformar un autómata no determinista visiblemente empujado en uno determinista, pero si el autómata no determinista hubiera estados, el determinista puede tener hasta estados. [3]
Problemas de decisión
Dejar ser del tamaño de la descripción de un autómata , entonces es posible verificar si una palabra n es aceptada por el autómata a tiempo. En particular, el problema de la vacuidad se puede resolver a tiempo.. Si es fijo, es decidible en el tiempo y espacio dónde es la profundidad de n en una visión continua. También es decidible con el espacio. y tiempo , y por un circuito booleano uniforme de profundidad . [2]
Para dos autómatas no deterministas A y B , decidir si el conjunto de palabras aceptadas por A es un subconjunto de la palabra aceptada por B es EXPTIME -completo. También es EXPTIME-complete para averiguar si hay una palabra que no se acepta. [2]
Idiomas
Como muestra la definición de autómatas visiblemente pushdown, los autómatas deterministas visiblemente pushdown pueden verse como un caso especial de autómatas deterministas pushdown ; por lo tanto, el conjunto VPL de idiomas visiblemente pushdown sobreforma un subconjunto del conjunto DCFL de lenguajes deterministas libres de contexto sobre el conjunto de símbolos en. En particular, la función que elimina la relación de coincidencia de las palabras anidadas transforma los lenguajes regulares sobre palabras anidadas en lenguajes libres de contexto.
Propiedades de cierre
El conjunto de idiomas visiblemente pushdown se cierra con las siguientes operaciones: [3]
- establecer operaciones:
- Unión
- intersección
- complemento,
- dando así lugar a un álgebra booleana .
Para la operación de intersección, se puede construir un VPA M simulando dos VPA dados y por una construcción de producto simple ( Alur & Madhusudan 2004 ): Para, asumir se da como . Entonces, para el autómata M , el conjunto de estados es, el estado inicial es , el conjunto de estados finales es , el alfabeto de la pila viene dado por , y el símbolo de pila inicial es .
Si está en estado al leer un símbolo de llamada , luego empuja el símbolo de la pila y va al estado , dónde es el símbolo de la pila empujado por al hacer la transición del estado a al leer la entrada .
Si está en estado al leer un símbolo interno , luego va al estado , cuando sea transiciones de estado a sobre la lectura a .
Si está en estado al leer un símbolo de devolución , luego aparece el símbolo de la pila y va al estado , dónde es el símbolo de la pila que aparece al hacer la transición del estado a al leer .
La exactitud de la construcción anterior se basa fundamentalmente en el hecho de que las acciones de empuje y estallido de las máquinas simuladas y se sincronizan a lo largo de los símbolos de entrada leídos. De hecho, una simulación similar ya no es posible para los autómatas pushdown deterministas , ya que la clase más grande de lenguajes deterministas libres de contexto ya no está cerrada bajo la intersección.
En contraste con la construcción para la concatenación que se muestra arriba, la construcción de complementación para los autómatas de empuje visible es paralela a la construcción estándar [4] para los autómatas de empuje deterministas.
Además, al igual que la clase de lenguajes libres de contexto, la clase de lenguajes visiblemente pushdown se cierra con cierre y reversión de prefijo , por lo tanto también cierre de sufijo.
Relación con otras clases de idiomas
Alur y Madhusudan (2004) señalan que los lenguajes visiblemente pushdown son más generales que los lenguajes entre paréntesis sugeridos en McNaughton (1967) . Como muestran Crespi Reghizzi y Mandrioli (2012) , los lenguajes visiblemente pushdown a su vez están estrictamente contenidos en la clase de lenguajes descritos por gramáticas de precedencia de operadores , que fueron introducidas por Floyd (1963) y disfrutan de las mismas propiedades y características de cierre (ver Lonati et al. (2015) para ω lenguajes y caracterizaciones lógicas y basadas en autómatas). En comparación con las gramáticas conjuntivas , una generalización de gramáticas libres de contexto, Okhotin (2011) muestra que los lenguajes conjuntivos lineales forman una superclase de los lenguajes visiblemente pushdown. La tabla al final de este artículo pone la familia de idiomas visiblemente empujados en relación con otras familias de idiomas en la jerarquía de Chomsky . Rajeev Alur y Parthasarathy Madhusudan [5] [6] relacionaron una subclase de lenguajes de árbol binarios regulares con lenguajes visiblemente pushdown.
Otros modelos de descripción
Gramáticas visiblemente pushdown
Los lenguajes visiblemente pushdown son exactamente los lenguajes que pueden describirse mediante gramáticas visiblemente pushdown . [2]
Las gramáticas visiblemente pushdown se pueden definir como una restricción de las gramáticas libres de contexto . Una gramática G visiblemente pushdown está definida por la tupla de 4 :
dónde
- y son conjuntos finitos disjuntos; cada elementose denomina carácter no terminal o variable . Cada variable representa un tipo diferente de frase o cláusula en la oración. Cada variable define un sub-lenguaje del lenguaje definido por, y los sub-idiomas de es el que no tiene convocatorias ni devoluciones pendientes.
- es un conjunto finito de terminales , disjunto de, que constituyen el contenido real de la oración. El conjunto de terminales es el alfabeto del idioma definido por la gramática..
- es una relación finita de a tal que . Los miembros dese llaman (reescribir) reglas o producciones de la gramática. Hay tres tipos de reglas de reescritura. Para, y
- y si luego y
- y si luego
- es la variable de inicio (o símbolo de inicio ), que se utiliza para representar la oración completa (o programa).
Aquí, el asterisco representa la operación de la estrella de Kleene y es la palabra vacía.
Circuitos booleanos uniformes
El problema de si una palabra de longitud es aceptado por un autómata de palabras anidadas dado se puede resolver mediante circuitos booleanos uniformes de profundidad. [2]
Descripción lógica
Los lenguajes regulares sobre palabras anidadas son exactamente el conjunto de lenguajes descritos por la lógica monádica de segundo orden con dos predicados unarios llamada y retorno , sucesor lineal y la relación de coincidencia ↝. [2]
Ver también
- Comprobación de modelo
Notas
- ^ Resultados de búsqueda de Google Académico para "palabras anidadas" O "visiblemente pushdown"
- ↑ a b c d e f Alur y Madhusudan (2009)
- ↑ a b Alur y Madhusudan (2004)
- ^ Hopcroft y Ullman (1979 , p. 238 f).
- ^ Alur, R .; Madhusudan, P. (2004). "Idiomas visiblemente pushdown" (PDF) . Actas del trigésimo sexto simposio anual ACM sobre teoría de la computación - STOC '04 . págs. 202–211. doi : 10.1145 / 1007352.1007390 . ISBN 978-1581138528. Sección 4, Teorema 5,
- ^ Alur, R .; Madhusudan, P. (2009). "Añadiendo estructura de anidamiento a las palabras" (PDF) . Revista de la ACM . 56 (3): 1–43. CiteSeerX 10.1.1.145.9971 . doi : 10.1145 / 1516512.1516518 . Sección 7
Referencias
- Floyd, RW (julio de 1963). "Análisis sintáctico y precedencia de operadores". Revista de la ACM . 10 (3): 316–333. doi : 10.1145 / 321172.321179 .
- McNaughton, R. (1967). "Gramáticas entre paréntesis". Revista de la ACM . 14 (3): 490–500. doi : 10.1145 / 321406.321411 .
- Alur, R .; Arenas, M .; Barceló, P .; Etessami, K .; Immerman, N .; Libkin, L. (2008). Grädel, Erich (ed.). "Lógicas de primer orden y temporales para palabras anidadas". Métodos lógicos en informática . 4 (4). arXiv : 0811.0537 . doi : 10.2168 / LMCS-4 (4:11) 2008 .
- Crespi Reghizzi, Stefano; Mandrioli, Dino (2012). "La precedencia del operador y la propiedad visiblemente pushdown" (PDF) . Revista de Ciencias de la Computación y Sistemas . 78 (6): 1837–1867. doi : 10.1016 / j.jcss.2011.12.006 . Archivado desde el original (PDF) el 9 de agosto de 2017 . Consultado el 11 de febrero de 2014 .
- Lonati, Violetta; Mandrioli, Dino; Panella, Federica; Pradella, Matteo (2015). "Lenguajes de precedencia del operador: su caracterización lógica y teórico-autómata". Revista SIAM de Computación . 44 (4): 1026–1088. doi : 10.1137 / 140978818 . hdl : 2434/352809 .
- Okhotin, Alexander: Comparación de lenguajes conjuntivos lineales con subfamilias de lenguajes libres de contexto , 37a Conferencia Internacional sobre Tendencias Actuales en Teoría y Práctica de la Ciencia de la Computación (SOFSEM 2011).
- Hopcroft, John E .; Ullman, Jeffrey D. (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas . Addison-Wesley. ISBN 978-0-201-02988-8.
enlaces externos
- Palabras anidadas e idiomas visiblemente pushdown
- Autómatas visiblemente pushdown - Autómatas en palabras anidadas
- clase VPL en el Complexity Zoo