Equivalência de
Autômatos
Programa de Pós-graduação em Ciência da
Computação - UFU
Profa. Sandra de Amo
Definição
Sejam M1 e M2 dois autômatos
Dizemos que M1 e M2 são equivalentes se L(M1) = L(M2), isto
é, se as respectivas linguagens aceitas são iguais.
Exemplo:
1
0
q0
0
q1
1
0
1
q0
0
q2
0
q2
1
M1
1
M2
L(M1) = {w | número de 1’s de w é impar}
L(M2) = {w | número de 1’s de w é impar}
Não-determinista ≡ Determinista
1
0
0
M1 ≡ M2
q0
q1
0
M1 (não determinista)
0,1
0
q’3
0
q’2
1
q’0
0
1
q’1
1
M2 (determinista)
q’0 = {q0}
q’1 = {q1}
q’2 = {q0,q1}
q’3 = {}
q’0
q’1
q’2
q’3
0
q’0
q’2
q’2
q’3
1
q’1
q’3
q’1
q’3
δ(q’2,1) = {δ(q0,1)}  {δ(q1,1)} =
{q1}  {} = {q1} = q’1
Execução de Autômatos Deterministas
0,1
0
e não-deterministas
1
0
q’3
0
0
q0
q1
0
w = 101
q0
1
q1
sucesso
q’0
q’1
1
1
1
0
0
1
q’0
q0
q1
q’2
0
q’1
0
q1
q’2
falha
1
q’1
1
Autômato com ϵ-movimentos
ϵ
q
q1
0
q’
q1
1
Passa de q para q’ sem avançar na fita – não lê nada – fica parado
q2
0
1
0,1
ϵ
1
q1
q2
q3
0,1
1
q4
q1
0
q3
1
q1
1
0
q4
q2
q4
ϵ
q3
1
w = 01011
1
1
q4
Autômato com ϵ-movimentos
ϵ
q
q1
0
q’
q1
1
Passa de q para q’ sem avançar na fita – não lê nada – fica parado
q2
0
1
0,1
1
q1
q3
q2
0,1
1
q4
q3
1
q1
1
q4
1
q4
Se q3 fosse final, q2 tornaria-se final na versão sem ϵ
q1
0
0
w = 01011
1
q2
ϵ
q3
1
q4
Autômato com ϵ-movimentos
Se q3 fosse final, q2 tornaria-se final na versão sem ϵ
1
0,1
ϵ
1
q1
q3
q2
0
w=1
0,1
1
q4
Outro exemplo
0
0
q0
q0
q1
0
0
1
ϵ
ϵ
q2
q2
1
q3
q1
1
1
q3
1
Operações com Linguagens Regulares
União de Linguagens Regulares é uma linguagem regular:
L(M1)  L(M2) = L(M1  M2) com ϵ-movimento
M1
ϵ
ϵ
M2
Operações com Linguagens Regulares
União de Linguagens Regulares é uma linguagem regular:
L(M1)  L(M2) = L(M1  M2)
sem ϵ-movimento
M1
ϵ
ϵ
M2
Operações com Linguagens Regulares
Concatenação de Linguagens Regulares é uma linguagem regular:
L(M1). L(M2) = L(M1.M2)
com ϵ-movimento
M1
ϵ
ϵ
ϵ
a
a
a
M2
Operações com Linguagens Regulares
Concatenação de Linguagens Regulares é uma linguagem regular:
L(M1). L(M2) = L(M1.M2)
sem ϵ-movimento
M1
a
a
a
a
a
a
M2
Caso M2 aceite
a palavra vazia
Operações com Linguagens Regulares
Concatenação de Linguagens Regulares é uma linguagem regular:
L(M1). L(M2) = L(M1.M2)
sem ϵ-movimento
Caso M2 não aceite
M1 a palavra vazia
a
a
a
a
a
a
M2
Operações com Linguagens Regulares
Star de Linguagem Regular é uma linguagem regular:
L(M)* = L(M*)
com ϵ-movimento
ϵ
ϵ
ϵ
ϵ
Exercicio : Por que introduzir um novo estado inicial ? Por que não considerar
o antigo estado como inicial, e torná-lo também um estado final para que a
Linguagem L(M*) aceite a palavra vazia ?
Operações com Linguagens Regulares
Star de Linguagem Regular é uma linguagem regular:
L(M)* = L(M*)
sem ϵ-movimento
a
a
a
a
a
a
a
a
a