Autômato de Duas Pilhas PDF

Preview

Summary

Download Autômato de Duas Pilhas PDF

Description

1. Introdução Linguagens Regulares são reconhecidas por Autômatos Finitos (determinísticos ou nãodeterminísticos), porém, para o caso das Linguagens Livre de Contexto, faz-se necessário o uso de uma memória auxiliar (Pilha), assim utilizando como dispositivo reconhecedor os Autômatos de Pilha (determinísticos ou não-determinísticos). Contudo, para o reconhecimento de Linguagens em que, por exemplo, haja necessidade de balanceamento, apenas uma Pilha não é suficiente para a execução da operação de reconhecimento. A partir disso surge a necessidade de dispositivos reconhecedores que implementem mais de uma Pilha.

2. Contexto Histórico Diversos estudos foram de suma importância na área da Teoria da Computação, entre os quais trabalhos que apresentam a utilização de modelos que aplicam a noção de pilha. A seguir, serão elencados alguns destes trabalhos: 

David Hilbert em 1900 propôs uma lista de 23 problemas matemáticos na conferência do Congresso Internacional de Matemáticos de Paris, cuja solução estimularia vários outros pesquisadores. Nessa conferência, ele publicou 10 dos problemas (1, 2, 6, 7, 8, 13, 16, 19, 21, e 22), e o resto da lista foi publicado mais tarde;



Para fazer com que a noção de "computável" fosse a mais clara e simples quanto possível, Alan Turing propôs em 1936 um modelo mecânico para computação, conhecido como Máquina de Turing;



Warren McCulloch e Walter Pitts foram os primeiros a apresentar uma descrição dos autômatos finitos em 1943. Seu trabalho, intitulado "A Logical Calculus Immanent in Nervous Activity", fez contribuições significativas para o estudo da teoria de redes neurais, teoria dos autômatos e para a teoria da computação;



A utilização de um modelo de pilha foi proposta pela primeira vez em 1946, no projeto do computador de Alan Turing, como um meio de chamar e retornar de sub-rotinas;



Em 1951, trabalhando a partir dos trabalhos realizados por McCulloch e Pitts, Stephen C. Kleene estabeleceu uma propriedade fundamental dos autômatos de estados finitos, ou seja, que os conjuntos de fitas reconhecidas por eles formam um modelo álgebra booleana;



Em 1955 dois cientistas da computação, G.H. Mealy e E.F. Moore, generalizaram a teoria dos autômatos para máquinas mais poderosas em papéis separados, as máquinas de estados finitos, a máquina de Moore e a máquina Mealy são nomeadas em reconhecimento do seu trabalho.



Klaus Samelson e Friedrich L. Bauer, da Universidade Técnica de Munique, propuseram uma ideia de maquina de pilha em 1955 e Friedrich solicitou uma patente

em 1957. Foi desenvolvido o mesmo conceito, de forma independente, pelo australiano Charles Hamblin no primeiro semestre de 1957; 

A teoria sobre Linguagem Formal teve seu início sobre uma base empírica com o artigo de Chomsky, "Three models of language" publicado em 1956, assim considerando uma gramática como um mapeamento de cadeias finitas de símbolos.



Chomsky estava procurando por uma teoria para explicar ou pelo menos revelar as implicações sobre a capacidade de uma linguagem extrair sua gramática a partir de um número finito de enunciados e usá-las para construir novas sentenças, todas elas também gramáticas, ou também prontamente rejeitar sequências gramaticais. Assim, em 1958, ele fez a conexão com autômatos finitos através de uma investigação colaborativa com George Miller sobre linguagens de estados finitos;



Em 1959, Chomsky introduziu linguagens determinadas por gramáticas, entre elas as gramáticas livres de contexto;



Seymour Ginsburg e H.G. Rice demonstraram em 1961 que grande parte da gramática da linguagem de programação Algol, eram livres de contexto, o que fez assim as gramáticas livres de contexto tão importantes;



