Autômatos com Pilha e Maquina de TuringFinal

Prévia do material em texto

Mestrado em Sistemas e Computação
Universidade Salvador – UNIFACS
Docente: Prof. Dr. Eldman
Discentes: Carlos Rogério, Ciro Júnior e Robson Gonzaga.
Reconhecedores de Linguagens: 
Autômatos e Máquina de Turing 
AGENDA
OBJETIVOS
METODOLOGIA
INTRODUÇÃO
AUTÔMATOS FINITOS
AUTÔMATOS DE PILHA
MAQUINA DE TURING
CONSIDERAÇÕES FINAIS
2
OBJETIVO
• Revisar a literatura disponível em relação a teoria da computação,
especificamente sobre os modelos matemáticos reconhecedores de
linguagens, conhecidos como Autômatos e Maquina de Turing;
• Identificar as relações e diferenças existentes entre:
3
Autômatos Finitos Autômatos de Pilha Máquina de Turing
• A Computação vem sendo utilizada como forma de solucionar problemas,
desenvolvendo, autômatizado e simplificando soluções;
• Constantes estudos buscam desenvolver soluções computáveis eficiêntes
para os mais diversos fíns;
• Uma das grandes questões que busaca-se no estudo da Teoria da
Computação é entender os problemas que realmente são computáveis ou
não.
INTRODUÇÃO
4
• Segundo [Diveiro; Menezes, 2009], a Teoria da Computação surgiu antes da
invenção dos computadores, e estuda modelos formais de computação,
sua aplicabilidade e sua viabilidade prática à resolução das diversas
classes existentes de problemas;
• A Teoria da Computação propõe, comparar modelos de computação, as
classes de problemas que cada um deles consegue resolver e os limites a
que cada qual está sujeito [DIVEIRO; MENEZES, 2009];
• Nesse contexto, o estudo dos Autômatos e da Maquina de Turing são de
fundamental importância dentro da Teoria da Computação;
INTRODUÇÃO
5
• Segundo [Diveiro; Menezes, 2009], a Teoria da Computação ssurgiu antes
da invenção dos computadores, e estuda modelos formais de
computação, sua aplicabilidade e sua viabilidade prática à resolução das
diversas classes existentes de problemas;
• A Teoria da Computação propõe, comparar modelos de computação, as
classes de problemas que cada um deles consegue resolver e os limites a
que cada qual está sujeito [DIVEIRO; MENEZES, 2009];
• Nesse contexto, o estudo dos Autômatos e da Maquina de Turing são de
fundamental importância dentro da Teoria da Computação;
INTRODUÇÃO
6
• Segundo [Prado, 2009] a linguagem regular:
– Trata-se de uma linguagem mais simples;
– É possível desenvolver algoritmos de reconhecimento ou de geração de pouca
complexidade;
– Possui grande eficiência e é de fácil implementação.
“Todas as linguagens finitas (com um número finito de palavras) são
Regulares” [Lima, 2009].
LINGUAGENS REGULARES
7
• Na visão de [Sthepan; Phuong, 2010], tais linguagens regulares, são
utilizadas para “descrever dispositivos que utilizam computação simples,
como os autômatos finitos (AFs)”.
• Uma das características das linguagens regulares, se dá pela sua grade
importância no processo de análise sintática das linguagens de
programação [Sthepan; Phuong, 2010].
LINGUAGENS REGULARES
8
• De acordo com a descrição de [Prado, 2009], as Linguagens Livres de
Contexto são:
– Mais amplas do que as Linguagens Regulares;
– Trata de forma apropriada as questões de balanceamento entre parênteses e blocos
de programas;
– “Os seus algoritmos são simples e possuem uma boa eficiência”.
LINGUAGENS LIVRES DE CONTEXTO
9
• Para [Déharbe, 2003], “o conjunto de todas as linguagens livres de contexto
é idêntico ao conjunto de linguagens aceitas por um autômato de pilha”.
• Essa característica torna a linguagem passível de análise.
LINGUAGENS LIVRES DE CONTEXTO
10
• Devido à complexibilidade de algumas aplicações, torna-se necessário a
utilização de linguagens mais sofisticadas, que envolvem a utilização de
formalismo mais sofisticado.
• Segundo [Vieria, 2004], “as linguagens de expressões aritméticas
normalmente contém todas as palavras na forma: ( nx0+x1)+x2) · · · +xn)”.
• Observa-se que tais linguagens não são regulares e por tanto não podem
ser reconhecidas pelos Autômatos Finitos.
AUTÔMATOS COM PILHA (AP) 
11
• Segundo [Lehrer, 2016], afirma que “Intuitivamente, um AF não pode
reconhecer a linguagem descrita porque não tem uma memória poderosa
o suficiente para “lembrar” que leu n ocorrências de certo símbolo, para n
arbitrário”.
• Os Autômatos com Pilha (APs), são:
– modelos matemáticos capazes de reconhecer linguagens livres de contextos;
– Na visão de [Álvares, 2017] é uma extensão dos Autômatos Finitos, com o diferencial
de adicionar uma memória organizada em uma estrutura do tipo pilha.
AUTÔMATOS COM PILHA (AP)
12
• Segundo [Michael, 2014], os APs se diferenciam dos AFDs por duas
características principais:
– 1- “Eles podem fazer uso da informação que está no topo da pilha para decidir qual
transição deve ser efetuada”;
– 2- “Eles podem manipular a pilha ao efetuar uma transição”.
AUTÔMATOS COM PILHA (AP)
13
• Outro diferencial dos Autômatos de Pilha em relação aos Autômatos Finitos
é a ausência de estados finais predeterminados.
• De acordo com [Maldonado; Costa, 2017], “uma cadeia X é aceita se, ao
chegar ao final do processamento da mesma, a pilha estiver vazia,
independente do estado em que o Autômato se encontra”.
AUTÔMATOS COM PILHA (AP)
14
• Nos Autômatos de Pilha, “além do alfabeto da fita haverá o alfabeto da
pilha (não necessariamente disjunto do da fita)” [Vieria, 2004].
• Essa condição possibilita:
– A transição de estados a partir da análise do símbolo de entrada (da fita) em
conjunto com a análise do símbolo do topo da pilha, em bora seja possível considerar
somente o símbolo de entrada da fita, como afirma [Vieria, 2004].
AUTÔMATOS COM PILHA (AP)
15
• Na visão de [Michael, 2014], os Autômatos com Pilha escolhem uma
transição de acordo com a análise de três elementos:
– Símbolo atual na cadeia de entrada;
– Estado atual;
– Topo da pilha.
• “Máquinas de estados finitos convencionais apenas analisam o símbolo na
cadeia de entrada e o estado atual” [SIPSER, 2007], a pilha é utilizada
como um recurso auxiliar.
AUTÔMATOS COM PILHA (AP)
16
AUTÔMATOS COM PILHA (AP)
17
Autômatos 
Finitos
Cadeia de 
Entrada
Estado Atual
Autômatos 
Finitos
Cadeia de 
Entrada
Estados Atual
Topo da Pilha
X
• Um Autômato de Pilha, pode ser definido formalmente por uma 6-tupla (Q,
Σ, Γ, Δ, q0, F) [Menezes, 2014; Vieira, 2004; Alvares, 2017], onde:
– Q é um conjunto finito de estados;
– Σ é um conjunto finito de símbolos, chamado de alfabeto de entrada;
– Γ é um conjunto finito de símbolos, denominado alfabeto da pilha;
– Δ (ou g) ⊆ ( Q x Σ* x Γ*) x (Q x Γ) é a relação de transição;
– q0∈ Q é o estado inicial;
– F ⊆ Q é um conjunto de estados de aceitação.
AUTÔMATOS COM PILHA (AP)
18
AUTÔMATOS COM PILHA (AP)
19
Figura 1: Estrutura de um Autômato de Pilha [Vieira, 2004].
• Algumas observações:
– Autômatos com duas pilhas, são equivalentes a Maquina de Turing;
– Os Autômatos de Pilha, são limitados na gestão de memória devido a limitação da
disciplina LIFO (Last In First Out).
AUTÔMATOS COM PILHA (AP)
20
BREVE HISTÓRICO
• 1912 - Nascimento de Alan Turing em Londres;
• 1934 - Graduou-se em Matemática na Universidade de Cambridge
• 1936 - Continuou seus estudos na Universidade, nos Estados Unidos, onde obteve seu PhD em logica matemática, sob a
orientação do professor americano Alonzo Church. Neste mesmo ano Church inventou o formalismo computacional chamado
Cálculo Lambda.
• 1937 - Turing começou a trabalhar com Church e, juntos, eles provaram a equivalência de seus trabalhos, que ficou conhecida
como a Tese de Church-Turing.
• 1939 - 1945 - Turing trabalhou para o governo britânico, ajudando a projetarmaquinas eletromecânicas para decifrar as
comunicações de radio alemãs, cuja codificação era produzida por um sistema chamado de Enigma.
• 1942 - A necessidade de decifrar as mensagens de forma mais rápida possível, dada a situação da guerra, levou Turing e os
demais cientistas a participarem do projeto do Colossus, o primeiro computador eletrônico e digital completamente funcional.
• 1950 - Em seu famoso artigo “Computing Machinery and Intellingence”, fez previsões sobre o que seria necessário para um
computador se passar por um ser humano e lançava as bases para a inteligência artificial.
• 1954 - Turing faleceu em Manchester, Inglaterra, vitima de suicídio, apos comer uma maça envenenada com cianureto.
MÁQUINA DE TURING
21
CARACTÉRISTICAS
A maquina abstrata de Turing é constituída de três partes: fita, unidade de controle e função de
transição(o programa).
• Fita: Usada simultaneamente como dispositivo de entrada, saída e memória de armazenamento;
• Unidade de controle: Reflete o estado corrente da máquina. Possui uma unidade de leitura e
gravação (cabeça da fita), a qual acessa uma célula de cada vez e movimenta-se para a direita ou
para a esquerda.;
• Função de transição : Define o estado da maquina e comanda a leitura, gravação e o sentido do 
movimento da cabeça da fita. 
MÁQUINA DE TURING
22
CARACTÉRISTICAS
•Para [29], uma Máquina de Turing é uma 8-upla:
•M =(∑, Q, Π, q0, F, V, β, ¤)
•∑ alfabeto de símbolos de entrada;
•Q conjunto de estados possíveis da máquina, o qual é finito;
•Π programa ou função de transição: (é uma função parcial)
•q0 estado inicial da máquina, tal que q0 é elemento de Q;
•F conjunto de estados finais, tal que F está contido em Q;
•V alfabeto auxiliar;
•β símbolo especial branco;
•¤ símbolo especial marcador de início da fita.
MÁQUINA DE TURING
23
EXEMPLOS
VIDEO: EXECUÇÃO ACEITE;
VIDEO: EXECUÇÃO COM PARADA;
MÁQUINA DE TURING
24
REFERÊNCIAS
25
[1] DIVERIO, Tiarajú A.; MENEZES, Paulo B. Teoria da Computação - UFRGS: Máquinas Universais e 
Computabilidade. Bookman Editora, 2009.
[2] NETO, João José. A Teoria da Computação e o profissional de informática. In: Revista de Computação e 
Tecnologia da PUC-SP.
[3] LEVIS, H. R. and C. H. Papadimitriou, Elementos da Teoria da Computação. Porto Alegre: Bookman, 2004.
[4] BACKHOUSE, R.,, Syntax of Programming Languages. London: Prentice-Hall International, 1979.
[5] PRADO, Simone das Gracas Domingues. Teoria da Computacao. Faculdade de Ciencias. Ano: 2009.
REFERÊNCIAS
26
[6] Maria. A. V, LIMA. Lema do Bombeamento: Aplicação para Linguagens Regulares e Livres de Contexto. UFU –
Univesidade Federal de Uberlândia, 2009. Avaliable: http://www.portal.facom.ufu.br/. [Acesso em 15 de outrubro
de 2017].
[7] Cook, STEPHEN; Nguyen, PHUONG. Logical foundations of proof complexity 1. publ. ed. Ithaca, In: Association
for Symbolic Logic.. ISBN 052151729X.
[8] M. FURST, J. B. SAXE, and M. SIPSER. Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory, 
1984, p.13–27.
REFERÊNCIAS
27
[9] D. DÉHARBE. Linguagens Formais: Autômatos com Pilha. UFRN – Universidade Federal do Rios Grande do 
Norte, 2003. Avaliable: http://docplayer.com.br/217189-Automatos-a-pilha-ufrn-dimapdim0330-linguagens-
formais-david-deharbe-http-www-consiste-dimapufrn-br-david-enseignement-2003.html. [Acesso em 18 de 
outubro de 2017].
[14] MENEZES, P. B. Linguagens formais e autômatos. 6. ed. Porto Alegre: Bookman, 2010. 256p. (Série Livros 
Didáticos Informática UFRGS, v.3).
[15] LIMA, Paulo R. Um Software Educacional Para Construção e Validação de Formalismos Utilizados na Geração e 
Reconhecimento de Sentenças de uma Linguagem Regular. Universidade do Vale do Itajaí, 2006.
REFERÊNCIAS
28
16] SILVEIRA, Ricardo A. Autômatos Finitos. INE-CTC-UFSC, 2006. 
Avaliable:http://www.inf.ufsc.br/~ricardo.silveira/INE5317/Laminas/E5317Aula5.pdf. [Acesso em 21 de outubro de 
2017].
[17] LAWSON, Mark V. Finite automata. Chapman and Hall/CRC, 2004. ISBN 1-58488-255-7. Zbl 1086.68074.
[18] MENEZES, I. Informática Teórica Engenharia da Computação. In: Centro de Informática UFPE – Universidade Federal 
de Pernambuco, 2014. Avaliable: http://slideplayer.com.br/slide/1594013/. [Acesso em 24 de outubro de 2017].
[19] Sipser, MICHAEL. Introduction to the Theory of Computation. In: Boston: PWS, 2014. ISBN 0-534-94728-X. Section
1.1: Finite Automata, pp. 31–47.
REFERÊNCIAS
29
[20] Ana. M. A. PRICE and Simão S. TOSCANI. Implementação de Linguagnes de Programação: Compiladores. In: 2. Ed. 
Porto Alegre: Sagra Luzzatto, 2001. 195p ISBN 8524106395.
[21] C. LEHRER, M. Sc. Linguagens Formais e Autômatos: Autômatos 
http://www.ybadoo.com.br/tutoriais/lfa/04/LFA04.pdf. [Acesso em 25 de outrubro de 2017].
[22] VIEIRA, Newton J. Uma Introdução aos Fundamentos da Computação. In: Cengage CTP; Edição: 1ª, p.137-148, ISBN-
10: 8522105081.
[23] ALVARES, Andrei R. Linguagens Formais e Autômatos: Autômatos de Pilha.(AP). In: CEFET-MG – Centro Federal de 
Educação Tecnológica de Minas Gerais, 2017. Avaliable: 
http://homepages.dcc.ufmg.br/~rimsa/documents/decom035/lessons/Aula09.pdf. [Acesso em 30 de outubro de 2017].