Palavra aninhada

Em ciência da computação, mais especificamente nas teorias dos autômatos e de linguagem formal, palavras aninhadas são um conceito proposto por Alur e Madhusudan como uma generalização conjunta de palavras, tradicionalmente usada para modelagem de estruturas linearmente ordenadas e de árvores ordenadas sem classificação, como também utilizadas para modelagem de estruturas hierárquicas. Os aceitadores de estado finito para palavras aninhadas são chamados de autômatos de palavras aninhadas, assim generalizando, de maneira mais expressiva, autômatos finitos não determinísticos sobre palavras. As codificações lineares de linguagens aceitas por autômatos finitos de palavra aninhada resultam em uma classe de linguagem visivelmente de pilha. A última classe de linguagem fica entre linguagens regulares e as linguagens livres de contexto determinísticas. Desde sua introdução, em 2004, esses conceitos têm desencadeado muitas pesquisas na área.

Definição formal

Para definir palavras aninhadas, nós primeiro precisamos definir a relação de correspondência. Como usual, para inteiros não negativos $\ell$, usaremos a notação $[\ell ]$ para denotar o conjunto $\{1,2,\ldots ,\ell -1,\ell \}$, com o caso especial $[0]=\emptyset$.

A relação de correspondência "↝", de tamanho $\ell \geq 0$, é um subconjunto de $\{-\infty ,1,2,\ldots ,\ell -1,\ell \}\times \{1,2,\ldots ,\ell -1,\ell ,\infty \}$, de tal modo que:

1. Todos os extremos aninhados estão à frente, isto é, se i↝j, então i < j;
2. Extremos aninhados nunca têm uma posição finita em comum, isto é, para $-\infty <i<\infty$, existe no máximo uma posição h, de maneira que h↝i, se existe no máximo uma posição j, de forma que i↝j;
3. Extremos aninhados nunca se cruzam, isto é, não podemos encontrar i < i'≤ j < j', de maneira que ambos i↝j e i'↝j'.

$i$ é referido como uma posição de chamada, se i↝j para algum j; como uma chamada pendente, se i↝∞; como um retorno pendente, se h↝i para algum h; e como um "retorno pendente", se -∞↝i.

Uma palavra aninhada de tamanho $\ell$ sobre o alfabeto Σ é um par (w,↝), onde w é a palavra de tamanho $\ell$ sobre Σ (no sentido usual) e "↝" é uma relação de correspondência do tamanho $\ell$.

Codificação de palavras aninhadas em palavras comuns

Palavras aninhadas em um alfabeto

$\Sigma =\{a_{1},a_{2},\ldots ,a_{n}\}$ pode ser codificado em palavras “comuns”, usando um alfabeto “rotulado” ${\hat {\Sigma }}$, em que cada um dos símbolos a de Σ h possui três contrapartes: o símbolo ⟨a que codifica para uma posição chamada por uma palavra aninhada marcada com um a; o símbolo a⟩ para codificar uma posição de retorno marcado com um a; e o símbolo a representando uma posição interna rotulada com um a. Mais precisamente, deixa φ ser uma função de mapeamento aninhado sobre Σ para palavras em ${\hat {\Sigma }}$, de modo que cada palavra aninhada ($w_{1}w_{2}\cdots w_{\ell }$,↝) é mapeada para a palavra $x_{1}x_{2}...x_{\ell }$, onde a letra $x_{i}$ é igual a ⟨a, a, ou a⟩, respectivamente, se $w_{i}=a$ e i é uma chamada de posição, uma posição interna ou uma posição de retorno, respectivamente.

Exemplo

Para a ilustração, deixe n=(w,↝) ser a palavra aninhada em um alfabeto ternário com w=abaabccca e a relação de correspondência ↝ = {(-∞,1),(2,∞),(3,4),(5,7),(8,∞)}. Assim sua codificação como palavra é lida como φ(n) = a⟩⟨b⟨aa⟩⟨bcc⟩⟨ca.

Autômato

Autômato de palavra aninhada

O autômato de palavra aninhada tem finitos números de estado; e opera quase do mesmo jeito que um autômato finito determinístico sobre cadeias clássicas: um clássico autômato finito lê a palavra de entrada $w=w_{1}\cdots w_{\ell }$ da esquerda para a direita, e o estado do autômato depois da leitura da j^a letra $w_{j}$ depende do estado em que o autômato estava antes de ler $w_{j}$.