Entre o período de 1962 a 1968, a partir de uma mistura de trabalhos teóricos e práticos, realizados nos Estados Unidos e na Alemanha, envolvendo o estudo sobre a fórmula de tradução seqüencial para compiladores, a gestão dos procedimentos recursivos, e a análise sintática para a tradução automática mais ou menos independente levou à noção de "pilha", ou lista de elementos acessíveis em apenas uma extremidade. Na linguagem da teoria de autômatos, uma pilha fornece a um autômato finito uma espécie de memória adicional na forma de uma fita que corre para os dois lados, mas sendo movida apenas uma célula de cada vez e apenas contendo dados colocados lá pelo autômato durante a operação. Schützenberger e Chomsky mostraram que tal "autômatos pushdown” (autômatos de pilha) correspondem exatamente às linguagens livres de contexto;



No final dos anos 1960, a teoria dos autômatos e linguagens formais tinha assumido forma canônica em torno de uma agenda própria. Em 1969, John Hopcroft e Jeffrey Ullman começaram seu texto, Linguagens Formais e sua relação com Autômatos, destacando as gramáticas de Chomsky, a definição livre de contexto do ALGOL, compilação dirigida pela sintaxe e o conceito do compilador-compilador.

3. Autômato de Pilha Analogamente às Linguagens Regulares, a Classe das Linguagens Livres do Contexto pode ser associada a um formalismo do tipo autômato, denominado Autômato com Pilha. O Autômato com Pilha é análogo ao Autômato Finito que reconhece as Linguagens Livre de Contexto, basicamente um AFND𝜀 (Autômato Finito não-Determinístico), incluindo uma pilha como memória auxiliar e a facilidade de não determinismo.

A pilha é independente da fita de entrada e não possui limite máximo de tamanho ("infinita"). Estruturalmente, sua principal característica é que o último símbolo gravado é o primeiro a ser lido (FIFO last in first out). Ao contrário da fita de entrada, a pilha pode ser lida e alterada durante um processamento;  

A base de uma pilha é fixa e define o seu início. O topo é variável e define a posição do último símbolo gravado.

3.1 Definição Formal Um Autômato de Pilha 𝑀 é uma tupla: 𝑀=

, 𝑄,

, 𝑞0, 𝐹, 𝑉

Onde: : Alfabeto de símbolos de entrada; 𝑄 : Conjunto finito de estados;

: Função 𝑝𝑟𝑜𝑔𝑟𝑎𝑚𝑎 ou função transição; =

𝑄,

∗

, 𝑉∗

𝑥

𝑄 𝑥 𝑉∗

𝑞0 : Estado inicial do autômato tal que 𝑞0 é elemento de 𝑄 ;

𝐹: Conjunto de estados finais tal que 𝐹 está contido em 𝑄 ; 𝑉: Alfabeto da pilha;

4. Autômato de Duas Pilhas O Autômato com Duas Pilhas ou simplesmente Autômato com Pilhas é uma Máquina Universal similar a Máquina com Duas Pilhas. A principal diferença é que o programa é especificado, usando a noção de estados (de forma análoga a Máquina de Turing), e não como um diagrama de fluxos. Diagramas de fluxos são úteis no desenvolvimento de algoritmos e na visualização da sua estruturação e computação. Já as Máquinas com estado são mais indicadas para estudos teórico-formais, pois facilita provas e estudos de facilidades especiais como não-determinismo. Adicionalmente, simuladores de modelos baseados em estados são, em geral, mais fáceis de serem implementados. A abordagem que segue é muito usada no estudo das Linguagens Formais. Um Autômato com Pilhas é composto, basicamente, por quatro partes:  

Fita: Dispositivo de entrada que contem a informação a ser processada; Pilhas: Memórias auxiliares que pode ser usadas livremente para leitura e gravação;

 

Unidade de Controle: Reflete o estado corrente da Máquina. Possui um cabeça de fita e uma cabeça para cada pilha; Programa ou Função de Transição: Comanda a leitura da fita, leitura e gravação das pilhas e define o estado da Máquina;

Uma pilha é dividida em células, armazenando, cada uma, um símbolo do alfabeto auxiliar (pode ser igual ao alfabeto de entrada). Lembre-se que, em uma estrutura do tipo pilha, a leitura e a gravação são sempre na mesma extremidade (topo). Uma pilha não possui um tamanho fixo e nem máximo, sendo seu tamanho corrente igual ao tamanho da palavra armazenada. Seu valor inicial é vazio. A unidade de controle possui um número finito e predefinido de estados. Possui uma cabeça de fita e uma cabeça para cada pilha, como segue: 



