Mostrar código-fonte de Palavra aninhada

{{Mais notas|Este artigo|ci|data=abril de 2013}}
Em [[ciência da computação]], mais especificamente nas teorias [[teoria dos autômatos|dos autômatos]] e de [[linguagem formal]], palavras aninhadas são um conceito proposto por Alur e Madhusudan como uma generalização conjunta de [[String|palavras]], tradicionalmente usada para [[Modelagem computacional|modelagem]] de estruturas linearmente ordenadas e de [[Árvore (estrutura de dados)|á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 (informática)|pilha]]. A última classe de linguagem fica entre [[linguagens regulares]] e as [[Linguagem livre de contexto determinística|linguagens livres de contexto determinística]]s. Desde sua introdução, em 2004, esses conceitos têm desencadeado muitas pesquisas na área.<ref>{{Citar web|url=https://scholar.google.com/scholar?as_q=&as_oq=%22nested+words%22+%22visibly+pushdown%22|titulo=Google Acadêmico|acessodata=2022-07-30|website=scholar.google.com}}{{ref deficiente}}</ref>

==Definição formal==
Para definir palavras aninhadas, [[Nó (unidade)|nós]] primeiro precisamos definir a relação de correspondência. Como usual, para [[Números naturais|inteiros não negativos]] <math>\ell</math>, usaremos a notação <math>[\ell]</math> para denotar o conjunto <math>\{1,2,\ldots,\ell-1,\ell\}</math>, com o caso especial <math>[0]=\emptyset</math>.

A relação de correspondência "↝", de tamanho <math>\ell\ge 0</math>, é um [[subconjunto]] de  <math>\{-\infty, 1,2,\ldots,\ell-1,\ell\}\times\{1,2,\ldots,\ell-1,\ell,\infty\}</math>, de tal modo que:

# Todos os extremos aninhados estão à frente, isto é, se i↝j, então i < j; 
# Extremos aninhados nunca têm uma posição [[Conjunto finito|finita]] em comum, isto é, para <math>-\infty < i < \infty </math>, 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; 
# Extremos aninhados nunca se cruzam, isto é, não podemos encontrar i < i'≤ j < j', de maneira que ambos i↝j e i'↝j'.

<math>i</math> é 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 <math>\ell</math> sobre o [[Alfabeto (ciência da computação)|alfabeto]] Σ é um par (w,↝), onde w é a palavra de tamanho <math>\ell</math> sobre Σ (no sentido usual) e "↝" é uma relação de correspondência do tamanho <math>\ell</math>.

==Codificação de palavras aninhadas em palavras comuns==
=== Palavras aninhadas em um alfabeto ===
<math>\Sigma=\{a_1,a_2,\ldots,a_n\}</math> pode ser codificado em palavras “comuns”, usando um alfabeto “rotulado” <math> \hat{\Sigma}</math>, em que cada um dos [[Símbolo|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 <math>\hat{\Sigma}</math>, de modo que cada palavra aninhada (<math>w_1w_2\cdots w_\ell</math>,↝) é mapeada para a palavra <math>x_1x_2...x_\ell</math>, onde a letra <math>x_i</math> é igual a ⟨a, a, ou a⟩, respectivamente, se <math>w_i=a</math> 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 <math>w = w_1\cdots w_\ell</math> da esquerda para a direita, e o estado do autômato depois da leitura da ''j''<sup>a</sup> letra <math>w_j</math> depende do estado em que o autômato estava antes de ler <math>w_j</math>.

Em um autômato de palavras aninhadas, a posição <math>j</math> em uma palavra aninhada (w,↝) pode ser uma posição de retorno; se assim, o estado de depois de ler <math>w_j</math> não será apenas dependente do ‘’estado linear’’ que o autômato estava antes de ler <math>w_j</math>, 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 [[Linguagem regular|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,<ref name="AlurMadhu09">{{harvtxt|Alur|Madhusudan|2009}}{{ref deficiente}}</ref> um autômato visivelmente determinístico é formalmente definido como uma 6-tupla<math>M=(Q,\  \hat{\Sigma},\  \Gamma,\  \delta,\ q_0, \ F)</math>, em que:
*<math>\, Q </math> é um [[conjunto finito]] de estados;
*<math>\,\hat{\Sigma}</math> é o alfabeto de entrada, o que - em contraste com o dos autômatos de pilha normal - é dividido em três conjuntos: <math>\Sigma_c</math>, <math>\Sigma_r</math>, e <math>\Sigma_{int}</math>. cO alfabeto <math>\Sigma_c</math> indica o conjunto de “símbolos de chamada”; <math>\Sigma_r</math> contém os símbolos de retorno; e <math>\Sigma_{int}</math> contém os "símbolos internos";
*<math>\,\Gamma</math> é um conjunto finito, que é o chamado alfabeto de pilha, que contém um símbolo especial <math>\bot\in\Gamma</math>, denotando a pilha vazia;
*<math>\,\delta = \delta_c \cup \delta_r \cup \delta_{int}</math> é 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:
**<math>\delta_c:Q \times \Sigma_c \to Q \times \Gamma</math>, a função de transição de chamada;
**<math>\delta_r:Q \times \Sigma_r \times \Gamma \to Q </math>,a função de transição de retorno;
**<math>\delta_{int}:Q \times \Sigma \to Q </math>, a função de transição interna;
*<math>\,q_0\in\, Q </math> é o estado inicial;
*<math>F \subseteq Q</math> é 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 <math>a_c\in \Sigma_c</math>; só removem o elemento do topo da pilha ao ler um símbolo de retorno  <math>a_r\in\Sigma_r</math>; e não alteram a pilha ao ler um evento interno <math>a_i\in\Sigma_{int}</math>. 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 <math>L=\{a^nba^n \mid n\in\mathrm{N} \}</math>  não pode ser aceita por um autômato visivelmente de pilha para qualquer partição de <math>\Sigma</math>. No entanto, existem autômatos de pilha aceitando essa linguagem.

Se uma linguagem ''L'' sobre um alfabeto marcado<math>\,\hat{\Sigma}</math> é 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 <math>s</math> estados, o determinístico pode ter até <math>2^{s^2}</math>estados.<ref name="AlurMadhu04">{{harvtxt|Alur|Madhusudan|2004}}{{ref deficiente}}</ref>

==Problema da decisão==
Se for atribuído <math>|A|</math> como o tamanho da descrição de um automato <math>A</math>, então é possível verificar se uma palavra ''n'' é aceita pelo autômato no [[tempo]] <math>O(|A|^3\ell)</math>. Em particular, o problema pode ser resolvido na [[vacuidade]], no tempo <math>O(|A|^3)</math>.

Se <math>A</math> é fixo, isto é, em tempo determinável <math>O(\ell)</math> e espaço <math>O(d)</math>, onde <math>d</math> é a profundidade de ''n'' vista em um ''[[streaming]]''. Também é determinável com um espaço  <math>O(\log(\ell))</math> e tempo <math>O(\ell^2 \log (\ell))</math> ; e por um circuito de profundidade uniforme booleano  <math>O(\log \ell)</math>.<ref name="AlurMadhu09"/>

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.<ref name="AlurMadhu09"/>

===Propriedades de fechamento===
O conjunto de idiomas visivelmente de pilha é fechado sob as seguintes operações:<ref name="AlurMadhu04"/>

*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 <math>M_1</math> e <math>M_2</math>, dadas por uma construção de um simples produto {{harv|Alur|Madhusudan|2004}}: para <math>i=1,2</math>, assume-se que <math>M_i</math> é <math>(Q_i,\  \hat{\Sigma},\  \Gamma_i,\  \delta_i, \ s_{i},\ Z_i, \ F_i)</math>. Então, para o autômato M, o conjunto de estados é <math>\, Q_1\times Q_2</math>, o estado inicial é <math>\left(s_{1}, s_2\right)</math>, o conjunto de estados final é <math>F_1 \times F_2</math>, o alfabeto de pilha é dado por <math>\,\Gamma_1\times\Gamma_2</math> e o símbolo de pilha inicial é <math>(Z_1,Z_2)</math>.

Se <math>M</math> está sobre o estado <math>(p_1,p_2)</math> e sobre o estado <math>\left\langle a\right.</math>, então <math>M</math> empurra o símbolo na pilha <math>(\gamma_1,\gamma_2)</math> e vai para o estado <math>(q_1,q_2)</math>, onde <math>\gamma_i</math> é o símbolo de pilha empurrado por  <math>M_i</math>, quando a transição vai do estado <math>p_i</math> para<math>q_i</math> quando a entrada <math>\left\langle a\right.</math> é lida.

Se <math>M</math> está no estado <math>(p_1,p_2)</math>, esta lê um símbolo interno <math>a</math>; e então <math>M</math> vai para o estado <math>(q_1,q_2)</math>, sempre que  <math>M_i</math> transiciona do estado <math>p_i</math> para <math>q_i</math> ao ler ''a''.

Se <math>M</math> está no estado <math>(p_1,p_2)</math>, a leitura de um símbolo retorna <math>\left. a\right\rangle</math>; e então <math>M</math> retira o símbolo <math>(\gamma_1,\gamma_2)</math> da pilha e vai para o estado <math>(q_1,q_2)</math>, onde <math>\gamma_i</math> é o símbolo de pilha apareceu por <math>M_i</math> quando a transição de estado <math>p_i</math> vai para <math>q_i</math> quando <math>\left. a\right\rangle</math> é 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 <math>M_1</math> e <math>M_2</math> 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<ref>{{harvtxt|Hopcroft|Ullman|1979}}, p. 238 f.{{ref deficiente}}</ref> 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===
{{harvtxt|Alur|Madhusudan|2004}} salientam que as línguagens visivelmente de pilha são mais gerais do que intervalos de linguagem sugeridos por {{harvtxt|McNaughton|1967}}. Como apresentado por {{harvtxt|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 {{harvtxt|Floyd|1963}}. Em comparação com gramáticas conjuntivas, uma generalização de gramáticas livres de contexto, {{harvtxt|Okhotin|2011}} mostra que linguagens de conjunções lineares formam uma superclasse de linguagens visivelmente de pilha. 

== Notas e referências ==
{{InícioRef}}
{{Tradução/ref|en|Nested word}}
{{-fim}}
{{Reflist}}

==Bibliografia==
{{InícioRef|colwidth=32em}}
*{{Citar periódico|ultimo=Alur|primeiro=Rajeev|coautores=Marcelo|titulo=First-Order and Temporal Logics for Nested Words|url=http://www.lmcs-online.org/ojs/viewarticle.php?id=394|jornal=Logical Methods in Computer Science|data=2008-11-25|volume=4|numero=4|doi=10.2168/lmcs-4(4:11)2008|idioma=en}}
*{{Citar periódico|ultimo=Alur||primeiro=Rajeev|coautores=P.|titulo=Visibly Pushdown Languages|url=http://doi.acm.org/10.1145/1007352.1007390|editora=ACM|jornal=Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing|data=2004-01-01|local=New York, NY, USA|paginas=202–211|doi=10.1145/1007352.1007390}}
*{{Citar periódico|ultimo=Alur||primeiro=Rajeev|coautores=P.|titulo=Adding Nesting Structure to Words|url=http://doi.acm.org/10.1145/1516512.1516518|jornal=J. ACM|data=2009-05-01|issn=0004-5411|paginas=16:1–16:43|volume=56|numero=3|doi=10.1145/1516512.1516518}}
*{{Citar periódico|ultimo=Floyd|titulo=Syntactic Analysis and Operator Precedence|url=http://doi.acm.org/10.1145/321172.321179|jornal=J. ACM|data=1963-07-01|issn=0004-5411|paginas=316–333|volume=10|numero=3|doi=10.1145/321172.321179|primeiro=Robert W.}}
*{{Citar periódico|ultimo=McNaughton|titulo=Parenthesis Grammars|url=http://doi.acm.org/10.1145/321406.321411|jornal=J. ACM|data=1967-07-01|issn=0004-5411|paginas=490–500|volume=14|numero=3|doi=10.1145/321406.321411|primeiro=Robert}}
*Okhotin, Alexander: [http://users.utu.fi/aleokh/papers/linconj_vs_dcfl.pdf Comparing linear conjunctive languages to subfamilies of the context-free languages], 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011).
*Reghizzi, Stefano Crespi; Mandrioli, Dino: Algebraic properties of structured context-free languages: old approaches and novel developments, 7th International Conference on Words (WORDS 2009), {{arxiv|0907.2130}}.
{{-fim}}

==Ligações externas==
* [http://www.cis.upenn.edu/~alur/nw.html Nested words and visibly pushdown languages]
* [http://www.cs.uiuc.edu/~madhu/vpa/ Visibly pushdown automata - Automata on nested words]
* [https://web.archive.org/web/20120809152133/http://qwiki.stanford.edu/index.php/Complexity_Zoo:V#vpl class VPL] no Complexity Zoo

{{Controle de autoridade}}

[[Categoria:Teoria dos autômatos]]