Em um autômato de palavras aninhadas, a posição $j$ em uma palavra aninhada (w,↝) pode ser uma posição de retorno; se assim, o estado de depois de ler $w_{j}$ não será apenas dependente do ‘’estado linear’’ que o autômato estava antes de ler $w_{j}$, mas também do estado hierárquico propagado pelo autômato no tempo em que ele estava na correspondente posição de chamada. Em analogia às linguagens regulares de palavras, um conjunto ‘’L’’ de palavras aninhadas é chamada regular se for aceito por algum autômato (estado-finito) aninhado.

Autômato visivelmente com pilha

Autômatos de palavras aninhadas são modelos de autômatos aceitantes de palavras aninhadas. Existe um modelo de autômato equivalente operacional em palavras (comuns). Ou seja, a noção de um autômato determinístico visivelmente com pilha é uma restrição da noção de um autômato determinístico com pilha.

Seguindo Alur e Madhusudan, um autômato visivelmente determinístico é formalmente definido como uma 6-tupla$M=(Q,\ {\hat {\Sigma }},\ \Gamma ,\ \delta ,\ q_{0},\ F)$, em que:

• $\,Q$ é um conjunto finito de estados;
• $\,{\hat {\Sigma }}$ é o alfabeto de entrada, o que - em contraste com o dos autômatos de pilha normal - é dividido em três conjuntos: $\Sigma _{c}$, $\Sigma _{r}$, e $\Sigma _{int}$. cO alfabeto $\Sigma _{c}$ indica o conjunto de “símbolos de chamada”; $\Sigma _{r}$ contém os símbolos de retorno; e $\Sigma _{int}$ contém os "símbolos internos";
• $\,\Gamma$ é um conjunto finito, que é o chamado alfabeto de pilha, que contém um símbolo especial $\bot \in \Gamma$, denotando a pilha vazia;
• $\,\delta =\delta _{c}\cup \delta _{r}\cup \delta _{int}$ é a função de transição, que é dividida em três partes, que correspondem às chamadas transições de chamada, transições de retorno e transições internas, respectivamente:
  • $\delta _{c}:Q\times \Sigma _{c}\to Q\times \Gamma$, a função de transição de chamada;
  • $\delta _{r}:Q\times \Sigma _{r}\times \Gamma \to Q$,a função de transição de retorno;
  • $\delta _{int}:Q\times \Sigma \to Q$, a função de transição interna;
• $\,q_{0}\in \,Q$ é o estado inicial;
• $F\subseteq Q$ é o conjunto de estados de aceitação.

A noção de computação de um autômato visivelmente de pilha é uma restrição do autômato de pilha utilizado. Autômatos visivelmente de pilha só adicionam um símbolo à pilha ao ler um símbolo de chamada $a_{c}\in \Sigma _{c}$; só removem o elemento do topo da pilha ao ler um símbolo de retorno $a_{r}\in \Sigma _{r}$; e não alteram a pilha ao ler um evento interno $a_{i}\in \Sigma _{int}$. A computação termina em um estado de aceitação.

Como resultado, um autômato visivelmente de pilha não pode empurrar e pegar a partir da pilha com o mesmo símbolo de entrada.

Assim, a línguagem $L=\{a^{n}ba^{n}\mid n\in \mathrm {N} \}$ não pode ser aceita por um autômato visivelmente de pilha para qualquer partição de $\Sigma$. No entanto, existem autômatos de pilha aceitando essa linguagem.

Se uma linguagem L sobre um alfabeto marcado$\,{\hat {\Sigma }}$ é aceita por um autômato determinístico visivelmente, então L é chamado de linguagem visivelmente de pilha.

Autômato não determinístico visivelmente de pilha

Os autômatos não determinísticos visivelmente de pilha são tão expressivos quanto os deterministas. Daí pode-se transformar uma autômato não determinístico visivelmente em um determinístico. Porém, se o autômato não determinístico tinha $s$ estados, o determinístico pode ter até $2^{s^{2}}$estados.

Problema da decisão

Se for atribuído $|A|$ como o tamanho da descrição de um automato $A$, então é possível verificar se uma palavra n é aceita pelo autômato no tempo $O(|A|^{3}\ell )$. Em particular, o problema pode ser resolvido na vacuidade, no tempo $O(|A|^{3})$.