Cabeça de Fita: Unidade de leitura a qual acessa uma célula da fita de cada vez e movimenta-se exclusivamente para a direita. É possível testar se a entrada foi completamente lida; Cabeça de Pilha: Unidade de leitura e gravação para cada pilha a qual move para cima ao gravar e para baixo ao ler um símbolo. Acessa um símbolo de cada vez, estando sempre posicionada no topo. A leitura exclui o símbolo lido (leitura destrutiva). É possível testar se a pilha está vazia;

O programa é uma função parcial que, dependendo do estado corrente, do símbolo lido da fita e o símbolo lido de cada pilha, determina o novo estado e o símbolo a ser gravado em cada pilha.

4.1 Definição Formal Um Autômato com Duas Pilhas 𝑀 ou simplesmente Autômato com Pilhas 𝑀 é uma tupla: 𝑀=

, 𝑄,

, 𝑞0, 𝐹, 𝑉

Onde: : Alfabeto de símbolos de entrada; 𝑄 : Conjunto de estados possíveis do autômato a qual é finito; : Função 𝑝𝑟𝑜𝑔𝑟𝑎𝑚𝑎 ou função transição: =

𝑄𝑥

∪

𝜀, ?

𝑥

𝑉∪

𝜀, ?

𝑥

𝑉∪

𝜀, ?

→

𝑞0 : Estado inicial do autômato tal que 𝑞0 é elemento de 𝑄 ;

𝐹: Conjunto de estados finais tal que 𝐹 está contido em 𝑄 ; 𝑉: Alfabeto das pilhas;

As seguintes características da função 𝑝𝑟𝑜𝑔𝑟𝑎𝑚𝑎 devem ser consideradas:

𝑄𝑥

𝑉∪

𝜀

𝑥

𝑉∪

𝜀







A função pode não ser total, ou seja, pode ser indefinida para alguns argumentos do conjunto de partida; a omissão do parâmetro de leitura, representado por "? ", indica o teste da correspondente pilha vazia ou toda palavra de entrada lida; O símbolo 𝜀 na leitura da fita ou de alguma pilha indica que o autômato não lê nem move a cabeça. Note-se que pelo menos uma leitura deve ser realizada ou sobre a fita ou sobre alguma pilha; O símbolo 𝜀 na gravação indica que nenhuma gravação é realizada na pilha (e não move a cabeça); Resumidamente, a função 𝑝𝑟𝑜𝑔𝑟𝑎𝑚𝑎 considera:

  

Estado corrente; Símbolo lido na fita (pode ser omitido) ou teste se toda palavra de entrada foi lida; Símbolo lido de cada pilha (pode ser omitido) ou teste de pilha vazia; Para determinar:

 

Novo estado; Símbolo gravado em cada pilha (pode ser omitido);

Por exemplo,

𝑝, ? , 𝑎, 𝜖

= {(𝑞, 𝜀, 𝑏)} indica que:

Se:    

No estado 𝑝 A entrada foi completamente lida (na fita) O topo da pilha 1 contem o símbolo 𝑎 Não lê da pilha 2 Então:

  

Assume o estado 𝑞 Não grava na pilha 1 Grava o símbolo 𝑏 no topo da pilha 2

Analogamente à Máquina de Turing, a função programa de um Autômato com Pilhas pode ser representada como um grafo direto, como na “Figura 1”.

Figura 1: Representação da função programa como um grafo. O processamento de um Autômato com Pilhas, para uma palavra de entrada 𝜔, consiste na sucessiva aplicação da função programa para cada símbolo de 𝜔 (da esquerda para a direita) até ocorrer uma condição de parada. Entretanto, é possível que um Autômato com Pilhas nunca atinja uma condição de parada. Nesse caso, fica processando indefinidamente (ciclo ou loop infinito). Um exemplo simples de ciclo infinito é um programa que empilha e desempilha um mesmo símbolo indefinidamente, sem ler da fita. As condições de parada são as seguintes:  

Estado Final: O autômato assume um estado final: o autômato para e a palavra de entrada é aceita; Função Indefinida: A função programa é indefinida para o argumento: o autômato para e a palavra de entrada é rejeitada;

4.2 Exemplos Definição dos Símbolos - Autômato de duas Pilhas    

 

