UNIVERSIDADE FEDERAL DE
UBERLÂNDIA
Faculdade de Ciência da Computação
Disciplina : Linguagens Formais e Autômatos - 20 Semestre 2002
Professora : Sandra Aparecida de Amo
Material Suplementar sobre Autômatos
Como garantir que um autômato proposto reconhece uma linguagem dada
Considere a linguagem L = conjunto dos strings com um número par de zeros e um um
número ı́mpar de uns.
Vimos em sala de aula que um autômato candidato para reconhecer esta linguagem é o
seguinte :
0
q0
1
1
1
q1
0
1
0
q2
q3
0
Para termos certeza absoluta de que este autômato A realmente reconhece exatamente a
linguagem L, precisamos provar que :
L(A) = L
Para isto, precisamos mostrar duas coisas : L(A) ⊆ L e L ⊆ L(A).
1. Provemos que L(A) ⊆ L, isto é :
1
P1
Sempre que uma palavra w é reconhecida
pelo autômato A, isto é, sempre que leio uma
palavra w partindo de q0 e chegando em q0 ,
esta palavra necessariamente está em L, isto
é, tem um número par de zeros e um número
par de uns.
Vamos provar P1 por indução sobre o comprimento de w. Infelizmente, uma indução
simples não vai funcionar. Precisamos utilizar uma técnica, chamada de indução mútua.
Antes de continuar, é recomendado ao leitor estudar a seção 1.4.4, páginas 28,
29 e 30 do livro texto.
Esta técnica consiste em provar algo mais forte do que o queremos provar, isto é, algo que
inclui o que queremos provar. No nosso caso, vamos provar P1 ∧ P2 ∧ P3 ∧ P4 onde P1 é a
asserção acima especificada (a que realmente nos interessa) e P2 , P3 e P4 são as asserções
dadas abaixo. Tais asserções são secundárias mas são necessárias para a indução poder
funcionar.
P2
Sempre que leio uma palavra w partindo de
q0 e chegando em q1 , esta palavra tem um
número ı́mpar de zeros e um número par de
uns.
P3
Sempre que leio uma palavra w partindo de
q0 e chegando em q2 , esta palavra tem um
número ı́mpar de zeros e um número ı́mpar
de uns.
P4
Sempre que leio uma palavra w partindo de
q0 e chegando em q3 , esta palavra tem um
número par de zeros e um número ı́mpar de
uns.
2
Provemos, portanto, que P1 ∧ P2 ∧ P3 ∧ P4 é verdade, por indução sobre o comprimento
da palavra w.
Base da indução :
– comprimento de w = 0
Neste caso, w é a palavra vazia e a única possibilidade de ler w partindo de q0 é
chegando em q0 . Ora, é claro que w tem um número par (=0) de zeros e um número
ı́mpar (=0) de uns. Portanto, P1 se verifica e as outras Pi se verificam pois suas
hipóteses são falsas.
– comprimento de w = 1 e w = 0
Neste caso, a única possibilidade de ler w partindo de q0 é chegando em q1 . Ora,
é claro que w tem um número ı́mpar (=1) de zeros e um número par (=0) de uns.
Portanto, P2 se verifica e as outras Pi se verificam pois suas hipóteses são falsas.
– comprimento de w = 1 e w = 1
Neste caso, a única possibilidade de ler w partindo de q0 é chegando em q3 . Ora,
é claro que w tem um número par (=0) de zeros e um número ı́mpar (=1) de uns.
Portanto, P4 se verifica e as outras Pi se verificam pois suas hipóteses são falsas.
Hipótese de Indução : Seja n > 1 e suponhamos que P1 ∧ P2 ∧ P3 ∧ P4 se verifica para
palavras de comprimento < n.
Mostremos que P1 ∧ P2 ∧ P3 ∧ P4 se verifica para palavras de comprimento n.
Seja w uma palavra de comprimento n, onde n > 1. Temos dois casos a considerar :
(a) w termina em zero, isto é, w = w0 0. Quatro subcasos a considerar :
i. Leio w saindo de q0 e chegando em q0 (isto é, estou dentro da hipótese de P1 ).
Tenho que mostrar que w tem um número par de zeros e um número
par de uns.
Realmente, se w = w0 0 e leio w saindo de q0 e chegando em q0 , então :
δ̂(q0 ,w) = q0
Mas, por definição da função de leitura δ̂, temos :
δ̂(q0 ,w) = δ(δ̂(q0 ,w0 ),0) = q0
Ora, de qual estado eu devo partir para, lendo um zero, chegar em q0 ? A resposta,
obviamente é q1 . Portanto,
δ̂(q0 ,w0 ) = q1
Portanto, w0 é uma palavra de comprimento n − 1. Portanto, a hipótese de
indução se verifica para w0 . Repare que a única das Pi na qual w0 se encaixa é
3
P2 , pois leio w0 saindo de q0 e chegando em q1 . Assim, posso afirmar w0 tem um
número ı́mpar de zeros e um número par de uns. Portanto, w tem um número
par de zeros e um número par de uns. OK, consegui mostrar o que queria !
(Veja lá em cima).
ii. Leio w saindo de q0 e chegando em q1 (isto é, estou dentro da hipótese de P2 ).
Tenho que mostrar que w tem um número ı́mpar de zeros e um número
par de uns.
Realmente, se w = w0 0 e leio w saindo de q0 e chegando em q1 , então :
δ̂(q0 ,w) = q1
Mas, por definição da função de leitura δ̂, temos :
δ̂(q0 ,w) = δ(δ̂(q0 ,w0 ),0) = q1
Ora, de qual estado eu devo partir para, lendo um zero, chegar em q1 ? A resposta,
obviamente é q0 . Portanto,
δ̂(q0 ,w0 ) = q0
Portanto, w0 é uma palavra de comprimento n − 1. Portanto, a hipótese de
indução se verifica para w0 . Repare que a única das Pi na qual w0 se encaixa é
P1 , pois leio w0 saindo de q0 e chegando em q0 . Assim, posso afirmar w0 tem um
número par de zeros e um número par de uns. Portanto, w tem um número
ı́mpar de zeros e um número par de uns. OK, consegui mostrar o que
queria ! (Veja lá em cima).
iii. Leio w saindo de q0 e chegando em q2 (isto é, estou dentro da hipótese de P3 ).
Tenho que mostrar que w tem um número ı́mpar de zeros e um número
ı́mpar de uns.
Realmente, se w = w0 0 e leio w saindo de q0 e chegando em q2 , então :
δ̂(q0 ,w) = q2
Mas, por definição da função de leitura δ̂, temos :
δ̂(q0 ,w) = δ(δ̂(q0 ,w0 ),0) = q2
Ora, de qual estado eu devo partir para, lendo um zero, chegar em q2 ? A resposta,
obviamente é q3 . Portanto,
δ̂(q0 ,w0 ) = q3
Portanto, w0 é uma palavra de comprimento n − 1. Portanto, a hipótese de
indução se verifica para w0 . Repare que a única das Pi na qual w0 se encaixa é
4
P4 , pois leio w0 saindo de q0 e chegando em q3 . Assim, posso afirmar w0 tem um
número par de zeros e um número ı́mpar de uns. Portanto, w tem um número
ı́mpar de zeros e um número ı́mpar de uns. OK, consegui mostrar o que
queria ! (Veja lá em cima).
iv. Leio w saindo de q0 e chegando em q3 (isto é, estou dentro da hipótese de P4 ).
Tenho que mostrar que w tem um número par de zeros e um número
ı́mpar de uns.
Realmente, se w = w0 0 e leio w saindo de q0 e chegando em q3 , então :
δ̂(q0 ,w) = q3
Mas, por definição da função de leitura δ̂, temos :
δ̂(q0 ,w) = δ(δ̂(q0 ,w0 ),0) = q3
Ora, de qual estado eu devo partir para, lendo um zero, chegar em q3 ? A resposta,
obviamente é q2 . Portanto,
δ̂(q0 ,w0 ) = q2
Portanto, w0 é uma palavra de comprimento n − 1. Portanto, a hipótese de
indução se verifica para w0 . Repare que a única das Pi na qual w0 se encaixa
é P3 , pois leio w0 saindo de q0 e chegando em q2 . Assim, posso afirmar w0 tem
um número ı́mpar de zeros e um número ı́mpar de uns. Portanto, w tem um
número par de zeros e um número ı́mpar de uns. OK, consegui mostrar
o que queria ! (Veja lá em cima).
(b) w termina em um, isto é, w = w0 1. Quatro subcasos a considerar :
i. Leio w saindo de q0 e chegando em q0 (isto é, estou dentro da hipótese de P1 ).
Tenho que mostrar que w tem um número par de zeros e um número
par de uns.
Realmente, se w = w0 1 e leio w saindo de q0 e chegando em q0 , então :
δ̂(q0 ,w) = q0
Mas, por definição da função de leitura δ̂, temos :
δ̂(q0 ,w) = δ(δ̂(q0 ,w0 ),1) = q0
Ora, de qual estado eu devo partir para, lendo um 1, chegar em q0 ? A resposta,
obviamente é q3 . Portanto,
δ̂(q0 ,w0 ) = q3
5
Portanto, w0 é uma palavra de comprimento n − 1. Portanto, a hipótese de
indução se verifica para w0 . Repare que a única das Pi na qual w0 se encaixa é
P4 , pois leio w0 saindo de q0 e chegando em q3 . Assim, posso afirmar w0 tem um
número par de zeros e um número ı́mpar de uns. Portanto, w tem um número
par de zeros e um número par de uns. OK, consegui mostrar o que queria !
(Veja lá em cima).
ii. Leio w saindo de q0 e chegando em q1 (isto é, estou dentro da hipótese de P2 ).
Tenho que mostrar que w tem um número ı́mpar de zeros e um número
par de uns.
Realmente, se w = w0 1 e leio w saindo de q0 e chegando em q1 , então :
δ̂(q0 ,w) = q1
Mas, por definição da função de leitura δ̂, temos :
δ̂(q0 ,w) = δ(δ̂(q0 ,w0 ),1) = q1
Ora, de qual estado eu devo partir para, lendo um 1, chegar em q1 ? A resposta,
obviamente é q2 . Portanto,
δ̂(q0 ,w0 ) = q2
Portanto, w0 é uma palavra de comprimento n − 1. Portanto, a hipótese de
indução se verifica para w0 . Repare que a única das Pi na qual w0 se encaixa
é P2 , pois leio w0 saindo de q0 e chegando em q2 . Assim, posso afirmar w0 tem
um número ı́mpar de zeros e um número ı́mpar de uns. Portanto, w tem um
número ı́mpar de zeros e um número par de uns. OK, consegui mostrar
o que queria ! (Veja lá em cima).
iii. Leio w saindo de q0 e chegando em q2 (isto é, estou dentro da hipótese de P3 ).
Tenho que mostrar que w tem um número ı́mpar de zeros de uns e
um número ı́mpar de uns.
Realmente, se w = w0 0 e leio w saindo de q0 e chegando em q2 , então :
δ̂(q0 ,w) = q2
Mas, por definição da função de leitura δ̂, temos :
δ̂(q0 ,w) = δ(δ̂(q0 ,w0 ),1) = q2
Ora, de qual estado eu devo partir para, lendo um 1, chegar em q2 ? A resposta,
obviamente é q1 . Portanto,
δ̂(q0 ,w0 ) = q1
6
Portanto, w0 é uma palavra de comprimento n − 1. Portanto, a hipótese de
indução se verifica para w0 . Repare que a única das Pi na qual w0 se encaixa é
P1 , pois leio w0 saindo de q0 e chegando em q1 . Assim, posso afirmar w0 tem um
número ı́mpar de zeros e um número par de uns. Portanto, w tem um número
ı́mpar de zeros e um número ı́mpar de uns. OK, consegui mostrar o que
queria ! (Veja lá em cima).
iv. Leio w saindo de q0 e chegando em q3 (isto é, estou dentro da hipótese de P4 ).
Tenho que mostrar que w tem um número par de zeros e um número
ı́mpar de uns.
Realmente, se w = w0 1 e leio w saindo de q0 e chegando em q3 , então :
δ̂(q0 ,w) = q3
Mas, por definição da função de leitura δ̂, temos :
δ̂(q0 ,w) = δ(δ̂(q0 ,w0 ),1) = q3
Ora, de qual estado eu devo partir para, lendo um 1, chegar em q3 ? A resposta,
obviamente é q0 . Portanto,
δ̂(q0 ,w0 ) = q0
Portanto, w0 é uma palavra de comprimento n − 1. Portanto, a hipótese de
indução se verifica para w0 . Repare que a única das Pi na qual w0 se encaixa é
P1 , pois leio w0 saindo de q0 e chegando em q0 . Assim, posso afirmar w0 tem um
número par de zeros e um número par de uns. Portanto, w tem um número
par de zeros e um número ı́mpar de uns. OK, consegui mostrar o que
queria ! (Veja lá em cima).
2. Provemos que L ⊆ L(A), isto é, que toda palavra com um número par de zeros e um
número par de 1s é reconhecida pelo autômato A, isto é, consigo ler a palavra percorrendo
o autômato saindo de q0 e chegando em q0 .
Novamente, somos obrigados a utilizar uma indução mútua, isto é, provar algo mais forte
do que o que realmente queremos. Vamos mostrar Q1 ∧ Q2 ∧ Q3 ∧ Q4 , onde :
Q1
Se uma palavra w tem um número par de
zeros e um número par de uns então consigo
ler esta palavra partindo de q0 e chegando em
q0 .
7
Q2
Se uma palavra w tem um número par de zeros e um número ı́mpar de uns então consigo
ler esta palavra partindo de q0 e chegando em
q1 .
Q3
Se uma palavra w tem um número ı́mpar de
zeros e um número par de uns então consigo
ler esta palavra partindo de q0 e chegando em
q3 .
Q4
Se uma palavra w tem um número ı́mpar
de zeros e um número ı́mpar de uns então
consigo ler esta palavra partindo de q0 e chegando em q2 .
Repare que o que realmente nos interessa é Q1 . Mas se provarmos que Q1 ∧ Q2 ∧ Q3 ∧ Q4
se verifica para qualquer palavra, então em particular Q1 se verifica.
Exercı́cio 1 Mostre Q1 ∧ Q2 ∧ Q3 ∧ Q4 por indução (mútua) sobre o comprimento de w.
Exercı́cio 2 Considere a linguagem L = strings que contém o substring 01. Considere o
autômato A que vimos em sala de aula, isto é :
0
q0
1
0
q2
0
1
q1
1
Mostre que L(A) = L.
8