direita|miniaturadaimagem|Autômato de pilha agrupado tem o mesmo mecanismo de um autômato com pilha, mas tem menos restrições para ser usado. Na teoria dos autômatos, uma pilha de autômatos agrupados é um autômato finito que pode ser usado como uma pilha que contém dados que podem ser de pilhas adicionais. Como um autômato de pilha, um autômato de pilha agrupado podem passar para cima ou para baixo na pilha, e ler o símbolo atual; além disso, ele poderá, em qualquer lugar, criar uma nova pilha, operar em que, eventualmente destruí-la, e continuar operando com a pilha antiga. Desta forma, as pilhas podem ser agrupadas de forma recursiva a uma profundidade arbitrária; no entanto, o autômato sempre opera na parte mais interna da pilha.

Autômato de pilha agrupado é capaz de reconhecer uma linguagem indexada, e no fato de a classe de linguagem indexada é, exatamente, a classe de linguagens aceita por um caminho não-determinístico de autômatos de pilha agrupados.

Autômato de pilha agrupado não deve ser confundido com autômato com pilha embutido, que têm menos poder computacional.[citação necessários]

Definição Formal

Autômato Um (não determinístico) autômato de pilha agrupado é uma tupla "Q,Σ,Γ,δ,q0,Z0,F,[,],]" onde Q, Σ, Γ é um conjunto finito não vazio de estados, de entrada de símbolos, e pilha de símbolos, respectivamente, [, ], ] são símbolos especiais distintos que não são contidos em Σ ∪ Γ, [ é usado como um marcador a esquerda para a entrada de cadeias de caracteres e uma (sub)pilha de cadeias de caracteres, ] é utilizado como um marcador a direita para estas cadeias de caracteres, ] é usada como um marcador de fim da cadeia de caracteres denotando a pilha inteira.Aho originally used "$", "¢", and "#" instead of "[", "]", and "]", respectively. Um longo alfabeto de entrada é definida por Σ' = Σ ∪ {[,]}, uma pilha expandida de alfabeto Γ' = Γ ∪ {]}, e o conjunto de entrada que informa a direção, por D = {-1,0,+1}. δ, o controle finito, é um mapeamento de Q × Σ' × (Γ' ∪ [Γ' ∪ {], []}) em subconjuntos finitos de Q × D × ([Γ* ∪ D), tal que δ mapasJuxataposition denotes string (set) concatenation, and has a higher binding priority than set union ∪. Q × Σ' × [Γ em subconjuntos de Q × D × [Γ* (modo de pilha), Q × Σ' × Γ' em subconjuntos de Q × D × D (modo de leitura), Q × Σ' × [Γ' em subconjuntos de Q × D × {+1} (modo de leitura), Q × Σ' × {]} em subconjuntos de Q × D × {-1} (modo de leitura), Q × Σ' × (Γ' ∪ [Γ') em subconjuntos de Q × D × [Γ*] (modo pilha de criação), e Q × Σ' × {[]} em subconjuntos de Q × D × {ε}, (modo de destruição da pilha), Informalmente, o símbolo superior de um (sub)pilha juntamente com o seu marcador anterior a esquerda "[" é visto como um único símbolo,Aho (1969), p.385 top em seguida, δ lê o estado atual, o atual símbolo de entrada, e o atual símbolo da pilha, e saídas o próximo estado, a direção em a qual se move na entrada, e a direção na a qual se move na pilha, ou a cadeia de símbolos para substituir a pilha de maior símbolo. q0 ∈ Q é o estado inicial, Z0 ∈ Γ é o símbolo de pilha inicial, F ⊆ Q é o conjunto de estados finais.

Configuração Uma configuração, ou descrição instantânea de como um autômato consiste em uma tripla " q, [a1a2...ai...an-1], [Z1X2...Xj...Xm-1] ", onde q ∈ Q é o estado atual, [a1a2...ai...an-1] é a seqüência de caracteres de entrada; por conveniência, a0 = [ e an = ] está definidoAho originally used the left and right stack marker, viz. $ and ¢, as right and left input marker, respectively. A posição atual na entrada, ou seja, i com 0 ≤ i ≤ n, é marcada por sublinhado o respectivo símbolo. [Z1X2...Xj...Xm-1] é a pilha, incluindo subpilhas; por conveniência, X1 = [Z1 The top symbol of a (sub)stack together with its preceding left endmarker "[" is viewed as a single symbol. e Xm = ] está definido. A posição atual na pilha, ou seja, j com 1 ≤ j ≤ m, é marcado sublinhando o respectivo símbolo.

Exemplo Um exemplo de execução (seqüência de caracteres de entrada não são mostrados): AçãoPassoPilha 1: [ab [k ] [p ] c] Criar subpilha 2: [a b [k ] [p [r s ] ] c ]remover 3: [a b [k ] [p [s ] ] c ]remover 4: [a b [k ] [p [] ] c ]Apagar subpilha5: [a b [k ] [p ] c ] mover para cima 6: [a b [k ] [p ] c ] mover para cime 7: [a b [k ] [p ] c ] mover para cima 8: [a b [k ] [p ] c ]inserir 9: [a b [k ] [n o p ] c ]

Propriedades Quando autômatos são permitidos para re-ler sua entrada ("autômato finito determinístico de dois sentidos"), pilhas agrupadas não resultam em uma linguagem com capacidades de reconhecimento adicional, em comparação a pilhas simples.

Gilman e Shapiro usaram autômatos de pilha agrupado para resolver o problema de palavras em determinados grupos.Robert Gilman, Michael Shapiro (Dec 1998)

Notas

Referências

Categoria:Teoria dos autômatos Categoria:Modelos computacionais