View
3
Download
0
Category
Preview:
Citation preview
Modelagem Computacional
Profº Cícero Costa Quarto
ASL09284
Matemática Discreta Avançada
Ana Carolina Cutrim Bessa; Khalil Ravikson Alcantara Do Carmo; Liriel Bezerra Silva; Lucas Vinícius Ferreira
Ribeiro; Rayla Amorim Araújo; Renan Victor Dias Costa.
2
1.Linguagens e Gramáticas
3
◎ Representação :
𝑀 = (𝑆,𝐼, 𝑂, 𝑓, 𝑔, S0)
■ 𝑆 é um conjunto finito de estados;
■ 𝐼 é um conjunto finito de símbolos (alfabeto) de ENTRADA;
■ 𝑂 é um conjunto finito de símbolos (alfabeto) de SAÍDA;
■ 𝑓 é uma função de transição que associa ao próximo estado, 𝑓 ∶ 𝑆 × 𝐼 → 𝑆;
■ 𝑔 é uma função para a saída, que associa o estado atual (S) e entrada à
sua saída, ou o estado inicial (S0)
2.Máquinas de Estados Finitos com Saída
4
◎ Representação simples de uma tabela e seu grafo :
2.Máquinas de Estados Finitos com Saída
I
S a b
S0 S0/0 S0/1
S1 S1/1 S1/0
f/g
● 𝑆 = {S0,S1}
● 𝐼 = {𝑎, 𝑏}
5
3.Máquinas de Estados Finitos sem Saída
◎ Representação
● S é um conjunto finito de estados;
● I é um alfabeto finito;
● f é uma função de transição que associa um próximo estado;
● S0 é o estado inicial;
● F é um subconjunto de S que representa os estados finais.
6
3.Máquinas de Estados Finitos sem Saída
◎ Autômatos finitos:
a) Determinísticos
7
3.Máquinas de Estados Finitos sem Saída
◎ Autômatos finitos:
b) Não Determinísticos
8
3.Máquinas de Estados Finitos sem Saída
◎ Reconhecimento de Linguagem por Máquinas de Estados Finitos
9
3.Máquinas de Estados Finitos sem Saída
◎ Autômatos Finitos Equivalentes
◎ Definição
◎ Autômatos com Pilha
4.Reconhecimento de Linguagem
10
4.Reconhecimento de Linguagem
11
◎ Representação :
𝑀 = (E, Σ, Γ, δ, q0, F)
■ E é um conjunto finito de estados;
■ Σ é um conjunto finito de símbolos (alfabeto) de ENTRADA;
■ Γ é um conjunto finito de símbolos (alfabeto) da pilha;
■ δ relação de transição onde, δ ⊆ (E × Σ* × Γ*) × (E × F*)
■ q0 estado inicial onde, q0 ϵ E
■ F conjunto de estados finais onde, F ⊆ E
4.Reconhecimento de Linguagem
12
◎ Demonstração:
L = {a2 b2 | n ≥ 0}
M = ( {q0, q, q2}, {a,b}, {A,Z}, δ, q0, {q2})
4.Reconhecimento de Linguagem
13
◎ Demonstração:
L = {a2 b2 | n ≥ 0}
M = ( {q0, q, q2}, {a,b}, {A,Z}, δ, q0, {q2})
◎ Alan Turing
◎ Importante participação na Segunda Guerra Mundial
◎ “Pai da Computação”
5.Máquinas de Turing
14
◎ Dispositivo teórico ou máquina universal
◎ Publicação do artigo “On Computable Numbers, with an Application on the
Entscheidungsproblem”, em 1936;
◎ Definição formal × Definição informal
5.Máquinas de Turing
15
5.Máquinas de Turing
16
1 1 0 1 0 1 1 0
Dispositivo de leitura/escrita
Fita de memória
1
Célula
Unidade de Controle- cabeçote◎ Representação
5.Máquinas de Turing
17
◎ Demonstração
*
*101*
◎ O alfabeto é constituído pelos
elementos 0, 1 e *
◎ Calcula-se o sucessor;
◎ A máquina irá, portanto, somar +1 ao
valor já representado pela máquina;
◎ O estado inicial (S0) é o símbolo “*”
5.Máquinas de Turing
18
◎ Estado de Adição
1
1 *01*
5.Máquinas de Turing
19
0
0 *01*
5.Máquinas de Turing
20
◎ Estado de Transporte
0
* 1 0 0 *
5.Máquinas de Turing
21
1
1 1 0 **
5.Máquinas de Turing
22
◎ Estado de Retorno
0
* 1 1 0 *
5.Máquinas de Turing
23
◎ Estado de Parar
*
1 0 *1*
24
REFERÊNCIAS
GERSTING, Judith L. Fundamentos matemáticos para a ciência da computação. LTC, 2001.
ROSEN, KENNETH H. Matemática Discreta e Suas Aplicações. 6. ed. Porto Alegre: AMGH, 2010.
VIEIRA, Newton José. Introdução aos fundamentos da computação: linguagens e máquinas. Pioneira Thomson
Learning, 2006.
“
Não existem métodos fáceis para resolver problemas difíceis
25
RENÉ DESCARTES
Recommended