Ling. Formais e Autômatos
AFN-ε
Tópicos
Autômatos finitos
AF com ε-transições
AF com ε-transições
Definição
 O autômato finito com ε-transições permite
transições sobre ε, a string vazia
 O AFN-ε tem permissão para fazer uma
transição espontaneamente, sem receber um
símbolo de entrada
 Conveniência de programação
q0
ε
q1
AF com ε-transições
Definição
 Um autômato finito com ε-transições consiste
em:
• Um conjunto finito de estados: Q
• Um conjunto finito de símbolos de entrada: Σ
• Uma função de transição que toma como
argumentos um estado em Q e um elemento de Σ
U {ε}: δ
• Um estado inicial (que está em Q)
• Um conjunto de estados finais F (F é um
subconjunto de Q)
AF com ε-transições
Notação:
A = (Q, Σ, δ, q0, F)
Exemplo 1
Construir um AFN que reconheça as
palavras-chave web e ebay
Como ele poderia ser construído?
Exemplo 1
Construir um AFN que reconheça as
palavras-chave web e ebay
 1.º passo: Construímos uma seqüência
completa de estados para cada palavrachave, como se fosse a única palavra que o
autômato precisasse reconhecer
Exemplo 1
Construir um AFN que reconheça as
palavras-chave web e ebay
 O AFN abaixo reconhece a palavra-chave
web
q0
w
q1
e
q2
b
q3
Exemplo 1
Construir um AFN que reconheça as
palavras-chave web e ebay
 O AFN abaixo reconhece a palavra-chave
ebay
q4
e
q5
b
q6
a
q7
y
q8
Exemplo 1
Construir um AFN que reconheça as
palavras-chave web e ebay
 2.º passo: Adicionamos um novo estado
inicial com ε-transições para os estados
iniciais dos autômatos anteriores, que
correspondem a cada uma das palavraschave!
Exemplo 1
Construir um AFN que reconheça as
palavras-chave web e ebay
ε
w
q0
e
q1
b
q2
q3
Início
ε
q4
e
q5
b
q6
a
q7
Acabamos de construir um AFN com ε-transições!
y
q8
Exemplo 2
L = { w | qualquer símbolo a antecede
qualquer símbolo b }
Como seria o AFN-ε que
aceita essa linguagem?
Exemplo 2
L = { w | qualquer símbolo a antecede
qualquer símbolo b }
q0
a
ε
q1
b
ε-fechamento de um estado
Definição informal
 Usamos o ε-fechamento em um estado q
seguindo todas as transições saindo de q
rotuladas por ε. Porém, quando chegamos a
outros estados seguindo ε, acompanhamos
as transições ε que saem desses estados, e
assim por diante, encontrando eventualmente
todo estado que pode ser alcançado a partir
de q ao longo de qualquer caminho cujos
arcos são todos rotulados por ε.
ε-fechamento de um estado
Definição formal
 O estado q está em ECLOSE(q). Se o estado
p está em ECLOSE(q), e existe uma
transição do estado p para o estado r
rotulada por ε, então r está em ECLOSE(q).
Mais precisamente, se δ é a função de
transição do AFN-ε envolvido, e p está em
ECLOSE(q), então ECLOSE(q) também
contém todos os estados em δ(p, ε).
ε-fechamento de um estado
ECLOSE(1) = { ? }
2
ε
ε
3
6
ε
b
1
ε
4
a
5
ε
7
ε-fechamento de um estado
ECLOSE(1) = { 1, 2, 3, 4, 6 }
2
ε
ε
3
6
ε
b
1
ε
4
a
5
ε
7
AF com ε-transições
Considerações
 Dado qualquer AFN-ε E, podemos encontrar
um AFD D que aceita a mesma linguagem
que E.
 Para eliminar as ε-transições, aplica-se uma
construção muito parecida com a construção
de conjuntos, pois os estados de D são
subconjuntos dos estados de E.
• A única diferença é que devemos incorporar as εtransições de E, o que fazemos por meio do
mecanismo do ε-fechamento (ECLOSE).
Ling. Formais e Autômatos
Exp. regulares
Tópicos
Expressões regulares
Introdução
Operadores
Linguagens regulares
De acordo com a Hierarquia de
Chomsky, as linguagens regulares
constituem a classe de linguagens mais
simples, sendo possível desenvolver
algoritmos de reconhecimento, de geração
ou de conversão entre formalismos de
pouca complexidade, de grande eficácia e
de fácil implementação.
Entretanto, as linguagens regulares
possuem fortes limitações de
expressividade.
Linguagens regulares
Um autômato finito reconhece
uma linguagem regular!
Expressões regulares
Toda linguagem regular pode ser descrita
por uma expressão regular
Uma expressão regular é definida a partir
de conjuntos (linguagens) básicos e
operações de concatenação e de união
Expressões regulares
 Ø é uma expressão regular e denota o conjunto { }
 Ε é uma expressão regular e denota o conjunto {ε}
 Para cada a Є Σ, a é uma expressão regular e denota o
conjunto { a }
 Se r e s são expressões regulares denotando os conjuntos
R e S, então (r+s), (rs) e (r*) são expressões regulares e
denotam os conjuntos RUS, RS e R*, respectivamente
Expressões regulares
 Alfabeto: Σ = { 0, 1 }
 00 é expressão regular se 0 é expressão regular
 L(0) L(0) = { 0 } { 0 } = { 0 }
 0+1 é expressão regular se 0 é expressão regular e 1 é
expressão regular
 L(0) U L(1) = { 0 } U { 1 } = { 0, 1 } = Σ
 0* é expressão regular se 0 é expressão regular
 L(0)* = { 0 }* = { ε, 0, 00, 000, 0000, ... }
Expressões regulares
 Precedência:
 *,+
 0+1*
 L(0) U L(1)* = { 0 } U L(1)* = { 0 } U { 1 }* = { 0 } U { ε, 1, 11, ...}=
= { 0, ε, 1, 11, ... }
 Abreviamos rr* por r+
 00*11*22* = 0+1+2+
Exemplo 1
Considerando o alfabeto Σ={ 0, 1 }
E1 = (0+1)* 00 (0+1)*
O que E1 representa?
Exemplo 1
Considerando o alfabeto Σ={ 0, 1 }
E1 = (0+1)* 00 (0+1)* =
L(E1) = L((0+1)*) . L(0) . L(0) . L((0+1)*) =
{0, 1}* . {00} . {0, 1}*
Uma string que tenha, pelo menos,
2 zeros consecutivos!
Exemplo 2
Considerando o alfabeto Σ={ 0, 1 }
E2 = ((0+1) (0+1))*
O que E2 representa?
Exemplo 2
Considerando o alfabeto Σ={ 0, 1 }
E2 = ((0+1) (0+1))* =
L(E2) = L((0+1) (0+1))* = (L(0+1) . L(0+1))* =
= ({0,1} {0,1})* = {ε, 00, 01, 10, 11}*
Cadeias que tenham
comprimento par! (ou ε)
Expressões regulares
AF
Determinístico
AF Não
Determinístico
Expressões
Regulares
Expressões regulares
Simplificações
 Associação
 Distribuição
 Equivalência de fecho
Expressões regulares
Seja r uma expressão regular. Então
existe um AF não determinístico com εtransições que aceita r.
Sérgio Donizetti Zorzo
[email protected]
Paulo R. M. Cereda
[email protected]
Universidade Federal de São Carlos