autômatos finitos com
transições e
p
e
q
o autômato vai do estado p
para o estado q sem ler um
símbolo de entrada.
EXEMPLO 1
s
b
e
t
e
p
b
e
u
e
q
b
r
Estando no estado s e recebendo o símbolo b:
 ler b e ir para p
 ir para t e então ler b e ir para q
 ir para t, ir para u e então ler b e ir para r.
O conjunto aceito pelo autômato acima é
{b, bb, bbb}.
EXEMPLO 2
e
q2
a
q3
a
a
q4
q1
e
q5
a
q8
a
q6
a
q7
a
a
q9
O conjunto aceito pelo autômato acima
é { x  {a*} | |x| é divisível por 3 ou 5}.
A maior vantagem de transições e é a
conveniência.
Autômato com transições e tem o
mesmo poder computacional que afds e
afnds
Propriedades de Linguagens
Regulares
Concatenação de dois conjuntos A e B
A•B = AB = { xy | x  A e y  B}
EXEMPLO.
{a, ab} • {b, ba} = {ab, aba, abb, abba}
Se A e B são conjuntos regulares, AB
também é.
Prova Intuitiva
Seja M o autômato para A e N para B.
 Construir um novo autômato P cujo os
estados são a união dos de M e N.
 Todas as transições de M e N serão
transições de P.
 O estado inicial de M será o de P.
 Os estados finais de N serão os de P.
 Finalmente, ligue os estados finais de
M ao estado inicial de N com uma
transição e.
EXEMPLO 4
Seja A = {aa}, B = {bb}
q0
q0
a
a
q1
q1
a
q2
a
q3
q2
e
q3
b
b
q4
q4
b
q5
b
q5
Fecho de Kleene
Se A é regular então A* também é.
A* = { e}  A  A2  A3  …
= { x1x2…xn | n  0 e xiA , 1  i  n}
Prova Intuitiva
Seja M o autômato para A então P
para A* é como segue:
 Comece
com todos os estados e
transições de M.
 Adicione um novo estado q e uma
transição e de q para o estado
inicial de M. Faça q o estado inicial de
P.
 Faça q o único estado final de P.
transições e dos estados
finais de M para o estado q.
 Adicione
EXEMPLO 5
Dado o autômato para A {aa}, o para
A* :
q
e
q0
e
a
q1
a
q2
Casamento de Padrões e
Expressões Regulares
O que acontece quando digitamos
‘rm *’ no Unix? E ‘rm *.dvi’?
Casamento de padrões é uma aplicação
importante da teoria dos afds.
Seja  um alfabeto finito.
Um padrão é uma cadeia de símbolos
de um certo formato representando um
conjunto (possivelmente infinito) de
cadeias sobre *.
Casamento de Padrões
Padrões: Básicos
Compostos
Notação: letras gregas a , b , g , …
Associado a definição de padrões,
temos quais cadeias x  * casam
com os padrões definidos.
Notação: L(a) é o conjunto de cadeias
em * que casam um dado padrão a.
L(X) = {x  * | X casa com a }
Padrões Básicos
a
e
para cada símbolo a  , L(a) = {a}
casa com a palava vazia e,L(e) = { e }
 f casa com nada, L(f) = f, o cjto.vazio
 # casa com qualquer símbolo em ,
