# Autômato de pilha agrupado

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çãonecessários]}$

## Definição Formal
### Autômato

Um (não determinístico) autômato de pilha agrupado é uma tupla "Q,Σ,Γ,δ,q$_0$,Z$_0$,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.
* 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 δ mapas
| 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; , 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.
* q$_0$ ∈ Q é o estado inicial,
* Z$_0$ ∈ Γ é 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, [a$_1$a$_2$...a$_i$...a$_{n-1}$], [Z$_1$X$_2$...X$_j$...X$_{m-1}$] ", onde
* q ∈ Q é o estado atual,
* [a$_1$a$_2$...a$_i$...a$_{n-1}$] é a seqüência de caracteres de entrada; por conveniência, a$_0$ = [ e a$_n$ = ] está definido A posição atual na entrada, ou seja, i com 0 ≤ i ≤ n, é marcada por sublinhado o respectivo símbolo.
* [Z$_1$X$_2$...X$_j$...X$_{m-1}$] é a pilha, incluindo subpilhas; por conveniência, X$_1$ = [Z$_1$ e X$_m$ = ] 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ção | Passo | Pilha | Pilha | Pilha | Pilha | Pilha | Pilha | Pilha | Pilha | Pilha | Pilha | Pilha |
| | 1: | [a | b | [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 subpilha | 5: | [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.