TC - Automatos Finitos - slides

Prévia do material em texto

FTC
Teoria da Computação
Autômatos Finitos
Lucilia Figueiredo
Universidade Federal de Ouro Preto
DECOM-UFOP 2008
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exemplo 1
q0
q1
1
0
0
1
M aceita o string 001?
M aceita o string 10100?
Qual é a linguagem reconhecida por M?
L(M) = {w |w termina com 0}
Autômato Finito Determinista DFA
Memória finita
Computação determinista
Computação sempre pára
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exemplo 1
q0
q1
1
0
0
1
M aceita o string 001?
M aceita o string 10100?
Qual é a linguagem reconhecida por M?
L(M) = {w |w termina com 0}
Autômato Finito Determinista DFA
Memória finita
Computação determinista
Computação sempre pára
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exemplo 1
q0
q1
1
0
0
1
M aceita o string 001?
M aceita o string 10100?
Qual é a linguagem reconhecida por M?
L(M) = {w |w termina com 0}
Autômato Finito Determinista DFA
Memória finita
Computação determinista
Computação sempre pára
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exemplo 1
q0
q1
1
0
0
1
M aceita o string 001?
M aceita o string 10100?
Qual é a linguagem reconhecida por M?
L(M) = {w |w termina com 0}
Autômato Finito Determinista DFA
Memória finita
Computação determinista
Computação sempre pára
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exemplo 1
q0
q1
1
0
0
1
M aceita o string 001?
M aceita o string 10100?
Qual é a linguagem reconhecida por M?
L(M) = {w |w termina com 0}
Autômato Finito Determinista DFA
Memória finita
Computação determinista
Computação sempre pára
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exemplo 1
q0
q1
1
0
0
1
M aceita o string 001?
M aceita o string 10100?
Qual é a linguagem reconhecida por M?
L(M) = {w |w termina com 0}
Autômato Finito Determinista DFA
Memória finita
Computação determinista
Computação sempre pára
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 1
Desenhe um DFA que reconheça a linguagem
L = {w |w começa com 00}
q0
erro
li 0 li 00
1
0
0,1
1
0
0,1
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 1
Desenhe um DFA que reconheça a linguagem
L = {w |w começa com 00}
q0
erro
li 0 li 00
1
0
0,1
1
0
0,1
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 2
Desenhe um DFA que reconheça a linguagem
L = {w |w tem número par de 0s}
#0s par #0s ímpar
1
0
1
0
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 2
Desenhe um DFA que reconheça a linguagem
L = {w |w tem número par de 0s}
#0s par #0s ímpar
1
0
1
0
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Autômato Finito Determinista
q0
q1
1
0
0
1
M = (Σ,Q,q0, δ,F )
Σ - alfabeto de entrada {0,1}
Q - conjunto finito de estados {q0,q1}
q0 - estado inicial
F ⊆ Q - conjunto de estados finais {q1}
δ : Q × Σ→ Q - função transição de estado
0 1
q0 q1 q0
q1 q1 q0
L(M) = {w |M aceita w}
Uma linguagem reconhecida por um DFA é
dita REGULAR
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Autômato Finito Determinista
q0
q1
1
0
0
1
M = (Σ,Q,q0, δ,F )
Σ - alfabeto de entrada {0,1}
Q - conjunto finito de estados {q0,q1}
q0 - estado inicial
F ⊆ Q - conjunto de estados finais {q1}
δ : Q × Σ→ Q - função transição de estado
0 1
q0 q1 q0
q1 q1 q0
L(M) = {w |M aceita w}
Uma linguagem reconhecida por um DFA é
dita REGULAR
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Autômato Finito Determinista
q0
q1
1
0
0
1
M = (Σ,Q,q0, δ,F )
Σ - alfabeto de entrada {0,1}
Q - conjunto finito de estados {q0,q1}
q0 - estado inicial
F ⊆ Q - conjunto de estados finais {q1}
δ : Q × Σ→ Q - função transição de estado
0 1
q0 q1 q0
q1 q1 q0
L(M) = {w |M aceita w}
Uma linguagem reconhecida por um DFA é
dita REGULAR
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Autômato Finito Determinista
q0
q1
1
0
0
1
M = (Σ,Q,q0, δ,F )
Σ - alfabeto de entrada {0,1}
Q - conjunto finito de estados {q0,q1}
q0 - estado inicial
F ⊆ Q - conjunto de estados finais {q1}
δ : Q × Σ→ Q - função transição de estado
0 1
q0 q1 q0
q1 q1 q0
L(M) = {w |M aceita w}
Uma linguagem reconhecida por um DFA é
dita REGULAR
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Autômato Finito Determinista
q0
q1
1
0
0
1
M = (Σ,Q,q0, δ,F )
Σ - alfabeto de entrada {0,1}
Q - conjunto finito de estados {q0,q1}
q0 - estado inicial
F ⊆ Q - conjunto de estados finais {q1}
δ : Q × Σ→ Q - função transição de estado
0 1
q0 q1 q0
q1 q1 q0
L(M) = {w |M aceita w}
Uma linguagem reconhecida por um DFA é
dita REGULAR
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Linguagem Regular
Mais formalmente, um linguagem é dita REGULAR se existe um
DFA M = (Σ,Q,q0, δ,F ) tal que
L = {w | δˆ(q0,w) ∈ F}
onde δˆ : Q × Σ∗ → Q é a função de transição estendida, definida
recursivamente como
δˆ(q, �) = q
δˆ(q,aw) = δˆ(δ(q,a),w) para todo a ∈ Σ e w ∈ Σ∗
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Implementando um DFA
module DFA where
import Data.Map
import qualified Data.Set as Set
data DFA a = DFA (Set.Set Char) -- alfabeto
(Set.Set a) -- estados
(Move a) -- função de transição
a -- estado inicial
(Set.Set a) -- estados finais
deriving (Eq, Show)
type Move a = Map a (Map Char a)
simDFA :: Ord a => DFA a -> String -> Bool
simDFA (DFA sigma states delta q0 fstates) input =
isFinalState (foldl step q0 input)
where isFinalState qe = Set.member qe fstates
step q c = (delta!q)!c
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 3
Desenhe um DFA que reconheça a linguagem
L = {w |w tem número par de 0s e número ímpar de 1s}
p, p
i, p
p, i
i, i
0
1
1
0
0
1
1 0
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 3
Desenhe um DFA que reconheça a linguagem
L = {w |w tem número par de 0s e número ímpar de 1s}
p, p
i, p
p, i
i, i
0
1
1
0
0
1
1 0
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 4
Desenhe um DFA que reconheça a linguagem
L = {w | w tem número par de 0s e número ímpar de 1s ou
w tem número ímpar de 0s e número ímpar de 1s}
p, p
i, p
p, i
i, i
0
1
1
0
0
1
1 0
Este autômato é mínimo?
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > AutômatoFinito Determinista
Exercício 4
Desenhe um DFA que reconheça a linguagem
L = {w | w tem número par de 0s e número ímpar de 1s ou
w tem número ímpar de 0s e número ímpar de 1s}
p, p
i, p
p, i
i, i
0
1
1
0
0
1
1 0
Este autômato é mínimo?
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 4
Desenhe um DFA que reconheça a linguagem
L = {w | w tem número par de 0s e número ímpar de 1s ou
w tem número ímpar de 0s e número ímpar de 1s}
p, p
i, p
p, i
i, i
0
1
1
0
0
1
1 0
Este autômato é mínimo?
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 4
Desenhe um DFA que reconheça a linguagem
L = {w | w tem número par de 0s e número ímpar de 1s ou
w tem número ímpar de 0s e número ímpar de 1s}
Autômato mínimo
q0 q1
0
1
0
1
Para todo M existe um DFA equivalente M ′ mínimo.
O DFA mínimo M ′ pode ser obtido por meio de um algoritmo.
Essa propriedade não vale para programas.
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 4
Desenhe um DFA que reconheça a linguagem
L = {w | w tem número par de 0s e número ímpar de 1s ou
w tem número ímpar de 0s e número ímpar de 1s}
Autômato mínimo
q0 q1
0
1
0
1
Para todo M existe um DFA equivalente M ′ mínimo.
O DFA mínimo M ′ pode ser obtido por meio de um algoritmo.
Essa propriedade não vale para programas.
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 4
Desenhe um DFA que reconheça a linguagem
L = {w | w tem número par de 0s e número ímpar de 1s ou
w tem número ímpar de 0s e número ímpar de 1s}
Autômato mínimo
q0 q1
0
1
0
1
Para todo M existe um DFA equivalente M ′ mínimo.
O DFA mínimo M ′ pode ser obtido por meio de um algoritmo.
Essa propriedade não vale para programas.
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 4
Desenhe um DFA que reconheça a linguagem
L = {w | w tem número par de 0s e número ímpar de 1s ou
w tem número ímpar de 0s e número ímpar de 1s}
Autômato mínimo
q0 q1
0
1
0
1
Para todo M existe um DFA equivalente M ′ mínimo.
O DFA mínimo M ′ pode ser obtido por meio de um algoritmo.
Essa propriedade não vale para programas.
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA
M é um DFA mínimo para a linguagem L(M) se nenhum outro
DFA para L(M) contém menor número de estados do que M.
É claro que um DFA mínimo para uma linguagem L não contém
estados inatingíveis a partir do estado inicial. Portanto, o
primeiro passo para minimização é eliminar estados
inatingíveis.
O segundo passo é determinar grupos de estados equivalentes
e substituir cada um do grupo por um dado estado desse
grupo. Dois estados e e e′ de um DFA M = (Q,Σ, δ,q0,F ) são
equivalentes sse:
∀y ∈ Σ∗, δˆ(e, y) ∈ F ⇔ δˆ(e′, y) ∈ F
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA
M é um DFA mínimo para a linguagem L(M) se nenhum outro
DFA para L(M) contém menor número de estados do que M.
É claro que um DFA mínimo para uma linguagem L não contém
estados inatingíveis a partir do estado inicial. Portanto, o
primeiro passo para minimização é eliminar estados
inatingíveis.
O segundo passo é determinar grupos de estados equivalentes
e substituir cada um do grupo por um dado estado desse
grupo. Dois estados e e e′ de um DFA M = (Q,Σ, δ,q0,F ) são
equivalentes sse:
∀y ∈ Σ∗, δˆ(e, y) ∈ F ⇔ δˆ(e′, y) ∈ F
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA
M é um DFA mínimo para a linguagem L(M) se nenhum outro
DFA para L(M) contém menor número de estados do que M.
É claro que um DFA mínimo para uma linguagem L não contém
estados inatingíveis a partir do estado inicial. Portanto, o
primeiro passo para minimização é eliminar estados
inatingíveis.
O segundo passo é determinar grupos de estados equivalentes
e substituir cada um do grupo por um dado estado desse
grupo. Dois estados e e e′ de um DFA M = (Q,Σ, δ,q0,F ) são
equivalentes sse:
∀y ∈ Σ∗, δˆ(e, y) ∈ F ⇔ δˆ(e′, y) ∈ F
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Algoritmo de Minimização de DFA
Determina as classes de equivalência de estados do DFA.
Antes, elimine todos os estado não-atingíveis a partir de q0.
distinct = {〈p,q〉 |p ∈ F e q 6∈ F}
oldDistinct = ∅
while (distinct 6= oldDistinct)
oldDistinct = distinct
for all symbol a and all 〈p,q〉 ∈ distinct do
if 〈d(p,a),d(q,a)〉 ∈ distinct
then distinct = distinct ∪ {〈p,q〉}
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA - Exemplo
A
C
E
G
F
D
B
0
1
01
0 1 0 1
0
1
0,1
0
1
B
C 2 2
D 2 2
E 2 2 2 2
F 1 1 1 1 1
G 1 1 1 1 1
A B C D E F G
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA - Exemplo
A
C
E
G
F
D
B
0
1
01
0 1 0 1
0
1
0,1
0
1
Passo 0: Eliminar estados inatingíveis
B
C 2 2
D 2 2
E 2 2 2 2
F 1 1 1 1 1
G 1 1 1 1 1
A B C D E F G
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA - Exemplo
A
C
E
G
F
D
B
0
1
01
0 1 0 1
0
1
0,1
0
1
Passo 1: Distinguir estados q ∈ F e q′ 6∈ F
B
C 2 2
D 2 2
E 2 2 2 2
F 1 1 1 1 1
G 1 1 1 1 1
A B C D E F G
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA - Exemplo
A
C
E
G
F
D
B
0
1
01
0 1 0 1
0
1
0,1
0
1
B
C 2 2
D 2 2
E 2 2 2 2
F 1 1 1 1 1
G 1 1 1 1 1
A B C D E F G
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA - Exemplo
A
C
E
G
F
D
B
0
1
01
0 1 0 1
0
1
0,1
0
1
Loop
B
C 2 2
D 2 2
E 2 2 2 2
F 1 1 1 1 1
G 1 1 1 1 1
A B C D E F G
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA - Exemplo
A
C
E
G
F
D
B
0
1
01
0 1 0 1
0
1
0,1
0
1
Loop
B
C 2 2
D 2 2
E 2 2 2 2
F 1 1 1 1 1
G 1 1 1 1 1
A B C D E F G
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA - Exemplo
A
C
E
G
F
D
B
0
1
01
0 1 0 1
0
1
0,1
0
1
Loop
B
C 2 2
D 2 2
E 2 2 2 2
F 1 1 1 1 1
G 1 1 1 1 1
A B C D E F G
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA - Exemplo
A
C
E
G
F
D
B
0
1
01
0 1 0 1
0
1
0,1
0
1
Loop
B
C 2 2
D 2 2
E 2 2 2 2
F 1 1 1 1 1
G 1 1 1 1 1
A B C D E F G
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA - Exemplo
A
C
E
G
F
D
B
0
1
01
0 1 0 1
0
1
0,1
0
1
Loop
B
C 2 2
D 2 2
E 2 2 2 2
F 11 1 1 1
G 1 1 1 1 1
A B C D E F G
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA - Exemplo
A
C
E
G
F
D
B
0
1
01
0 1 0 1
0
1
0,1
0
1
Loop
B
C 2 2
D 2 2
E 2 2 2 2
F 1 1 1 1 1
G 1 1 1 1 1
A B C D E F G
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA - Exemplo
A
C
E
G
F
D
B
0
1
01
0 1 0 1
0
1
0,1
0
1
Loop
B
C 2 2
D 2 2
E 2 2 2 2
F 1 1 1 1 1
G 1 1 1 1 1
A B C D E F G
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA - Exemplo
A
C
E
G
F
D
B
0
1
01
0 1 0 1
0
1
0,1
0
1
Loop
B
C 2 2
D 2 2
E 2 2 2 2
F 1 1 1 1 1
G 1 1 1 1 1
A B C D E F G
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA - Complexidade
Qual é o número de iterações do loop?
O(n)
Qual é o tempo gasto em cada iteração?
O(n2)
Portanto, o tempo de execução é
O(n3)
Existe algoritmo de minimização mais eficiente: O(n logn)
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA - Complexidade
Qual é o número de iterações do loop? O(n)
Qual é o tempo gasto em cada iteração?
O(n2)
Portanto, o tempo de execução é
O(n3)
Existe algoritmo de minimização mais eficiente: O(n logn)
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA - Complexidade
Qual é o número de iterações do loop? O(n)
Qual é o tempo gasto em cada iteração?O(n2)
Portanto, o tempo de execução é
O(n3)
Existe algoritmo de minimização mais eficiente: O(n logn)
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA - Complexidade
Qual é o número de iterações do loop? O(n)
Qual é o tempo gasto em cada iteração?O(n2)
Portanto, o tempo de execução é O(n3)
Existe algoritmo de minimização mais eficiente: O(n logn)
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Minimização de DFA - Complexidade
Qual é o número de iterações do loop? O(n)
Qual é o tempo gasto em cada iteração?O(n2)
Portanto, o tempo de execução é O(n3)
Existe algoritmo de minimização mais eficiente: O(n logn)
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 5
Desenhe um DFA que reconheça a linguagem
L = {w |w representa um número divisível por 4}
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 5
Desenhe um DFA que reconheça a linguagem
L = {w |w representa um número divisível por 4}
Um número binário é divisível por 4 sse termina com 00 ou é 0!
Portanto L ≡ {w |w termina com 00 ou w=0}
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 5
Desenhe um DFA que reconheça a linguagem
L = {w |w representa um número divisível por 4}
q0 last=0 last2=00
1
0 0
1
0
1
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 5
Desenhe um DFA que reconheça a linguagem
L = {w |w representa um número divisível por 4}
q0 last=0 last2=00
1
0 0
1
0
1
Correto? Aceita 0?
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 5
Desenhe um DFA que reconheça a linguagem
L = {w |w representa um número divisível por 4}
q0 last=0 last2=00
1
0 0
1
0
1
Agora OK!
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 6
Desenhe um DFA que reconheça a linguagem
L = {w |w representa um número não divisível por 4}
Dica: é o complemento da linguagem anterior.
q0 last=0 last2=00
1
0 0
1
0
1
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 6
Desenhe um DFA que reconheça a linguagem
L = {w |w representa um número não divisível por 4}
Dica: é o complemento da linguagem anterior.
q0 last=0 last2=00
1
0 0
1
0
1
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 6 - continuação
Desenhe um DFA que reconheça a linguagem
L = {w |w representa um número não divisível por 4}
Basta então inverter estados finais e não finais
q0 last=0 last2=00
1
0 0
1
0
1
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Aplicação
Pesquisa por um string s em um texto t .
Solução ingênua: O(n ×m), onde n = |t | e m = |s|.
Algoritmo de Knuth-Morrison-Pratt (KMP): O(n + m)
L = {w |w contém o substring 110110 }
� 1 11 110 1101 11011 110110
1
0
1
0
0
1
1
0
1
0
0
1
0,1
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Aplicação
Pesquisa por um string s em um texto t .
Solução ingênua: O(n ×m), onde n = |t | e m = |s|.
Algoritmo de Knuth-Morrison-Pratt (KMP): O(n + m)
L = {w |w contém o substring 110110 }
� 1 11 110 1101 11011 110110
1
0
1
0
0
1
1
0
1
0
0
1
0,1
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Aplicação
Pesquisa por um string s em um texto t .
Solução ingênua: O(n ×m), onde n = |t | e m = |s|.
Algoritmo de Knuth-Morrison-Pratt (KMP): O(n + m)
L = {w |w contém o substring 110110 }
� 1 11 110 1101 11011 110110
1
0
1
0
0
1
1
0
1
0
0
1
0,1
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Aplicação
Pesquisa por um string s em um texto t .
Solução ingênua: O(n ×m), onde n = |t | e m = |s|.
Algoritmo de Knuth-Morrison-Pratt (KMP): O(n + m)
L = {w |w contém o substring 110110 }
� 1 11 110 1101 11011 110110
1
0
1
0
0
1
1
0
1
0
0
1
0,1
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Aplicação
Pesquisa por um string s em um texto t .
Solução ingênua: O(n ×m), onde n = |t | e m = |s|.
Algoritmo de Knuth-Morrison-Pratt (KMP): O(n + m)
L = {w |w contém o substring 110110 }
� 1 11 110 1101 11011 110110
1
0
1
0
0
1
1
0
1
0
0
1
0,1
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 7
Desenhe um DFA que reconhece a linguagem
L = {w |w não contém o substring 110110 }
� 1 11 110 1101 11011 110110
1
0
1
0
0
1
1
0
1
0
0
1
0,1
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 7
Desenhe um DFA que reconhece a linguagem
L = {w |w não contém o substring 110110 }
� 1 11 110 1101 11011 110110
1
0
1
0
0
1
1
0
1
0
0
1
0,1
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 8
L = {w |w termina com 0 }
q0q1
1
0
0
1
rev(L) = {w |w começa 0 }?
q0
q1
1
0
0
1
Não é um DFA!
O que significa uma escolha
não determinística sobre um
dado símbolo?
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 8
L = {w |w termina com 0 }
q0
q1
1
0
0
1
rev(L) = {w |w começa 0 }?
q0
q1
1
0
0
1
Não é um DFA!
O que significa uma escolha
não determinística sobre um
dado símbolo?
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 8
L = {w |w termina com 0 }
q0
q1
1
0
0
1
rev(L) = {w |w começa 0 }?
q0
q1
1
0
0
1
Não é um DFA!
O que significa uma escolha
não determinística sobre um
dado símbolo?
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 8
L = {w |w termina com 0 }
q0
q1
1
0
0
1
rev(L) = {w |w começa 0 }?
q0
q1
1
0
0
1
Não é um DFA!
O que significa uma escolha
não determinística sobre um
dado símbolo?
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 9
Desenhe um DFA que reconhece
L = {w | cada 1 é seguido de pelo menos dois 0s }
q0 q1 q2
q3
0
1 0
1
0
1
0,1
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 9
Desenhe um DFA que reconhece
L = {w | cada 1 é seguido de pelo menos dois 0s }
q0 q1 q2
q3
0
1 0
1
0
1
0,1
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 10
Desenhe um DFA que reconhece
L = {w |w não é divisível por 3 }
rem = 0 rem = 1 rem = 2
0
1 0
1
1
0
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Exercício 10
Desenhe um DFA que reconhece
L = {w |w não é divisível por 3 }
rem = 0 rem = 1 rem = 2
0
1 0
1
1
0
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Precisamos mais que DFAs?
Vimos vários exemplos de linguagens que podem ser
reconhecidas por DFAs.
O que não pode ser computado por um DFA?
Exemplo: L = {0n 1n |n ∈ N}
Como podemos provar que essa linguagem não pode ser
reconhecida por um DFA?
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Precisamos mais que DFAs?
Vimos vários exemplos de linguagens que podem ser
reconhecidas por DFAs.
O que não pode ser computado por um DFA?
Exemplo: L = {0n 1n |n ∈ N}
Como podemos provar que essa linguagem não pode ser
reconhecida por um DFA?
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC > Autômato Finito Determinista
Precisamos mais que DFAs?
Vimos vários exemplos de linguagens que podem ser
reconhecidas por DFAs.
O que não pode ser computado por um DFA?
Exemplo: L = {0n 1n |n ∈ N}
Como podemos provar que essa linguagem não pode ser
reconhecida por um DFA?
Universidade Federal de Ouro Preto www.dcc.ufmg.br/~lucilia/cursos/ftc
	Autômato Finito Determinista