Se $A$ é fixo, isto é, em tempo determinável $O(\ell )$ e espaço $O(d)$, onde $d$ é a profundidade de n vista em um streaming. Também é determinável com um espaço $O(\log(\ell ))$ e tempo $O(\ell ^{2}\log(\ell ))$ ; e por um circuito de profundidade uniforme booleano $O(\log \ell )$.

Para dois autômatos não determinísticos A e B, decidindo se o conjunto de palavras aceito por A é um subconjunto da palavra B aceito pelo EXPTIME-completo. Isso apenas se o EXPTIME-completo também éo EXPTIME-completo usado para descobrir se existe uma palavra que não é aceita.

Propriedades de fechamento

O conjunto de idiomas visivelmente de pilha é fechado sob as seguintes operações:

• Definir operações:
  • União;
  • Interseção;
  • Complemento, dando assim origem a uma álgebra booleana;
• Kleene star;
• Concatenação.

Para a operação de cruzamento, pode-se construir uma simulação VPA M de duas APVs $M_{1}$ e $M_{2}$, dadas por uma construção de um simples produto (Alur & Madhusudan 2004): para $i=1,2$, assume-se que $M_{i}$ é $(Q_{i},\ {\hat {\Sigma }},\ \Gamma _{i},\ \delta _{i},\ s_{i},\ Z_{i},\ F_{i})$. Então, para o autômato M, o conjunto de estados é $\,Q_{1}\times Q_{2}$, o estado inicial é $\left(s_{1},s_{2}\right)$, o conjunto de estados final é $F_{1}\times F_{2}$, o alfabeto de pilha é dado por $\,\Gamma _{1}\times \Gamma _{2}$ e o símbolo de pilha inicial é $(Z_{1},Z_{2})$.

Se $M$ está sobre o estado $(p_{1},p_{2})$ e sobre o estado $\left\langle a\right.$, então $M$ empurra o símbolo na pilha $(\gamma _{1},\gamma _{2})$ e vai para o estado $(q_{1},q_{2})$, onde $\gamma _{i}$ é o símbolo de pilha empurrado por $M_{i}$, quando a transição vai do estado $p_{i}$ para$q_{i}$ quando a entrada $\left\langle a\right.$ é lida.

Se $M$ está no estado $(p_{1},p_{2})$, esta lê um símbolo interno $a$; e então $M$ vai para o estado $(q_{1},q_{2})$, sempre que $M_{i}$ transiciona do estado $p_{i}$ para $q_{i}$ ao ler a.

Se $M$ está no estado $(p_{1},p_{2})$, a leitura de um símbolo retorna $\left.a\right\rangle$; e então $M$ retira o símbolo $(\gamma _{1},\gamma _{2})$ da pilha e vai para o estado $(q_{1},q_{2})$, onde $\gamma _{i}$ é o símbolo de pilha apareceu por $M_{i}$ quando a transição de estado $p_{i}$ vai para $q_{i}$ quando $\left.a\right\rangle$ é lida.

A correção da construção acima crucialmente se baseia no fato de que a pressão e ações retiradas das máquinas simuladas $M_{1}$ e $M_{2}$ são sincronizadas ao longo dos símbolos de entrada de leitura. Na verdade, uma simulação semelhante não é mais possível para autômatos de pilhas determinísticos, como a maior classe de linguagens determinísticas livres de contexto não é mais fechada sob interseção.

Em contraste com a construção de concatenação mostrada acima, a construção de complementação para autômatos visivelmente de pilha é paralela à construção padrão por autômatos de pilha determinísticos.

Além disso, a classe de linguagens visivelmente de pilha é fechada sob:

• Fechamento prefixo;
• Fechamento sufixo;
• Reversão.

Relação com outras classes de linguagem

Alur & Madhusudan (2004) salientam que as línguagens visivelmente de pilha são mais gerais do que intervalos de linguagem sugeridos por McNaughton (1967). Como apresentado por Reghizzi & Mandrioli (2009), para VPL, por sua vez, são estritamente contidos na classe dos idiomas descritos como operandos de procedência gramatical, que foram introduzidas por Floyd (1963). Em comparação com gramáticas conjuntivas, uma generalização de gramáticas livres de contexto, Okhotin (2011) mostra que linguagens de conjunções lineares formam uma superclasse de linguagens visivelmente de pilha.

Ligações externas

• Nested words and visibly pushdown languages
• Visibly pushdown automata - Automata on nested words
• class VPL no Complexity Zoo