Palavra aninhada

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Ambox important.svg
Foram assinalados vários aspectos a serem melhorados nesta página ou secção:

Em ciência da computação, mais especificamente em teoria do automato e teoria de linguagem formal, palavras alinhada são um conceito propostos Alur e Madhusudan como uma generalização conjunta de palavras, tradicionalmente usada para modelagem de estruturas linearmente ordenadas e de Arvore ordenadas sem classificação , como também utilizadas para modelagem de estruturas hierarquicas. Aceitadores de estado finito para palavras aninhadas,

são chamados de automatos de palavras aninhadas, assim generalizam de maneira mais expressiva automatos finitos nao deterministicos 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 languagem regulares e das Linguagem livre de contexto determinísticas. Desde sua introdução em 2004, Esses conceitos tem desencadeado muita pesquisa na área.[1] um formalismo equivalente regular tree grammars.

Definição formal[editar | editar código-fonte]

Para definir palavras aninhadas, nós primeiro precisamos definir relação de correspondência. Como usual, para inteiro inteiros nao 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\ge 0é um subconjunto de \{-\infty, 1,2,\ldots,\ell-1,\ell\}\times\{1,2,\ldots,\ell-1,\ell,\infty\} de tal modo que:

(i) Todos os extremos aninhados estão à frente, isto é, se i ↝ j então i<j;

(ii) 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, ae existe no máximo uma posição j de forma que i ↝ j; e

(iii) 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 for some h and as a "pending return" se -∞ ↝ i.

Uma palavra aninhada de tamanho \ell sobre o alfabeto Σ é um par (w,↝), onde w é a palavra de tamanho \ell sebrer Σ (no sentido usual) and ↝é relação de correspondencia do tamanho \ell.

Codificação palavras aninhados em palavras comuns[editar | editar código-fonte]

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 Σ hpossue três contrapartes: o símbolo ⟨a que codifica para uma posição chamada de uma palavra aninhada marcado com um a, o simbolo a⟩ para codificar uma posição de retorno marcado com um a, e finalmente o simbolo a ele mesmo representando uma posição interna rotulada com um a. Mais precisamente, deixa φ ser função de mapeamento aninhado sobre Σ para palavras em \hat{\Sigma} de maneira que cada palavra aninhada (w_1w_2\cdots w_\ell,↝) é mapeada para a palavra x_1x_2...x_\ell, onde a letra x_i é igual a ⟨a, a, ou a⟩, respectivamente, se w_i=a e i e i é uma chamada de posição, uma posição interna, ou uma posição de retorno, respectivamente.

Exemplo[editar | editar código-fonte]

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

Autômato[editar | editar código-fonte]

Autômato de palavra aninhada[editar | editar código-fonte]

O automato de palavra aninhada tem finitos números de estados, e opera quase do mesmo jeito que um automato finito deterministico sobre cadeias classicas:um clássico automato finito lê a palavra de entrada entrada w = w_1\cdots w_\ell da esquerda para a direita, e o estado do automato depois da leitura da jth letra w_j depende do estado que o automato estava antes de ler w_j.

Em um automato 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 will não erá apenas dependente do ‘’estado linear’’ que o automato estava antes de lerw_j, mas também do estado hierárquico propagado pelo o automato no tempo que ele estava na correspondente posição de chamada. Em analogia as linguagens regulares de palavras, um conjunto ‘’L’’ de palavras aninhadas é chamada regular se é aceito por algum automato (estado- finito) aninhado.

Automato visivelmente com Pilha[editar | editar código-fonte]

Automatos de palavra aninhadas são modelo de automato aceitantes de palavras aninhadas. Existe um modelo de automato equivalente operacional em palavras (comuns). Ou seja, a noção de um Automato Deterministico Com Pilha Visivelmente é uma restrição da noção de um Automato Deterministico com Pilha.

Seguindo Alur e Madhusudan ,[2] m determinístico visivelmente autômato visivelmente deterministico é formalmente definida como uma 6-tupla M=(Q,\  \hat{\Sigma},\  \Gamma,\  \delta,\ q_0, \ F)

onde

  • \, Q é um conjunto finito de estados,
  • \,\hat{\Sigma}é o alfabeto de entrada, o que - em contraste com a dos autómatos pilha normal - é dividida em três conjuntos\Sigma_c, \Sigma_r, e \Sigma_{int}. o alfabeto\Sigma_c indica o conjunto de “símbolos de chamada”,, \Sigma_rontém os símbolos de retorno, e o conjunto \Sigma_{int} contem os 'simbolos internos,
  • \,\Gamma é um conjunto finito que é chamado o 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 é dividido em três partes que correspondem às transições de chamada de retorno, transições e transições internas, nomeadas
    • \delta_c:Q \times \Sigma_c \to Q \times \Gamma, a função de transição 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, e
  • F \subseteq Q é o conjunto de estados de aceitação.

