palabra anidada

---

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 aceptores 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 aceptados por autómatas de palabras anidadas finitas dan la clase delenguajes visiblemente pushdown . La última clase de lenguaje se encuentra propiamente entre los lenguajes regulares y los lenguajes libres de contexto deterministas . Desde su introducción en 2004, estos conceptos han dado lugar a muchas investigaciones en esa área. ^[1]

Para definir palabras anidadas , primero defina relaciones coincidentes . Para un entero no negativo , la notación denota el conjunto , con el caso especial .${\ estilo de visualización \ ell}$${\ estilo de visualización [\ ell]}$${\displaystyle \{1,2,\ldots,\ell -1,\ell \}}$${\ estilo de visualización [0] = \ conjunto vacío}$

Una relación de concordancia ↝ de longitud es un subconjunto de tal que:${\displaystyle \ell \geq 0}$${\displaystyle \{-\infty ,1,2,\ldots ,\ell -1,\ell \}\times \{1,2,\ldots ,\ell -1,\ell ,\infty \}}$

Una palabra anidada de longitud sobre un alfabeto Σ es un par ( w ,↝), donde w es una palabra, o cadena , de longitud sobre Σ y ↝ es una relación coincidente de longitud .${\displaystyle \ell }$${\displaystyle \ell }$${\displaystyle \ell }$

---