Paralelismo

Aluno: Petrus Saulo Almeida e sousa

Autômato com Pilha e Linguagens Livres do Contexto
Introdução:

Os aceitadores, ou reconhecedores, das linguagens livres de contexto são os chamados autômatos de pilha ou ap's. O ap não determinístico, ou apnd, que consiste basicamente de um autômato finito não determinístico, com uma memória adicional, em forma de pilha. Numa pilha, símbolos novos só podem ser acrescentados no topo da pilha; apenas o último símbolo armazenado, o símbolo que se encontra no topo da pilha pode ser consultado; esse símbolo deve ser retirado para que os demais possam ser alcançados.

Autômato com pilha determinístico Aceita um sub conjunto próprio das linguagens livre de contexto , denominadas linguagens livres de contexto determinísticas (LLCD). A Classe das LLCD inclui muitas das linguagens aplicadas em informática, com destaque para as de programação.

Autômatos de pilha não determinísticos

Definição. Definimos um autômato de pilha não determinístico (apnd) como uma construção (tupla) A = < K, S, G, d, i, I, F >, formada pelos seguintes elementos: K - conjunto (finito) de estados - alfabeto de entrada T - alfabeto da pilha - função de transição : K x ( {e}) x T P(K x T*) i - estado inicial i K I - símbolo inicial da pilha I G F - conjunto de estados finais F K O alfabeto T contém os símbolos que podem ser armazenados na pilha, ou seja, empilhados. Para simplificar a especificação da função de transição d, consideramos que a cada passo, um símbolo é lido (e retirado) do topo da pilha, e, no mesmo passo, uma seqüência de comprimento qualquer pode ser empilhada. Assim, se queremos retirar um símbolo do topo da pilha, basta que a sequência a ser empilhada seja a seqüência vazia e. Por outro lado, se quisermos manter o símbolo do topo da pilha, ele deve ser re-empilhado.