Upload
cliceres-mack-dal-bianco
View
481
Download
1
Embed Size (px)
DESCRIPTION
Citation preview
slide 1
Introdução à Teoria da Computação
UAB/UFRPE
Eduardo Araújo Oliveira
http://sites.google.com/site/eaoufpe
slide 2
Conceitos Iniciais
• Computadores atuais mais rápidos e poderosos
• Modelos matemáticos
• Autômatos Finitos
slide 3
Autômatos Finitos
• Reconhecedor de palavras ou cadeia de caracteres
• Bons modelos para computadores com capacidade de memória reduzida
• Fazem parte de vários dispositivos eletro-mecânicos
do dia-a-dia
slide 4
Autômatos Finitos
• Exemplo 1
Visão aérea de uma porta automática
slide 5
Autômatos Finitos
• Exemplo 1
O controlador passa de um estado para outro dependendo do estímulo (entrada) que recebe:
O controlador da porta pode estar em 2 estados:
- aberto (significando porta aberta)
- fechado (significando porta fechada)
slide 6
Autômatos Finitos
• Exemplo 1
Entradas: Existem 4 condições de entrada possíveis
Frente: significando que uma pessoa está em pé sobre o tapete da
frente;
Retaguarda: significando que uma pessoa está em pé sobre o tapete
de
dentro;
Ambos: significando que existem pessoas sobre os 2 tapetes;
Nenhum: significando que ninguém está sobre os tapetes.
slide 7
Autômatos Finitos
• Exemplo 1
Entradas: Existem 4 condições de entrada possíveis
slide 8
Autômatos Finitos
• Exemplo 1
Tabela de Transição
slide 9
Autômatos Finitos
• Exemplo 2
Interruptor
Estados: Ligado ou Desligado
slide 10
Autômatos Finitos
• Exemplo 3
Palavra AMOR
Qualquer outra palavra deve ser descartada
slide 11
Autômatos Finitos
• Exemplo 3
Tentativa de leitura da Palavra AMBIENTE
slide 12
Autômatos Finitos
• Controladores para:
– Lavadoras de louça/roupa
– Termômetros eletrônicos
– Relógios digitais
– Calculadoras
– Máquinas de venda automática
slide 13
Autômatos Finitos
• O AF é uma máquina, reconhecedora de palavras ou cadeia de caracteres, que sempre pára retornando uma resposta sim (cadeia reconhecida) ou não (cadeia não conhecida)
• Podem ser classificados em:
– Autômatos Finitos Determinísticos (AFD)
– Autômatos Finitos Não-Determinísticos (AFND)
slide 14
Autômatos Finitos Determinísticos – Definição Formal
Definição formal de um Autômato Finito Determinístico:
Um Autômato Finito Determinístico (AFD) M é uma 5-upla:
M = (Q, Σ, δ, q0, F), onde
Q: conjunto finito de estados do autômato;
Σ: alfabeto de símbolos de entrada;
δ: função programa ou função de transição (parcial) δ: Q × Σ → Q. Significa dizer que permanecendo em um estado e lendo um símbolo do alfabeto faz o autômato passar para outro estado ou mesmo ficar no mesmo
q0: estado inicial (q0∈Q)
F: conjunto de estados finais ou estados de aceitação (F⊆Q)
slide 15
Um alfabeto Σ é um conjunto finito (não-vazio) de símbolos
Ex.: Alfabetos
Σ1 = {0,1}
Σ2 = {a, b, c, …, z}
Uma cadeia (string) em um alfabeto Σ é uma
seqüência finita de símbolos deste alfabeto
Ex.: Cadeias
01001
abracadabra
Autômatos Finitos Determinísticos – Cadeias e Linguagens
slide 16
Se w = w1w2…wn é uma cadeia sobre Σ, o
comprimento de w, denotado por |w|, é n
A cadeia de comprimento 0, é denominada cadeia nula e é representada por λ
Ex.: |abracadabra| = 11
Autômatos Finitos Determinísticos – Cadeias e Linguagens
slide 17
Se u = u1u2…un e v = v1v2
…vm são cadeias no
alfabeto Σ, então a concatenação de u com v, denotada por uv, é definida por:
uv = u1u2…unv1v2
…vm
Ex.: u = abra e v = cadabra ⇒ uv = abracadabra
� Propriedades da concatenação
• uλ = λu = u
• u(vw) = (uv)w
• |uv| = |u| + |v|
Autômatos Finitos Determinísticos – Cadeias e Linguagens
slide 18
A concatenação da mesma cadeia várias vezes é definida por:
w0 = λ, e
wn+1 = wn w, para n ≥ 0
Se w = w1w2…wn é uma cadeia no alfabeto Σ,
então a reversa (inversa) de w, denotada por wR, é definida por wR = wn
…w2w1
� Observações
• λR = λ
• (vw)R = wRvR
Autômatos Finitos Determinísticos – Concatenação
slide 19
Seja Σ um alfabeto. Então:
Σ0 = { λ }
Σ1 = { w : |w| = 1 }
Σ2 = { w : |w| = 2 }
Σn = { w : |w| = n }
Σ* = Σ0 ∪ Σ1 ∪ … ∪ Σn ∪ Σn+1 ∪ …
ou seja,
Σ* = { w : w é uma cadeia em Σ}
Autômatos Finitos Determinísticos – Linguagens
slide 20
Uma Linguagem L no alfabeto Σ é qualquer
subconjunto de Σ*
Ex.: Σ = { a, b }
L1 = { ab, ba }
L2 = { λ }
L3 = { anbn : n ≥ 0 }
Autômatos Finitos Determinísticos – Linguagens
slide 21
Exemplo:
Seja ∑ = {a, b, c, ..., z}. Sejam A e B as linguagens sobre ∑ dadas por: A = {bom, mau} e B = {garoto, garota}, então:
A ∪ B = {bom, mau, garoto, garota}
A • B = {bomgaroto, bomgarota, maugaroto,
maugarota}
A* = {λ, bom, mau, bombom, bommau,
maubom, maumau, bombombom, ...}
Autômatos Finitos Determinísticos – Linguagens
slide 22
Autômatos Finitos Determinísticos – Representação Gráfica
• Representação Gráfica
slide 23
Autômatos Finitos Determinísticos
Um autômato finito M1: (diagrama de estados)
M1 tem 3 estados, q1, q2, q3 ;
M1 inicia no estado q1 ;
M1 tem um estado final, q2 ;
Os arcos que vão de um estado p/ outro chamam-se transições.
slide 24
- O autômato finito M1 recebe os símbolos de entrada um por um;
- Depois de ler cada símbolo, M1 move-se de um estado para outro, de acordo com a transição que possui aquele símbolo como seu rótulo;
- Quando M1 lê o ultimo símbolo ele produz uma saída:
reconhece se M1 está no estado final não-reconhece se M1 não estiver.
Autômatos Finitos Determinísticos
slide 25
Exemplo: entrada 1101
1. Inicia no estado q1.
2. Lê 1, segue transição de q1 p/ q2.
3. Lê 1, segue transição de q2 p/ q2.
4. Lê 0, segue transição de q2 p/ q3.
5. Lê 1, segue transição de q3 p/ q2.
6. Pára c/ saída reconhece.
Autômatos Finitos Determinísticos
slide 26
Percebemos que :
- M1 reconhece qualquer cadeia que termine com 1 (vai p/ o estado final q2 toda vez que lê 1);
- M1 não reconhece cadeias como 0, 10, 101000.
Vamos aprender!
Testar: 1, 01, 11, 0101 (em M1)
Autômatos Finitos Determinísticos
slide 27
Exemplo: Autômato que reconhece a linguagem de números binários com quantidade ímpar de 1s.
M = (∑, Q, δ, qo, F)
Q = { qo, q1 }, ∑ = { 0, 1 }, F = { q1 }
δ 0 1
qpar
qímpar
qpar
qímpar
qímpar
qpar
Autômatos Finitos Determinísticos
Função de Transição
δ (qpar,0) = qpar
...
slide 28
• Um Autômato Finito nunca entra em “loop” infinito
• Novos símbolos da entrada são lidos a cada aplicação da
função programa, o processo de reconhecimento de
qualquer cadeia pára de duas maneiras:
– Aceitando ou;
– rejeitando uma entrada.
Autômatos Finitos Determinísticos
slide 29
• Definir um AF engloba definir
– Um conjunto finito de estados;
– Um alfabeto de entrada que indica os símbolos de entrada permitidos;
– Um conjunto de regras de movimento que indicam como ir de um estado p/ outro, dependendo do símbolo de entrada;
– Um estado escolhido como estado inicial;
– Um conjunto de estados escolhidos como estados finais (de reconhecimento);
Autômatos Finitos Determinísticos
slide 30
• Exercício: suponha que o alfabeto é {0,1}.Projete um AF para reconhecer a linguagem regular composta por todas as cadeias que tem 001 como subcadeia
• Por exemplo, 0010, 1001, 001 e 11111110011111 pertencem a esta linguagem, mas 11 e 0000 não
Autômatos Finitos Determinísticos – Praticando...
slide 31
Exercício 2: Construir um AFD que reconhece a linguagem a*.
M = (∑, Q, δδδδ, qo, F)
Q = { qo }, ∑ = { a }, F = { q0 }
δδδδ a
qo qo
qo
a
Autômatos Finitos Determinísticos – Praticando...
Função de Transição
slide 32
Exercício 3: Construir um AFD que reconhece a linguagem aa* .
M = (∑, Q, δδδδ, qo, F)
Q = { qo, q1 }, ∑ = { a }, F = { q1 }
δδδδ a
qo
q1
q1
q1
qo q1
a a
Autômatos Finitos Determinísticos – Praticando...
Função de Transição
slide 33
Exercício 4: Construir um AFD que reconhece a
linguagem (abb*a)*
M = (∑, Q, δδδδ, qo, F)
Q = { qo, q1, q2 }, ∑ = { a, b }, F = { q0 }
qo q1
a
b
q2
b
a
δδδδ a b
qo
q1
q1
qrej
qrej
q2
q2 q0 q2
Autômatos Finitos Determinísticos – Praticando...
Função de Transição
slide 34
Exercício 5:
Conjunto de todos as palavras com três zeros consecutivos.
Autômatos Finitos Determinísticos – Praticando...
slide 35
Exercício 6:
Conjunto de todas as palavras que não contém 101
como subpalavra.
Autômatos Finitos Determinísticos – Praticando...
slide 36
Introdução à Teoria da Computação
UAB/UFRPE
Eduardo Araújo Oliveira
http://sites.google.com/site/eaoufpe
slide 1
Introdução à Teoria da Computação
UAB/UFRPE
Eduardo Araújo Oliveira
http://sites.google.com/site/eaoufpe
slide 2
Conceitos Iniciais
• Computadores atuais mais rápidos e poderosos
• Modelos matemáticos
• Autômatos Finitos
slide 3
Autômatos Finitos
• Reconhecedor de palavras ou cadeia de caracteres
• Bons modelos para computadores com capacidade de memória reduzida
• Fazem parte de vários dispositivos eletro-mecânicos
do dia-a-dia
slide 4
Autômatos Finitos
• Exemplo 1
Visão aérea de uma porta automática
slide 5
Autômatos Finitos
• Exemplo 1
O controlador passa de um estado para outro dependendo do estímulo (entrada) que recebe:
O controlador da porta pode estar em 2 estados:
- aberto (significando porta aberta)
- fechado (significando porta fechada)
slide 6
Autômatos Finitos
• Exemplo 1
Entradas: Existem 4 condições de entrada possíveis
Frente: significando que uma pessoa está em pé sobre o tapete da
frente;
Retaguarda: significando que uma pessoa está em pé sobre o tapete
de
dentro;
Ambos: significando que existem pessoas sobre os 2 tapetes;
Nenhum: significando que ninguém está sobre os tapetes.
slide 7
Autômatos Finitos
• Exemplo 1
Entradas: Existem 4 condições de entrada possíveis
slide 8
Autômatos Finitos
• Exemplo 1
Tabela de Transição
slide 9
Autômatos Finitos
• Exemplo 2
Interruptor
Estados: Ligado ou Desligado
slide 10
Autômatos Finitos
• Exemplo 3
Palavra AMOR
Qualquer outra palavra deve ser descartada
slide 11
Autômatos Finitos
• Exemplo 3
Tentativa de leitura da Palavra AMBIENTE
slide 12
Autômatos Finitos
• Controladores para:
– Lavadoras de louça/roupa
– Termômetros eletrônicos
– Relógios digitais
– Calculadoras
– Máquinas de venda automática
slide 13
Autômatos Finitos
• O AF é uma máquina, reconhecedora de palavras ou cadeia de caracteres, que sempre pára retornando uma resposta sim (cadeia reconhecida) ou não (cadeia não conhecida)
• Podem ser classificados em:
– Autômatos Finitos Determinísticos (AFD)
– Autômatos Finitos Não-Determinísticos (AFND)
slide 14
Autômatos Finitos Determinísticos – Definição Formal
Definição formal de um Autômato Finito Determinístico:
Um Autômato Finito Determinístico (AFD) M é uma 5-upla:
M = (Q, Σ, δ, q0, F), onde
Q: conjunto finito de estados do autômato;
Σ: alfabeto de símbolos de entrada;
δ: função programa ou função de transição (parcial) δ: Q × Σ → Q. Significa dizer que permanecendo em um estado e lendo um símbolo do alfabeto faz o autômato passar para outro estado ou mesmo ficar no mesmo
q0: estado inicial (q0∈Q)
F: conjunto de estados finais ou estados de aceitação (F⊆Q)
slide 15
Um alfabeto Σ é um conjunto finito (não-vazio) de símbolos
Ex.: Alfabetos
Σ1 = {0,1}
Σ2 = {a, b, c, …, z}
Uma cadeia (string) em um alfabeto Σ é uma
seqüência finita de símbolos deste alfabeto
Ex.: Cadeias
01001
abracadabra
Autômatos Finitos Determinísticos – Cadeias e Linguagens
slide 16
Se w = w1w2…wn é uma cadeia sobre Σ, o
comprimento de w, denotado por |w|, é n
A cadeia de comprimento 0, é denominada cadeia nula e é representada por λ
Ex.: |abracadabra| = 11
Autômatos Finitos Determinísticos – Cadeias e Linguagens
slide 17
Se u = u1u2…un e v = v1v2
…vm são cadeias no
alfabeto Σ, então a concatenação de u com v, denotada por uv, é definida por:
uv = u1u2…unv1v2
…vm
Ex.: u = abra e v = cadabra ⇒ uv = abracadabra
� Propriedades da concatenação
• uλ = λu = u
• u(vw) = (uv)w
• |uv| = |u| + |v|
Autômatos Finitos Determinísticos – Cadeias e Linguagens
slide 18
A concatenação da mesma cadeia várias vezes é definida por:
w0 = λ, e
wn+1 = wn w, para n ≥ 0
Se w = w1w2…wn é uma cadeia no alfabeto Σ,
então a reversa (inversa) de w, denotada por wR, é definida por wR = wn
…w2w1
� Observações
• λR = λ
• (vw)R = wRvR
Autômatos Finitos Determinísticos – Concatenação
slide 19
Seja Σ um alfabeto. Então:
Σ0 = { λ }
Σ1 = { w : |w| = 1 }
Σ2 = { w : |w| = 2 }
Σn = { w : |w| = n }
Σ* = Σ0 ∪ Σ1 ∪ … ∪ Σn ∪ Σn+1 ∪ …
ou seja,
Σ* = { w : w é uma cadeia em Σ}
Autômatos Finitos Determinísticos – Linguagens
slide 20
Uma Linguagem L no alfabeto Σ é qualquer
subconjunto de Σ*
Ex.: Σ = { a, b }
L1 = { ab, ba }
L2 = { λ }
L3 = { anbn : n ≥ 0 }
Autômatos Finitos Determinísticos – Linguagens
slide 21
Exemplo:
Seja ∑ = {a, b, c, ..., z}. Sejam A e B as linguagens sobre ∑ dadas por: A = {bom, mau} e B = {garoto, garota}, então:
A ∪ B = {bom, mau, garoto, garota}
A • B = {bomgaroto, bomgarota, maugaroto,
maugarota}
A* = {λ, bom, mau, bombom, bommau,
maubom, maumau, bombombom, ...}
Autômatos Finitos Determinísticos – Linguagens
slide 22
Autômatos Finitos Determinísticos – Representação Gráfica
• Representação Gráfica
slide 23
Autômatos Finitos Determinísticos
Um autômato finito M1: (diagrama de estados)
M1 tem 3 estados, q1, q2, q3 ;
M1 inicia no estado q1 ;
M1 tem um estado final, q2 ;
Os arcos que vão de um estado p/ outro chamam-se transições.
slide 24
- O autômato finito M1 recebe os símbolos de entrada um por um;
- Depois de ler cada símbolo, M1 move-se de um estado para outro, de acordo com a transição que possui aquele símbolo como seu rótulo;
- Quando M1 lê o ultimo símbolo ele produz uma saída:
reconhece se M1 está no estado final não-reconhece se M1 não estiver.
Autômatos Finitos Determinísticos
slide 25
Exemplo: entrada 1101
1. Inicia no estado q1.
2. Lê 1, segue transição de q1 p/ q2.
3. Lê 1, segue transição de q2 p/ q2.
4. Lê 0, segue transição de q2 p/ q3.
5. Lê 1, segue transição de q3 p/ q2.
6. Pára c/ saída reconhece.
Autômatos Finitos Determinísticos
slide 26
Percebemos que :
- M1 reconhece qualquer cadeia que termine com 1 (vai p/ o estado final q2 toda vez que lê 1);
- M1 não reconhece cadeias como 0, 10, 101000.
Vamos aprender!
Testar: 1, 01, 11, 0101 (em M1)
Autômatos Finitos Determinísticos
slide 27
Exemplo: Autômato que reconhece a linguagem de números binários com quantidade ímpar de 1s.
M = (∑, Q, δ, qo, F)
Q = { qo, q1 }, ∑ = { 0, 1 }, F = { q1 }
δ 0 1
qpar
qímpar
qpar
qímpar
qímpar
qpar
Autômatos Finitos Determinísticos
Função de Transição
δ (qpar,0) = qpar
...
slide 28
• Um Autômato Finito nunca entra em “loop” infinito
• Novos símbolos da entrada são lidos a cada aplicação da
função programa, o processo de reconhecimento de
qualquer cadeia pára de duas maneiras:
– Aceitando ou;
– rejeitando uma entrada.
Autômatos Finitos Determinísticos
slide 29
• Definir um AF engloba definir
– Um conjunto finito de estados;
– Um alfabeto de entrada que indica os símbolos de entrada permitidos;
– Um conjunto de regras de movimento que indicam como ir de um estado p/ outro, dependendo do símbolo de entrada;
– Um estado escolhido como estado inicial;
– Um conjunto de estados escolhidos como estados finais (de reconhecimento);
Autômatos Finitos Determinísticos
slide 30
• Exercício: suponha que o alfabeto é {0,1}.Projete um AF para reconhecer a linguagem regular composta por todas as cadeias que tem 001 como subcadeia
• Por exemplo, 0010, 1001, 001 e 11111110011111 pertencem a esta linguagem, mas 11 e 0000 não
Autômatos Finitos Determinísticos – Praticando...
slide 31
Exercício 2: Construir um AFD que reconhece a linguagem a*.
M = (∑, Q, δδδδ, qo, F)
Q = { qo }, ∑ = { a }, F = { q0 }
δδδδ a
qo qo
qo
a
Autômatos Finitos Determinísticos – Praticando...
Função de Transição
slide 32
Exercício 3: Construir um AFD que reconhece a linguagem aa* .
M = (∑, Q, δδδδ, qo, F)
Q = { qo, q1 }, ∑ = { a }, F = { q1 }
δδδδ a
qo
q1
q1
q1
qo q1
a a
Autômatos Finitos Determinísticos – Praticando...
Função de Transição
slide 33
Exercício 4: Construir um AFD que reconhece a
linguagem (abb*a)*
M = (∑, Q, δδδδ, qo, F)
Q = { qo, q1, q2 }, ∑ = { a, b }, F = { q0 }
qo q1
a
b
q2
b
a
δδδδ a b
qo
q1
q1
qrej
qrej
q2
q2 q0 q2
Autômatos Finitos Determinísticos – Praticando...
Função de Transição
slide 34
Exercício 5:
Conjunto de todos as palavras com três zeros consecutivos.
Autômatos Finitos Determinísticos – Praticando...
slide 35
Exercício 6:
Conjunto de todas as palavras que não contém 101
como subpalavra.
Autômatos Finitos Determinísticos – Praticando...
slide 36
Introdução à Teoria da Computação
UAB/UFRPE
Eduardo Araújo Oliveira
http://sites.google.com/site/eaoufpe