Autômato com Pilha

Prévia do material em texto

Autômato com pilha 
Larissa Fernandes 
Universidade do Estado do Rio Grande do Norte (UERN) – Curso de Ciência da 
Computação – Campus Universitário Central 
Av. Professor Antônio Campos, S/N – Bairro Costa e Silva – CEP 596000-000 – 
Mossoró – RN 
Abstract. ​Context-Free Languages (CFL) encompass a broader approach than                 
Regular Languages by properly addressing the issues of parenthesis and                   
program block balancing. Its algorithms are simple and have good efficiency.                     
This report describes the main characteristics of a Pushdown Automaton, a                     
CFL recognizer, in order to complement the seminar presented in the                     
Computer Theory course. 
Resumo. ​As Linguagens Livres de Contextos (LLC) compreendem uma                 
abordagem mais ampla do que as Linguagens Regulares tratando, de forma                     
apropriada, as questões de balanceamentos entre parênteses e blocos de                   
programas. Seus algoritmos são simples e possuem uma boa eficiência. Este                     
relatório descreve as principais características de um Autômato com Pilha, um                     
reconhecedor das LLC, de forma a complementar o seminário apresentado na                     
disciplina de Teoria da Computação. 
1. Introdução 
As Linguagens Livres de Contexto são geradas por uma gramática livre de contexto                         
(GLC) e são importantes para definir linguagens de programação, onde a maioria das                         
expressões aritméticas são geradas por uma GLC. 
Os Autômatos com Pilha são reconhecedores das Linguagens Livres de                   
Contexto, sendo os não-determinísticos mais usuais. Eles possuem uma memória                   
auxiliar, uma pilha de armazenamento infinito, para o processamento da entrada, isso                       
garante uma poder de reconhecimento estendido, comparado ao dos autômatos finitos. 
Pela definição de pilhas, sabemos que o último que entra é o primeiro que sai.                             
Assim, neste Autômato, ela é dividida em células que comportam apenas um símbolo                         
cada e sua leitura e gravação são feitas pelo topo. 
2. Definição Formal 
O Autômato com Pilha é um sétuplo M = (Q, Σ, Γ, ∆, Z, s, F) onde: 
Q: Conjunto finito dos estados do autômato; 
Σ: Alfabeto de entrada; 
Γ: Alfabeto da pilha; 
∆ ​⊆ ((Q × Σ*​ ​× Γ*) × (Q × Γ*​)), a relação finita de transição.; 
Z ∈ Γ: Símbolo inicial da pilha; 
s ∈ Q: Estado inicial do autômato; 
F ⊆ Q: Conjunto dos estados finais. 
O alfabeto da pilha Γ especifica os símbolos que podem ser armazenados na                         
pilha. Um desses símbolos, o Z, representa o conteúdo inicial da pilha sempre que o                             
autômato tem início e reconhece uma nova sentença. Os elemento deΓ são adicionados                           
ou removidos da pilha ao longo da operação. 
3. Composição 
3.1. Fita 
É o dispositivo de entrada que possui a informação que será processada e é dividida em                               
células. 
3.2. ​ ​Pilhas 
O Autômato é constituído de duas pilhas. Elas são as memórias auxiliares que podem                           
ser usadas tanto para leitura quanto para gravação. Uma pilha é dividida em células,                           
onde cada uma armazena um símbolo do alfabeto auxiliar que pode ser igual ao de                             
entrada. Sendo seu valor inicial vazio, não possui um tamanho fixo ou                       
máximo, e seu tamanho tende a ser igual ao tamanho da palavra armazenada. 
3.3. Unidade de Controle 
Reflete o estado corrente da máquina. Possui um número finito e predefinido de estados,                           
além de uma “Cabeça da Fita” (unidade de leitura que acessa uma célula da fita de cada                                 
e movimenta-se apenas para a direita), e uma “Cabeça da Pilha” (sendo uma para cada                             
pilha, é uma unidade de leitura e gravação que se move para cima ao gravar e para baixo                                   
ao ler um símbolo. A leitura exclui o símbolo lido). 
3.4. Função de Transição 
Comanda a leitura da fita, define o estado da máquina e a leitura e gravação das pilhas.                                 
É uma função que determina um novo estado e símbolo a ser gravado dependendo do                             
estado corrente, símbolo lido da fita e dos lidos em cada pilha. A função pode ser                               
indefinida para alguns argumento do conjunto de partida. 
O símbolo ε na leitura da fita ou de uma pilha, indica que não há leitura e nem                                   
movimento por parte do autômato. Enquanto que ε na gravação, indica que nenhuma                         
gravação e movimento estão sendo realizados. 
4. Processamento de um Autômato com Pilha 
Considerando uma palavra w como entrada, o processamento consiste na sucessiva                     
aplicação da função de transição para cada símbolo da palavra (da esquerda para a                           
direita), até que ocorra uma condição de parada. 
5. Condições de parada 
4.1. Estado Final 
O autômato assume um estado final e para. A palavra é aceita. 
   
4.2. Função Indefinida 
A função de transição é indefinida para o argumento e o autômato para. A palavra é                               
rejeitada. 
4.3. ​ ​Pilha vazia 
A pilha está vazia quando não existe nenhum símbolo de Γ. A palavra é aceita. 
5. Referências 
Morais, J. ​Autômatos com Pilha ​. Disponível em:             
<http://www2.unifap.br/furtado/files/2016/03/aula04_automatospilha.pdf>. Acesso:   
9 de Julho de 2018. 
Casillo, D. ​Teoria da Computação: Máquina com Pilhas e Autômato com duas                       
pilhas ​. Disponível em:     
<http://www2.ufersa.edu.br/portal/view/uploads/setores/166/arquivos/CienciaCompu
tacao/Maquina_com_Pilhas_e_Automatos_com_Pilhas.pdf>. Acesso: 9 de Julho de           
2018. 
Rangel, J. ​Linguagens livres de contexto e autômatos de pilha. ​Disponível em:                       
<http://www.inf.puc-rio.br/~inf1626/Apostila/lf6.pdf>. Acesso: 10 de Julho de 2018. 
Sousa, S. ​Teoria da Computação: Autómatos com pilha​. Disponível em:                   
<https://www.di.ubi.pt/~desousa/2012-2013/TC/pushdown.pdf>. Acesso: 10 de       
Julho de 2018. 
Departamento de Ciência de Computadores da FCUP. ​Autómatos de Pilha​. Disponível                     
em: <https://www.dcc.fc.up.pt/~nam/aulas/0102/mc/slides/slimc14.pdf>. Acesso: 10       
de Julho de 2018. 
Prado, S. ​Linguagens Livres de Contexto​. Disponível em:               
<http://wwwp.fc.unesp.br/~simonedp/zipados/TC03.pdf>. Acesso: 10 de Julho de           
2018.