Slides 07 - Teoria da Computação VII

Prévia do material em texto

• Relações e operações envolvendo linguagens regulares
• AFN – Autômatos Finitos Não-determinísticos
Aula 7
• Relações de pertinência Resp.
i. a ∈ L ( a(avb)* ) ?
ii. aa ∈ L ( a(avb)* ) ?
iii. λ ∈ L ( a(avb)* ) ?
iv. ab ∈ L ( a(avb)* ) ?
v. ba ∈ L ( a(avb)* ) ?
Relações envolvendo Linguagens Regulares
i. Sim
ii. Sim
iii. Não
iv. Sim
v. Não
• Relações de inclusão
vi. L( a* ) ⊂ L( aa* ) ?
vii. L( aa* ) ⊂ L( a* ) ?
viii. L( a* ) ⊂ L( a(avb) * ) ? 
ix. L( aa* ) ⊂ L( a(avb)* ) ?
x. L( a(avb)* ) ⊂ L( aa* ) ?
Relações envolvendo Linguagens Regulares
Respostas a seguir
• Relações de inclusão: respostas
vi. L( a* ) ⊄ L( aa* ), pois λ ∈ L( a* ) mas λ ∉ L( aa* )
vii. L( aa* ) ⊂ L( a* )
viii. L( a* ) ⊄ L( a(avb) * ), pois λ ∈ L( a* ) mas λ ∉ L( a(avb) * )
ix. L( aa* ) ⊂ L( a(avb)* )
x. L( a(avb)* ) ⊄ L( aa* ), pois ab ∈ L( a(avb)* ) mas ab ∉ L( aa* )
Relembrando:
L( a* ) = { λ, a, aa, aaa, aaaa, … }
L( aa* ) = { a, aa, aaa, aaaa, … }
Relações envolvendo Linguagens Regulares
• A partir do Teorema de Kleene, pode-se provar que
– O conjunto das linguagens regulares é fechado sobre as operações de
• União, Interseção
• Diferença, Complemento
– Em outras palavras
• As operações de união, interseção, diferença e complemento
envolvendo linguagens regulares resultam em conjuntos que
também são linguagens regulares
Operações envolvendo Linguagens Regulares
• Exemplos
i. L ( a* ) ∪ L ( b* ) =
ii. L ( a* ) ∩ L ( b* ) =
iii. L ( a* ) – L ( λ ) =
Operações envolvendo Linguagens Regulares
L ( a* v b* )
L ( λ )
L ( aa* )
• Exercícios
– Caracterize por expressão regular os conjuntos resultantes
das operações a seguir:
iv. L ( a* ) – L ( b* ) =
v. L ( (a v b)* ) – L ( λ ) =
vi. L ( a* v b* ) – L ( λ ) =
vii. L ( a* ) – L ( (aa)* ) =
viii. L ( a(avb)* ) – L ( a* ) =
Operações envolvendo Linguagens Regulares
Respostas a seguir
• Exercícios
– Respostas:
iv. L ( a* ) – L ( b* ) =
v. L ( (a v b)* ) – L ( λ ) =
vi. L ( a* v b* ) – L ( λ ) =
vii. L ( a* ) – L ( (aa)* ) =
viii. L ( a(avb)* ) – L ( a* ) =
Operações envolvendo Linguagens Regulares
L ( aa* )
L ( (a v b)(a v b)* )
L ( aa* v bb* )
L ( a(aa)* )
L ( aa*b(avb)* ) ou
L ( a(avb)*b(avb)* )
• Exemplo
1. M1
AFN – Autômatos Finitos Não-determinísticos
Marca de estado inicial
q0 q1
a,b
a
δ(q0,a) = { q0, q1 }
δ(q1,a) = ∅
δ(q0,b) = { q0 }
δ(q1,b) = ∅
• Definição de um AFN M
– M = ( Q, Σ, δ, qi, F ), onde:
• Q Conjunto finito de estados
• Σ alfabeto de entrada
• δ Função de transição
δ: Q x Σ → ℘℘℘℘(Q) Ex.: δ(q0,a) = { q0, q1 }
• qi Estado inicial
qi ∊ Q qi é um dos estados de Q
• F Estados finais
F ⊂ Q F é subconjunto de Q
AFN – Autômatos Finitos Não-determinísticos
• Autômatos Finitos Não-determinísticos*
– O estado atual lê um símbolo e tem várias opções de transição
– O estado atual lê um símbolo e não tem nenhuma opção de transição
• O AFN “trava”, sem reconhecer a sequência (mesmo que o estado seja final),
pois a sequência não foi inteiramente processada 
– Um estado, ao não ler nenhuma entrada, pode ir para outros estados
• Também chamada ε-transições (veremos mais adiante)
AFN – Autômatos Finitos Não-determinísticos
*Em inglês: NFA – Nondeterministic Finite Automaton
• Processamento de sequências
1. M1
AFN – Autômatos Finitos Não-determinísticos
a a a aaa é processada por M1
q0 q0 q0 q0 M1 não termina em estado final
a a a aaa não é processada por M1
q0 q0 q1 ?
a a a aaa é processada por M1
q0 q0 q0 q1 M1 termina em estado final
q0 q1
a,b
a
M1 reconhece
a sequência aaa
• Processamento de sequências
1. M1
AFN – Autômatos Finitos Não-determinísticos
a b ab é processada por M1
q0 q0 q0 M1 não termina em estado final
a b ab não é processada por M1
q0 q1 ?
q0 q1
a,b
a
M1 não reconhece
a sequência ab
• Processamento de sequências
– Um AFN M reconhece uma sequência de entrada α se
existe alguma linha de processamento tal que M
processe toda a sequência α
e
termine em um estado final
AFN – Autômatos Finitos Não-determinísticos
• Linguagens reconhecidas por AFN’s
1. M1
Notação: L(M1) =
AFN – Autômatos Finitos Não-determinísticos
L( (avb)*a )
• Linguagens reconhecidas por AFN’s
– Equivalência entre os AFN’s e os AFD’s
• Os AFN’s possuem a mesma capacidade de processamento dos AFD’s.
Ou seja:
• Os AFN’s reconhecem linguagens regulares
– Prova
• Todo AFN pode ser convertido em um AFD
AFN – Autômatos Finitos Não-determinísticos
• Convertendo AFN’s em AFD’s
– 1º Passo: grafo → tabela do AFN
• Exemplo: M1 → M1’
AFN – Autômatos Finitos Não-determinísticos
q0 q1
a,b
a
AFN a b
> q0 {q0,q1} {q0}
* q1 ∅ ∅
Marca de estado final
q1 ∊ F
• Convertendo AFN’s em AFD’s
– 2º Passo: tabela do AFN → tabela do AFD
• Exemplo: M1 → M1’
AFN – Autômatos Finitos Não-determinísticos
AFN a b
> q0 {q0,q1} {q0}
* q1 ∅ ∅
AFD a b
> e0 = {q0} e1 = {q0,q1} e0 = {q0}
* e1 = {q0,q1} e1 = {q0,q1} e0 = {q0}
Estado final do AFD:
contém q1 (estado final do AFN)
• Convertendo AFN’s em AFD’s
– 3º Passo: tabela do AFD → grafo do AFD
• Exemplo: M1 → M1’
L(M1’) = L ( (avb)*a )
AFN – Autômatos Finitos Não-determinísticos
AFD a b
> e0 e1 e0
* e1 e1 e0
M1’
• Processamento de sequências
2. M2
L(M1) =
AFN – Autômatos Finitos Não-determinísticos
q0
a,b
a
q2q1
a
L( (avb)*aa )
• Processamento de sequências
2. M2
M2 reconhece
a sequência baa
AFN – Autômatos Finitos Não-determinísticos
b a a baa é processada por M2
q0 q0 q0 q1 M1 não termina em estado final
b a a baa é processada por M2
q0 q0 q1 q2 M1 termina em estado final
q0
a,b
a
q2q1
a
• Convertendo AFN’s em AFD’s
– 1º Passo: grafo → tabela do AFN
• Exemplo: M2 → M2’
AFN – Autômatos Finitos Não-determinísticos
q0
a,b
a
q2q1
a
AFN a b
> q0 {q0,q1} {q0}
q1 {q2} ∅
* q2 ∅ ∅
• Convertendo AFN’s em AFD’s
– 2º Passo: tabela do AFN → tabela do AFD
• Exemplo: M2 → M2’
AFN – Autômatos Finitos Não-determinísticos
AFD a b
> e0 = {q0} e1 = {q0,q1} e0 = {q0}
e1 = {q0,q1} e2 = {q0,q1,q2} e0 = {q0}
* e2 = {q0,q1,q2} e2 = {q0,q1,q2} e0 = {q0}
AFN a b
> q0 {q0,q1} {q0}
q1 {q2} ∅
* q2 ∅ ∅
• Convertendo AFN’s em AFD’s
– 3º Passo: tabela do AFD → grafo do AFD
• Exemplo: M2 → M2’
L(M2’) = L ( (avb)*aa )
AFN – Autômatos Finitos Não-determinísticos
AFD a b
> e0 e1 e0
e1 e2 e0
* e2 e2 e0
M2’
• Exercícios para serem resolvidos em aula
– Converta os AFN’s abaixo para seus AFD’s equivalentes
a) M3 b) M4
AFN – Autômatos Finitos Não-determinísticos
• Exercícios
– Converta os AFN’s abaixo para seus AFD’s equivalentes
a) M4 b) M5
AFN – Autômatos Finitos Não-determinísticos
L(M5) = L [ (a v b)*a(a v b) ]L(M4) = L [ (a v b)* aa (a v b)* ]
• Gabarito a) M3 → M3’
1º Passo: grafo → tabela do AFN
AFN – Autômatos Finitos Não-determinísticos
AFN a b
> q0 {q0,q1} {q0,q3}
q1 {q2} ∅
* q2 ∅ ∅
q3 ∅ {q4}
* q4 ∅ ∅
• a) M3 → M3’
2º Passo: tabela AFN → tabela AFD
AFN – Autômatos Finitos Não-determinísticos
AFD a b
> e0 = {q0} e1 = {q0,q1} e2 = {q0,q3}
e1 = {q0,q1} e3 = {q0,q1,q2} e2 = {q0,q3}
e2 = {q0,q3} e1 = {q0,q1} e4 = {q0,q3,q4}
* e3 = {q0,q1,q2} e3 = {q0,q1,q2} e2 = {q0,q3}
* e4 = {q0,q3,q4} e1 = {q0,q1} e4 = {q0,q3,q4}
AFN a b
> q0 {q0,q1} {q0,q3}
q1 {q2} ∅
* q2 ∅ ∅
q3 ∅ {q4}
* q4 ∅ ∅
• a) M3 → M3’
3º Passo: tabela AFD → grafo AFD
AFN – Autômatos Finitos Não-determinísticos
AFD a b
> e0 = {q0} e1 = {q0,q1} e2 = {q0,q3}
e1 = {q0,q1} e3 = {q0,q1,q2} e2 = {q0,q3}
e2 = {q0,q3} e1 = {q0,q1} e4 = {q0,q3,q4}
* e3 = {q0,q1,q2} e3 = {q0,q1,q2} e2 = {q0,q3}
* e4 = {q0,q3,q4} e1 = {q0,q1} e4 = {q0,q3,q4}
• AFN com ε-transições
– ε
• Outra notação para sequência vazia
– ε-transição
• Transição sem a leitura de nenhum símbolo da entrada
AFN – Autômatos Finitos Não-determinísticos
• AFN com ε-transições
– Exemplos
M1
AFN – Autômatos Finitos Não-determinísticos
Sequências reconhecidas:
• a, b
• aa, aaa, aaaa, ...
• ba, baa, baaa, ...
• AFN com ε-transições
– Exemplos
M1
AFN –Autômatos Finitos Não-determinísticos
Sequências não reconhecidas:
• λ (ou ε)
• ab, aab, aaab, ...
• bb, bab, baab, ...
• bbb, bbbb, bbbbb, ...
• AFN com ε-transições
– Exemplos
M1
AFN – Autômatos Finitos Não-determinísticos
L(M1) = L [ (a v b) a* ]
• AFN com ε-transições
– Exemplos
M2
AFN – Autômatos Finitos Não-determinísticos
Sequências reconhecidas:
• λ (ou ε)
• ab, aab, aaab, ...
• abb, aaab, aaabbbb, ...
• ba, bab, babb, babbb, ...
• abba, aabbbabbaabbb, ...
• baab, babbaab, ...
• AFN com ε-transições
– Exemplos
M2
AFN – Autômatos Finitos Não-determinísticos
Sequências não reconhecidas:
• a, aa, aaa, ...
• b, bb, bbb, ...
• baa, baaa, baaaa, ...
• aba, aaabaaa, ...
• AFN com ε-transições
– Exemplos
M2
AFN – Autômatos Finitos Não-determinísticos
L(M2) = L [ (aa*bb* v bab*)* ]
• AFN com ε-transições
– Exercício
POSCOMP 2008
43) Considere o autômato finito mostrado na figura abaixo (círculos em negrito representam estados 
terminais).
A esse respeito, assinale a afirmativa FALSA.
A) A palavra aaa é reconhecida pelo autômato.
B) A palavra ababa não é reconhecida pelo autômato.
C) A palavra vazia é reconhecida pelo autômato.
D) A palavra aba é reconhecida pelo autômato.
E) A palavra baba é reconhecida pelo autômato.
AFN – Autômatos Finitos Não-determinísticos
Respostas no próximo slide
• AFN com ε-transições
– Exercício
POSCOMP 2008
43) Considere o autômato finito mostrado na figura abaixo (círculos em negrito representam estados 
terminais).
A esse respeito, assinale a afirmativa FALSA.
A) A palavra aaa é reconhecida pelo autômato.
B) A palavra ababa não é reconhecida pelo autômato.
C) A palavra vazia é reconhecida pelo autômato.
D) A palavra aba é reconhecida pelo autômato.
E) A palavra baba é reconhecida pelo autômato.
AFN – Autômatos Finitos Não-determinísticos
• AFN com ε-transições
– Exercício
Para o AFN M ao lado, qual a expressão 
regular correspondente a L(M)?
AFN – Autômatos Finitos Não-determinísticos
Respostas no próximo slide
• AFN com ε-transições
– Exercício
Para o AFN M ao lado, qual a expressão 
regular correspondente a L(M)?
AFN – Autômatos Finitos Não-determinísticos
L(M) = L [ (aa v bb) (aa v bb)* ]
AFN – Autômatos Finitos Não-determinísticos
• Referência
– HOPCROFT, John E; MOTWANI, Rajeev; ULMAN, Jeffrey D.
Introdução à teoria dos autômatos, linguagens e computação.
Rio de Janeiro: Elsevier, 2002.
Obrigado!