Revisão Autômatos
Teoria da Computação
Pós-graduação em Ciência da Computação –
UFU
Profa. Sandra de Amo
Como detectar se uma linguagem
não é regular ?
Seja L uma linguagem regular
Existe autômato A tal que L(A) = L
A = ({q0,…,qn-1}, S, δ, q0,F)
w = a1 a2 a3 a4 … ak
q0
palavra de L
a1
q1
a2
ak
a3
q2
qs
a4
qi
qj
qf
Como detectar se uma linguagem
não é regular ?
Qual o comprimento máximo de w para que todos
os estados percorridos sejam distintos ?
O caminho percorrido tem no máximo n estados
Logo w tem no máximo comprimento n-1
q0
a1
q1
a2
ak
a3
q2
qs
a4
qi
qj
qf
Como detectar se uma linguagem
não é regular ?
E se comprimento de w for maior ou igual a n ?
O caminho percorrido terá estados repetidos
Seja q2 o primeiro estado que se repete futuramente e
tal que não existem estados repetidos entre as duas ocorrências de q2
q0
a1
q1
a2
ak
a4
q2
a3
qi
qs
q2
sem estados intermediários repetidos
qf
Como detectar se uma linguagem
não é regular ?
E se comprimento de w for maior ou igual a n ?
O caminho percorrido terá estados repetidos
w = a1a2a3a4…ak
ak
q0
a1
qs
q1
a2
q2
qf
a1a2 … ak
a1a2 a3a4 a3a4…ak
a1a2 a3a4 a3a4 a3a4…ak
a4
a3
qi
w = a1a2
x
a3 a4
… ak
y
z
w = a1a2
x
|x y| ≤ n
|y| > 0
y
… ak
z
O caminho percorrido pela palavra
xy tem no máximo um estado repetido (q2)
e
Logo, total de estados percorridos pela palavra
é no máximo n+1.
Portanto a palavra xy tem comprimento máximo n
ak
q0
a3 a4
a1
qs
q1
a2
q2
a4
a3
qi
qf
|y| = comprimento do caminho
percorrido no laço (q2... qi ... q2)
O número mínimo de estados dentro
do laço é zero, o que produziria
|y| = 1
Logo |y| > 0
Como detectar se uma linguagem
não é regular ?
• Se L é regular e w pertence a L e
|w| ≥ n, então:
–w=xyz
– |x y| ≤ n
– |y|>0
– x yk z pertence a L para todo k ≥ 0
Como detectar se uma linguagem
não é regular ?
Se L é regular então
• Existe n > 0 (n = número de estados do automato minimal que
aceita L) tal que:
• Para toda palavra w de L com |w| ≥ n
• Existe uma maneira de dividir w em 3 partes
• Para todo k ≥ 0
w=xyz
| x y | ≤ n, |y| > 0
x yk z pertence a L
Como detectar se uma linguagem
não é regular ?
Se a expressão abaixo nao se verifica
• Existe n > 0 (n = número de estados do automato minimal que aceita L)
tal que:
• Para toda palavra w de L com |w| ≥ n
• Existe uma maneira de dividir w em 3 partes
w=xyz
• Para todo k ≥ 0
| x y | ≤ n, |y| > 0
x yk z pertence a L
então L não é regular
Para mostrar que L não é regular basta
mostrar que a expressao abaixo é falsa !
• Existe n > 0 (n = número de estados do automato minimal que
aceita L) tal que:
• Para toda palavra w de L com |w| ≥ n
• Existe uma maneira de dividir w em 3 partes
w=xyz
| x y | ≤ n, |y| > 0
• Para todo k ≥ 0
x yk z pertence a L
Para mostrar que L não é regular basta
mostrar que a expressao abaixo é falsa !
• Para todo n > 0
• Existe palavra w de L com |w| ≥ n
• Para toda maneira de dividir w em 3 partes
w=xyz
| x y | ≤ n, |y| > 0
• Existe k ≥ 0
x yk z não pertence a L
Exemplo
L = {0k 1k | k ≥ 0} nao é regular
Para todo n > 0
Tenho de exibir uma palavra w de L com
|w| ≥ n
Tal que para toda maneira de dividir w em 3 partes
w=
X
y
com a parte | x y | ≤ n, |y| > 0
Existe um k tal que x yk z não está em L.
z
Exemplo
0
z
y
x
0
0 0 … 0
1
1
y
0 0
x
0
0
…
0
0
…
1
n vezes
n vezes
0
1
y
m vezes, m > n
1
1
… 1
z
n vezes
Não está em L
1