A noção de computação de um visivelmente autômato pilha é uma restrição do utilizado automato pilha. Autômatos visivelmente Pilha só adicionar um símbolo para a pilha ao ler um símbolo de chamada a_c\in \Sigma_c,eles só removem o elemento do topo da pilha ao ler um símbolo de retorno a_r\in\Sigma_r e eles 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 Pilha não pode empurrar e pegar a partir da pilha com o mesmo símbolo de entrada.

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

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

Autômato não determinístico visivelmente Pilha[editar | editar código-fonte]

Automato não deterministico visivelmente pilha ão tão expressivos quanto os deterministas. Daí pode-se transformar uma não determinístico visivelmente autômato em um determinístico, mas se o autômato não determinístico tinha s estados, o determinístico pode ter até 2^{s^2} estados.[3]

Problema da decisão[editar | editar código-fonte]

Atribua |A| como o tamanho da descrição de um automato A, então é possível verificar se uma palavra n é aceito pelo autômato no tempo O(|A|^3\ell). Em particular, o problema pode ser resolvido vacuidade em vez O(|A|^3).

seA é fixo, isto é, em tempo determinável O(\ell) e espaço O(d) onde dé a profundidade de n em um streaming vendo. Também é determinável com espaço O(\log(\ell)) e tempo O(\ell^2 \log (\ell)), e por um circuito de profundidade uniforme booleano O(\log \ell).[2]

para dois autómatos não determinístico A e B, decidindo se o conjunto de palavras aceite por A é um subconjunto da palavra B é aceite pelo EXPTIME-complete. It is also EXPTIME-complete ambém é EXPTIME-completo para descobrir se existe uma palavra que não é aceito.[2]

propriedades de fechamento[editar | editar código-fonte]

O conjunto de idiomas visivelmente Pilha é fechado sob as seguintes operações:[3]

  • definir operações:
    • uniao
    • interseção

Para a operação de cruzamento, pode-se construir um VPA M simulação de duas dadas APV M_1 e M_2 por uma construção simples produto (Alur & Madhusudan 2004): para i=1,2, assume M_i é dado (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 pilha é dada pela \,\Gamma_1\times\Gamma_2, e o símbolo pilha inicial é (Z_1,Z_2).

Se M esta sobre o estado (p_1,p_2) esta sobre o estado \left\langle a\right., então Mmpurra 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 uando a transição vai do estado p_i paraq_i quando ler a entrada \left\langle a\right..

Se M iesta no estado (p_1,p_2) o ler um símbolo interno a, então M vai para o estado (q_1,q_2), sempre que M_i transições de estado p_i para q_i a leitura a.

Se M esta no estado (p_1,p_2) a leitura de um símbolo retorno \left. a\right\rangle, entaoM retira o simbolo (\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 para q_i quando ler\left. a\right\rangle.

Correcção da construção acima crucialmente se baseia no fato de que a pressão e ações retiradas das máquinas simulados M_1 e M_2 aasão sincronizadas ao longo dos símbolos de entrada de leitura. Na verdade, uma simulação semelhante não é mais possível para automatos pilhas deterministicos, como a maior classe de determinístico linguagens livres de contexto não é mais fechada sob interseção.

Em contraste com a construção de concatenação mostrado acima, a construção de complementação para autómatos visivelmente Pilha paralela à construção padrão[4] por automatos pilhas deterministicos

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

  • fechamento prefixo
  • fechamento sufixo
  • reversão.

Relação com outras classes de linguagem[editar | editar código-fonte]

Alur & Madhusudan (2004) salienta que as línguagens de visivelmente pilha são mais gerais do que intervalos de linguagem sugerido emMcNaughton (1967).Como apresentado Reghizzi & Mandrioli (2009), to VPL por sua vez são estritamente contido na classe dos idiomas descritos por operando de procedencoa gramaticas, que foram introduzidas por Floyd (1963). Em comparação com conjunctive grammars, uma generalização de gramáticas livres de contexto, Okhotin (2011) mostra que linguagens de conjunções lineares formam uma superclasse de línguagens de visivelmente pilha.

Notas

  1. Google Scholar search results para cadeias aninhadas ou visivelmente pilha
  2. a b c Alur & Madhusudan (2009)
  3. a b Alur & Madhusudan (2004)
  4. Hopcroft & Ullman (1979), p. 238 f.

Referências[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]