Ent – O que se está lendo como entrada; P1 – Pilha número 1; P2 – Pilha número 2; N – Na parte de leitura da pilha significa que não importa o que se está lendo no topo da pilha. Na parte de escrita da pilha significa que se mantém o conteúdo atual do topo da pilha; E – Eliminação do conteúdo do topo da pilha; [ ] – Pilha vazia.

Formato das Transições   

Ent – Símbolo lido na entrada; P1 – Símbolo lido no topo da pilha 1 | Símbolo escrito no topo da pilha 1; P2 – Símbolo lido no topo da pilha 2 | Símbolo escrito no topo da pilha 2.

4.2.1

𝐿 = 𝑎𝑚 𝑏 𝑚 𝑐 𝑚 𝑚 ≥ 1

Figura 2: Autômato reconhecedor da linguagem L = 𝒂𝒎 𝒃𝒎 𝒄𝒎 𝒎 ≥ 𝟏

4.2.2

𝐿 = 𝑎𝑛 𝑏 𝑚 𝑐 𝑚 𝑑 𝑛 𝑛, 𝑚 ≥ 1

Figura 3: Autômato reconhecedor da linguagem L = 𝒂𝒏 𝒃𝒎 𝒄𝒎 𝒅𝒏 𝒏, 𝒎 ≥ 𝟏

5. Equivalência Autômato de Duas Pilhas x Maquina de Turing 



Máquina de Turing → Autômato com Duas Pilhas: A estrutura de fita da Máquina de Turing é simulada usando as duas pilhas como segue: a pilha 1 simula o conteúdo da fita à esquerda da cabeça da fita, e a pilha 2, o conteúdo à direita; Autômato com Duas Pilhas → Máquina de Turing: A fita e as duas pilhas do Autômato com Duas Pilhas são simuladas, usando a fita da Máquina de Turing, como segue: o A palavra de entrada corresponde às primeiras posições da fita da Máquina de Turing; o A pilha 1 corresponde a todas as células anteriores a palavra de entrada; o Analogamente, a pilha 2 corresponde a todas as células posteriores a palavra de entrada;

Portanto, o formalismo Máquina de Turing pode ser simulado pelo formalismo Autômato com Duas Pilhas e vice-versa. Logo, são formalismos equivalentes.

5.1 Modelo Geral Considerando um autômato de duas pilhas “A” e uma Máquina de Turing “M”, para que M seja equivalente a “A”, é necessário seguir os seguintes passos: 1. Marcar o início e o fim da entrada, ou seja, preencher os espaços em branco encontrados imediatamente à esquerda do primeiro símbolo da entrada(𝑠1 ) e o imediatamente à direita do último símbolo da entrada (𝑠2 ), com {𝑠𝑛 /𝑠 ∈ 𝛽 e (𝛽 ∩ ฀ ฀∅)}. É necessário verificar se(𝑠1 = 𝑠2 ) não acarretará em dificuldades para o funcionamento de M. (Figura 4);

Figura 4: Marcação das extremidades da entrada. 2. Determinar uma regra para o local onde as pilhas serão construídas. Neste trabalho estamos considerando que P1 cresce à esquerda da entrada, no sentido direita para esquerda (ou seja, o topo da pilha P1 se encontra no elemento mais à esquerda da fita) e P2 cresce à direita da entrada, no sentido esquerda para direita (ou seja, seu topo se encontra no elemento mais à direita da fita). (Figura 5);

Figura 5: Adaptação das duas Pilhas.

