Construa um AFD , com alfabeto
, que aceitam as linguagens:
{Toda as cadeia contêm 00 mas não devem conter 000 }.
{Toda as cadeia contêm 00 mas não devem conter 000 }.
Passo 1
O enunciado dá o alfabeto
e pede para construir um autômato finito determinístico (AFD) que aceite exatamente as cadeias que satisfazem duas condições simultâneas:
- Contêm a substring
em algum lugar (ou seja, tem ao menos duas zeros consecutivos em algum ponto). - Não contêm a substring
(ou seja, nunca aparecem três zeros consecutivos).
Informações relevantes extraídas do enunciado:
- O alfabeto é
. - Precisamos detectar a ocorrência de
(ao menos uma) — essa é uma condição de aceitação. - Precisamos também garantir que nunca ocorra
— isso força um estado de rejeição caso apareça. - O autômato deve ser determinístico e completo (todas transições definidas).
A resolução começa no próximo passo.
Passo 2
Ideia-chave para modelar com AFD (explicando como pensar):
- Precisamos lembrar duas coisas enquanto lemos a cadeia da esquerda para a direita:
- Se já vimos (em qualquer ponto anterior) a substring
(flag “já viu 00” = verdadeiro/falso). - Quantos zeros consecutivos acabamos de ver no final do prefixo lido até agora (isto é, o comprimento do sufixo contínuo de zeros). Para nossa condição basta memorizar esse comprimento até
, porque ao chegar a zeros consecutivos já devemos rejeitar.
- Se já vimos (em qualquer ponto anterior) a substring
- Portanto, uma boa estratégia é fazer estados que combinam (a) a informação “já vi
?” e (b) a informação “quantos zeros seguidos no final (0, 1 ou 2)?”. - Se em algum ponto chegarmos a
zeros seguidos, vamos para um estado morto (sink) que representa "já apareceu " — esse estado é não aceitando e absorvente.
Vou transformar essa ideia em estados concretos e depois escrever a função de transição.
Passo 3
Definição dos estados com interpretação (cada variável em TeX):
-
: começo; ainda não vimos e o sufixo atual não termina em (ou seja, último símbolo não é ou ainda não lemos nada). Interpretação: “flag found = falso, runZeros = 0”. -
: ainda não vimos e o sufixo atual termina em exatamente um (runZeros = 1). Interpretação: “found = falso, runZeros = 1”. -
: já vimos em algum ponto, e o sufixo atual não termina em (runZeros = 0). Interpretação: “found = verdadeiro, runZeros = 0”. -
: já vimos e o sufixo atual termina em exatamente um (runZeros = 1). Interpretação: “found = verdadeiro, runZeros = 1”. -
: já vimos e o sufixo atual termina em exatamente dois consecutivos (runZeros = 2). Interpretação: “found = verdadeiro, runZeros = 2”. Observe que ao entrar em acabamos de observar um ; por isso o flag found passa a verdadeiro. -
: já apareceu (três zeros consecutivos). Estado de rejeição absorvente (todas as transições ficam nele).
Estado inicial:
- O estado inicial é
.
Estados de aceitação:
- Aceitamos exatamente os estados em que o flag "já vimos
" é verdadeiro e não estamos no estado morto. Logo os estados de aceitação serão . (Qualquer um desses indica que já apareceu antes e não apareceu .)
Passo 4
Agora construímos a função de transição
. Vou explicitar o raciocínio para cada estado e cada símbolo:
Transições a partir de
(ainda não vi
, sufixo sem zero):
- Ao ler
: o sufixo continua sem zeros, não vimos — permanecer em . - Ao ler
: passamos a ter um sufixo com um zero (runZeros = 1), ainda não vimos — ir para .
Transições a partir de
(ainda não vi
, sufixo termina em exatamente um
):
- Ao ler
: o sufixo passa a terminar com não-zero, não vimos — voltar para . - Ao ler
: agora temos dois zeros consecutivos; isso significa que acabamos de ver , então o flag found fica verdadeiro e o runZeros passa a 2 — ir para .
Transições a partir de
(já vimos
, sufixo termina em exatamente dois zeros):
- Ao ler
: teríamos três zeros consecutivos ( ) — isso viola a condição, então ir para . - Ao ler
: o sufixo passa a terminar sem zeros, e já vimos — ir para .
Transições a partir de
(já vimos
, sufixo não termina em zero):
- Ao ler
: continua sem zeros, permance em . - Ao ler
: sufixo passa a terminar em um zero, já vimos — ir para .
Transições a partir de
(já vimos
, sufixo termina em exatamente um zero):
- Ao ler
: sufixo passa a não terminar em zero, continuar em . - Ao ler
: agora terminamos com duas zeros seguidos; já vimos — ir para .
Transições a partir de
:
- Tanto ao ler
quanto : permanecer em (estado absorvente).
Passo 5
Coloco a função de transição
em forma tabular/lista (cada entrada é
):
Essa tabela é completa (cada estado tem transição definida para ambos os símbolos) e determinística.
Passo 6
Verificação rápida por exemplos (simulação mental) para ganhar confiança:
-
Exemplo aceito:
- Começa em
. - Ler
→ . - Ler
→ . - Ler
→ (aqui vimos ). - Ler
→ . - Estado final
é de aceitação. A cadeia contém e não contém — OK.
- Começa em
-
Exemplo rejeitado por não conter
: - Passagens alternam entre
e , terminando em (não found), que não é estado de aceitação — rejeitado corretamente.
- Passagens alternam entre
-
Exemplo rejeitado por conter
: - Em algum ponto a leitura levará
seguido de um , entrando em , e permanecerá nele — rejeitado corretamente.
- Em algum ponto a leitura levará
Passo 7
Argumento de correção (por que este AFD reconhece exatamente a linguagem solicitada):
- Invariantes dos estados:
- Em
e o autômato ainda não encontrou nenhum em qualquer prefixo lido (flag found = falso). Em o sufixo atual não termina em zero; em termina em exatamente um zero. - Em
o autômato já encontrou pelo menos um (flag found = verdadeiro). O sufixo atual termina em 0 zeros (em ), em 1 zero (em ) ou em 2 zeros (em ). Nunca se chega a um estado com runZeros = 3; ao ocorrer isso, o autômato vai para . - Em
já apareceu , logo qualquer continuação deve ser rejeitada.
- Em
- Aceitação: os estados de aceitação são exatamente os que correspondem ao fato "já vimos
" (ou seja, ), e como não incluímos entre aceitos garantimos que qualquer cadeia que contenha será rejeitada. - Portanto, a máquina aceita se e somente se a cadeia contém
em algum ponto e nunca contém .
Passo 8
Observações finais e pequenas otimizações:
- O autômato descrito é limpo e direto: ele usa a combinação do bit “já viu
?” com o contador de zeros consecutivos até . É fácil de construir à mão durante uma prova. - Em termos práticos, o autômato tem
estados: . Pode haver minimizações teóricas (por exemplo, alguns estados podem ser indistinguíveis em certos conjuntos), mas a máquina apresentada é já simples e fácil de justificar numa resposta de prova.
Resposta
O AFD é o quíntuplo
com
estado inicial
,
conjunto de aceitação ,
e função de transição dada por:
conjunto de aceitação
e função de transição