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.[1] 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,[2] 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.[1][3]
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[editar | editar código-fonte]
Autômato[editar | editar código-fonte]
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.[note 1]
- 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[note 2]
| 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;[4] , 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[editar | editar código-fonte]
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á definido[note 3] 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 [note 4] e Xm = ] está definido. A posição atual na pilha, ou seja, j com 1 ≤ j ≤ m, é marcado sublinhando o respectivo símbolo.
Exemplo[editar | editar código-fonte]
Um exemplo de execução (seqüência de caracteres de entrada não são mostrados):
| Ação | Passo | 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[editar | editar código-fonte]
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.[5]
Gilman e Shapiro usaram autômatos de pilha agrupado para resolver o problema de palavras em determinados grupos.[6]
Notas[editar | editar código-fonte]
- ↑ Aho originally used "$", "¢", and "#" instead of "[", "]", and "]", respectively.
- ↑ Juxataposition denotes string (set) concatenation, and has a higher binding priority than set union ∪.
- ↑ Aho originally used the left and right stack marker, viz. $ and ¢, as right and left input marker, respectively.
- ↑ The top symbol of a (sub)stack together with its preceding left endmarker "[" is viewed as a single symbol.
Referências[editar | editar código-fonte]
- ↑ a b Aho, Alfred (1969). «Nested stack automata». Journal of the ACM. 16 (3): 383–406. ISSN 0004-5411. doi:10.1145/321526.321529
- ↑ Partee, Barbara; Alice ter Meulen; Robert E. Wall (1990). Mathematical Methods in Linguistics. [S.l.]: Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4
- ↑ John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. [S.l.]: Addison-Wesley. ISBN 0-201-02988-X
- ↑ Aho (1969), p.385 top
- ↑ C. Beeri (1975). «Two-Way Nested Stack Automata Are Equivalent to Two-Way Stack Automata» (PDF). J. Comp. and System Sciences. 10: 317–339. doi:10.1016/s0022-0000(75)80004-3
- ↑ Robert Gilman, Michael Shapiro (Dec 1998).