Também encontramos alguns trabalhos que usam os espaços ímpares para P1 e os pares para P2, mas consideramos esta abordagem muito complexa. 3. Agora, toda vez que uma regra de “A” mencionar uma escrita em P1, é necessário usar o deslocamento " ← "até que se encontre um espaço em branco, e escrever neste. Para escrever no topo de P2, usa-se o deslocamento " → " até encontrar um espaço em branco, e escrever neste; 4. Quando uma regra de “A” indicar que o topo de uma das pilhas precisa ser apagado é necessário, para apagar o topo de P1, deslocar-se para a esquerda até encontrar um espaço em branco e logo depois deslocar em um (1) espaço para a direita, encontrando assim o topo de P1, e sobrescrevendo qualquer símbolo lá existente pelo símbolo branco. Já quando se trata de P2, desloca-se para a direita até encontrar um elemento em branco e logo depois se desloca em um (1) espaço para a esquerda, chegando assim no topo de P2, e sobrescrevendo o símbolo lá presente por um símbolo branco; 5. Quando se lê um símbolo da entrada na fita, precisa-se marcar este símbolo como lido (substituindo-o por algum símbolo 𝑠, sendo 𝑠 ≠ 𝑠1e 𝑠 ≠ 𝑠2), para que, após a computação seja possível retornar à entrada original, para este mesmo fim é importante que cada símbolo do alfabeto da entrada seja substituído por um 𝑠 diferente; 6. Após a leitura de toda a entrada, é possível notar se a palavra da entrada pertence à linguagem testada se, imediatamente à esquerda de 𝑠1 e imediatamente à direita de 𝑠2 os espaços estão em branco; 7. Em caso positivo, desloca-se até o espaço de 𝑠2 , substituindo-o por espaço em branco, bem como substituindo todo símbolo 𝑠 pelo seu equivalente no alfabeto de entrada, e chegando ao espaço de 𝑠1 também substituí-lo pelo espaço em branco, terminando assim a transformação de “A” em “M”. 5.2 Exemplos de conversão – Autômato de Duas Pilhas ↔ Máquina de Turing Definição dos Símbolos – Máquina de Turing   

Br – Representação de um espaço em Branco na fita; = > – Deslocamento para a direita na fita; < = – Deslocamento para a esquerda na fita;

Formato das Transições (1, 2, 3) 1 - Símbolo lido na entrada da fita, 2 - símbolo escrito na fita e 3 - deslocamento na fita.

5.2.1

𝐿 = 𝑎𝑚 𝑏 𝑚 𝑐 𝑚 𝑚 ≥ 1

Figura 6: Máquina de Turing reconhecedora da linguagem L = 𝒂𝒎 𝒃𝒎 𝒄𝒎 𝒎 ≥ 𝟏, simulando a execução de um Autômato de Duas Pilhas. 5.2.2

𝐿 = 𝑎𝑛 𝑏 𝑚 𝑐 𝑚 𝑑 𝑛 𝑛, 𝑚 ≥ 1

Figura 7: Máquina de Turing reconhecedora da linguagem L 𝑎𝑛 𝑏 𝑚 𝑐 𝑚 𝑑 𝑛 𝑛, 𝑚 ≥ 1, simulando a execução de um Autômato de Duas Pilhas.

=

6. Conclusão Sendo assim, conclui-se que o poder computacional de um Autômato com Duas Pilhas é equivalente ao poder computacional de um Autômato com Múltiplas Pilhas. Ou seja, se um problema é solucionado por um Autômato com Múltiplas Pilhas, o mesmo problema pode ser solucionado por um Autômato de Duas Pilhas. E por fim, o Autômato com Duas Pilhas possui o mesmo poder computacional da Máquina de Turing, que é considerada o dispositivo mais geral da computação. Assim, se existe um algoritmo para resolver um problema, então esse algoritmo pode ser expresso com o Autômato de Duas Pilhas.

Referências Diverio, Tiarajú A., and Paulo B. Menezes. Teoria da Computação: Máquinas Universais e Computabilidade-Vol. 5. Bookman, 2011. Menezes, Paulo Blauth. Linguagens Formais e Autômatos: Volume 3 da Série Livros Didáticos Informática UFRGS. Bookman. Mônica Xaveier Py. Análise da Máquina de Turing Persistente com Múltiplas Fitas de Trabalho. Dissertação de mestrado, 2003. Disponível em: https://www.lume.ufrgs.br/bitstream/handle/10183/3419/000400280.pdf?sequence=1, acessado em 30 de novembro de 2015. Prof. Gláucya Carreiro Boechat. Autômato de Pilha. Disponível em: http://www.cin.ufpe.br/~gcb/tc/tc_automato_pilha.pdf, acessado em 30 de novembro de 2015. COMPUTER SCIENCE, The Search for a Mathematical Theory Michael S. Mahoney Program in History of Science, Princeton. Disponível em: University.http://www.princeton.edu/~hos/h593/20thcent.fin.wp.html, acessado em 30 de novembro de 2015. Friedrich L. Bauer, Inventor of the stack and of the term software engenieering. Disponível em: http://people.idsia.ch/~juergen/bauer.html, acessado em 30 de novembro de 2015....