L(#) = 
 @ casa qualquer cadeia em *,
L(@)=*.
Padrões compostos
 São
formados indutivamente usando
os operadores: +, , * , ~ , •
 Suponha que definimos os conjuntos
de cadeias L(a) e L(b) casando a e b
respectivamente. Então dizemos:
 x casa com a + b , se x casa ou com a
ou com b
L(a + b ) = L(a )  L(b)
X
casa com a  b se X casa com
ambos a e b
L(a  b ) = L(a)  L(b)
 X casa com ab se existem cadeias y
e z tal que y casa com a, z casa
com b e x = yz.
L(ab) = L(a)•L(b)
 X casa ~a se X não casa com a.
L(~a) = ~ L(a ) = * \ L(a)
Esta definição depende de .
X
casa a* se x pode ser dividido na
concatenação de várias (talvez
nenhuma) cadeias finitas,
x=x1x2x3…xn, n 0 tal que cada xi
casa com a.
L(a*) = {x1x2…x n| n e xiL(a),1  i  n}
= L(a)0  L(a)1  L(a)2  …= L(a)*
 Note
que Padrões são cadeias de
símbolos sobre o alfabeto:
{ a | a   }  {e, f , #, @, +, , ~, *, (, )}
EXEMPLOS
= L(@) = L(#*)
 Conjuntos com um único símbolo: se
x  * , então, x por se só é um
padrão e casa somente com a cadeia
x, i.e , {x} = L(x)
 Conjuntos finitos: se x1 , … , xm  * ,
então
{x1, x2 , …, xm } = L(x1 + x2 + … + xm )
 *
 cadeias
contendo pelo menos 3
ocorrências de a:
@a@a@a@
 cadeias contendo um a seguido mais
tarde por um b, isto é cadeias da
forma xaybz para algum x, y, z
@a@b@
 \ { a }
#  (~a)
 cadeias sem a ocorrência da letra a
(#  (~a) ) *
Algumas Questões Importantes
 Quão
difícil é determinar se uma dada
cadeia casa um determinado padrão?
(Existem algoritmos muitos eficientes,
veremos alguns deles. Esta é uma
questão prática.
 Todos os conjuntos são representados
por algum padrão?
(Não! Veremos, por exemplo, que o
conjunto {an bn | n  0} não é
representado por nenhum padrão.)
 Quais
operadores são redundantes?
e pois é equivalente a ~(#@) e a f*
@ pois é equivalente a #*
# se  = a1 , a2 , … , an então # é
equivalente a a1 + a2 + … + an .
 a  b é equivalente a ~(~a + ~ b)
 Todos
os padrões são equivalentes a
um padrão usando somente o padrão
básico a para a   , f e os
operadores ~,+ , * e •. Padrões usando
somente estes símbolos são
chamados expressões regulares.
Evitando Parentesis
+ e . São associativas, i. e.
L(a+(b+g)) = L((a+b)+g)
L(a(bg)) = L((ab)g) , e podemos escrever
a+b+g
abg
Precedência:
*
•
Menor
+
Equivalência de Padrões,
Expressões Regulares e Autômatos
Finitos
Teorema:
Seja A  *. As três afirmações abaixo
são equivalentes:
(i) A é regular; i.e., A = L(M) para algum
autômato finito M.
(ii) A = L(a ) para algum padrão a
(iii) A = L(a ) para alguma expressão
regular a .
Prova:

(iii)  (ii)
A implicação (iii)  (ii) é trivial, uma
vez que toda expressão regular é um
padrão por definição.
(ii)  (i)
O coração desta prova envolve mostrar
que outros conjuntos básicos
(correspondendo aos padrões
básicos) são regulares, e que
conjuntos são fechados sobre
operações de fechamento
correspondendo aos operadores
usados para construir padrões.
Note que:
- o conjunto unitário { a } é regular, a 

- o conjunto unitário {} é regular
- o conjunto vazio f é regular, uma vez
que cada um destes conjuntos é um
conjunto aceito por algum autômato.
q0
a
(1)
q1
q0
q0
(2)
Mostramos previamente que os
conjuntos regulares são fechados sobre
o conjunto de operações , , ~ , *, e, ·,
i.e. , se A e B são conjuntos regulares
então A  B, A  B,
~A = *\ A, AB e A* são regulares.
Seja a um dado padrão. Queremos
mostrar que L(a) é um conjunto regular.
Procedemos por indução na estrutura
de a.
O padrão é de uma das seguintes
formas:
(i) a, para algum a 
(vi) b+g
(ii) 
(vii) bg
(iii) f(viii) bg
(iv) #
(ix) ~b
(v) @
(x) b*
São cinco casos base (i) - (v) correspondendo aos padrões atômicos e
cinco casos de indução correspondendo aos padrões compostos.
Para (i) - (iii) temos L(a) = {a} para a 
, L(e L(f) = f estes são
conjuntos regulares.
Para (iv) e (v), argumentamos antes
que os operadores # e @ são dundantes
logo podemos desconsiderar estes
casos.
 Para
(vi), lembre que L(b+g) = L(b)L(g)
pela definição do operador +. Pela
hipótese da indução, L(b) e L(g) são
regulares. Como conjuntos regulares
são fechados sobre a união, L(b+g) =
L(b)  L(g) é regular.
 Para
os casos (vii) - (x) use argumentos similares aos usados em (vii).
convertendo autômatos em
expressões regulares (I)  (iii)
Dado um subconjunto de estados T de
um AFND M e estados u e v,
construamos a expressão regular:
aTuv
representando o conjunto de todas as
cadeias x tal que existe um caminho
de u para v em M rotulado x (isto é ,
d*(u, x) = v) e todos os estados no
caminho, com a possível exceção de u
e v estarem em T.
As expressões são construídas por
indução no tamanho de T.
Base T = f
Seja a1, … , ak todos os símbolos em 
tal que
d (u, ai) = v.
afuv = a1 + … + ak
se u  v
a1 + … + ak +  se u = v
Indução
Tf
Escolha um elemento qualquer q  T
aTuv = auvT-{q} + auqT-{q} (aqqT-{q} )* aqvT-{q}
Note que qualquer caminho de u para v
com todos os estados intermediários
em T ou :
(i) nunca visita q :
auvT-{q}
ou
(ii) visita q uma primeira vez: auqT-{q}
Seguido por um número finito (≥ zero)
de laços de q para q sem visitar q no
meio tempo e ficando em q :
(aqqT-{q} )*
Seguido por um caminho de q para v
deixando q pela última vez
aqvT-{q}
A expressão:
aQsf1 + aQsf2 + … + aQsfk
representa o conjunto de cadeias
aceitas por M, onde
Q é o conjto de todos os estados de M,
s é o estado inicial e
{ f1 , … , fk } é o conjunto de estados
finais.
Ex: Converta o autômato em uma
expressão regular equivalente .
1
0
q
p
1
0
0
r
T={p,q,r}
app{p,q,r}
Remova q
a
pp
{p,q,r} =
app{p,r}
T- {q}
app{p,r} + apq {p,r}(aqq{p,r})* aqp{p,r}
= 0*
apq{p,r} = 0*1
aqq{p,r} = e + 01 + 000*1
aqp{p,r} = 000*
app{p,q,r} = 0* + 0*1 (e + 01 + 000*1 )*000*