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 aninhadas são um conceito proposto Alur e Madhusudan como uma generalização conjunta de palavras, tradicionalmente usada para modelagem de estruturas linearmente ordenadas e de árvore ordenadas sem classificação , como também utilizadas para modelagem de estruturas hierárquicas. Aceitadores de estado finito para palavras aninhadas, são chamados de automatos de palavras aninhadas, assim generalizam de maneira mais expressiva automatos 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 das linguagens livre de contexto determinísticas. Desde sua introdução, em 2004, esses conceitos têm desencadeado muita pesquisa na área.[1]

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 , usaremos a notação para denotar o conjunto, com o caso especial .

A relação de correspondência' ↝ de tamanho é um subconjunto de 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 , 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'.

é 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 sobre o alfabeto Σ é um par (w,↝), onde w é a palavra de tamanho sebrer Σ (no sentido usual) and ↝é relação de correspondencia do tamanho .

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

Palavras aninhadas em um alfabeto: pode ser codificado em palavras “comuns” usando um alfabeto “rotulado” , 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 de maneira que cada palavra aninhada (,↝) é mapeada para a palavra , onde a letra é igual a ⟨a, a, ou a⟩, respectivamente, se 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 da esquerda para a direita, e o estado do automato depois da leitura da jth letra depende do estado que o automato estava antes de ler .

Em um automato de palavras aninhadas, a posição em uma palavra aninhada (w,↝) pode ser uma posição de retorno; se assim, o estado de depois de ler will não erá apenas dependente do ‘’estado linear’’ que o automato estava antes de ler, 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

onde

  • é um conjunto finito de estados,
  • é o alfabeto de entrada, o que - em contraste com a dos autómatos pilha normal - é dividida em três conjuntos, , e . o alfabeto indica o conjunto de “símbolos de chamada”,, ontém os símbolos de retorno, e o conjunto contem os 'simbolos internos,
  • é um conjunto finito que é chamado o alfabeto de pilha, que contém um símbolo especial denotando a pilha vazia
  • é 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
    • , a função de transição chamada
    • ,a função de transição de retorno
    • , a função de transição interna
  • é o estado inicial, e
  • é 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 ,eles só removem o elemento do topo da pilha ao ler um símbolo de retorno e eles não alteram a pilha ao ler um evento interno . 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 cnão pode ser aceito por um autômato visivelmente Pilha para qualquer partição de ,no entanto, existem autômatos Pilha aceitando essa linguagem.

Se uma language L sobre um alfabeto marcado é 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 estados, o determinístico pode ter até estados.[3]

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

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

se é fixo, isto é, em tempo determinável e espaço onde é a profundidade de n em um streaming vendo. Também é determinável com espaço e tempo , e por um circuito de profundidade uniforme booleano .[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 e por uma construção simples produto (Alur & Madhusudan 2004): para , assume é dado . Então, para o autômato M, o conjunto de estados é , o estado inicial é , o conjunto de estados final é , o alfabeto pilha é dada pela , e o símbolo pilha inicial é .

Se esta sobre o estado esta sobre o estado , então mpurra o símbolo na pilha e vai para o estado , onde é o símbolo de pilha empurrado por uando a transição vai do estado para quando ler a entrada .

Se iesta no estado o ler um símbolo interno , então vai para o estado , sempre que transições de estado para a leitura a.

Se esta no estado a leitura de um símbolo retorno , entao retira o simbolo da pilha e vai para o estado , onde é o símbolo de pilha apareceu por quando a transição de estado para quando ler.

Correcção da construção acima crucialmente se baseia no fato de que a pressão e ações retiradas das máquinas simulados e 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]