Construa um AFD , com alfabeto Σ={0,1}, que aceitam as linguagens:
{Toda as cadeia contêm 00 mas não devem conter 000 }.

Passo 1

O enunciado dá o alfabeto \Sigma = \{0,1\} e pede para construir um autômato finito determinístico (AFD) que aceite exatamente as cadeias que satisfazem duas condições simultâneas:
  1. Contêm a substring 00 em algum lugar (ou seja, tem ao menos duas zeros consecutivos em algum ponto).
  2. Não contêm a substring 000 (ou seja, nunca aparecem três zeros consecutivos).
Informações relevantes extraídas do enunciado:
  • O alfabeto é \Sigma = \{0,1\}.
  • Precisamos detectar a ocorrência de 00 (ao menos uma) — essa é uma condição de aceitação.
  • Precisamos também garantir que nunca ocorra 000 — 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:
    1. Se já vimos (em qualquer ponto anterior) a substring 00 (flag “já viu 00” = verdadeiro/falso).
    2. 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é 2, porque ao chegar a 3 zeros consecutivos já devemos rejeitar.
  • Portanto, uma boa estratégia é fazer estados que combinam (a) a informação “já vi 00?” e (b) a informação “quantos zeros seguidos no final (0, 1 ou 2)?”.
  • Se em algum ponto chegarmos a 3 zeros seguidos, vamos para um estado morto (sink) que representa "já apareceu 000" — 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):
  • q_0: começo; ainda não vimos 00 e o sufixo atual não termina em 0 (ou seja, último símbolo não é 0 ou ainda não lemos nada). Interpretação: “flag found = falso, runZeros = 0”.
  • q_1: ainda não vimos 00 e o sufixo atual termina em exatamente um 0 (runZeros = 1). Interpretação: “found = falso, runZeros = 1”.
  • q_2: já vimos 00 em algum ponto, e o sufixo atual não termina em 0 (runZeros = 0). Interpretação: “found = verdadeiro, runZeros = 0”.
  • q_3: já vimos 00 e o sufixo atual termina em exatamente um 0 (runZeros = 1). Interpretação: “found = verdadeiro, runZeros = 1”.
  • q_4: já vimos 00 e o sufixo atual termina em exatamente dois 0 consecutivos (runZeros = 2). Interpretação: “found = verdadeiro, runZeros = 2”. Observe que ao entrar em q_4 acabamos de observar um 00; por isso o flag found passa a verdadeiro.
  • q_{dead}: já apareceu 000 (três zeros consecutivos). Estado de rejeição absorvente (todas as transições ficam nele).
Estado inicial:
  • O estado inicial é q_0.
Estados de aceitação:
  • Aceitamos exatamente os estados em que o flag "já vimos 00" é verdadeiro e não estamos no estado morto. Logo os estados de aceitação serão \{q_2, q_3, q_4\}. (Qualquer um desses indica que já apareceu 00 antes e não apareceu 000.)

Passo 4

Agora construímos a função de transição \delta. Vou explicitar o raciocínio para cada estado e cada símbolo:
Transições a partir de q_0 (ainda não vi 00, sufixo sem zero):
  • Ao ler 1: o sufixo continua sem zeros, não vimos 00 — permanecer em q_0.
  • Ao ler 0: passamos a ter um sufixo com um zero (runZeros = 1), ainda não vimos 00 — ir para q_1.
Transições a partir de q_1 (ainda não vi 00, sufixo termina em exatamente um 0):
  • Ao ler 1: o sufixo passa a terminar com não-zero, não vimos 00 — voltar para q_0.
  • Ao ler 0: agora temos dois zeros consecutivos; isso significa que acabamos de ver 00, então o flag found fica verdadeiro e o runZeros passa a 2 — ir para q_4.
Transições a partir de q_4 (já vimos 00, sufixo termina em exatamente dois zeros):
  • Ao ler 0: teríamos três zeros consecutivos ( 000) — isso viola a condição, então ir para q_{dead}.
  • Ao ler 1: o sufixo passa a terminar sem zeros, e já vimos 00 — ir para q_2.
Transições a partir de q_2 (já vimos 00, sufixo não termina em zero):
  • Ao ler 1: continua sem zeros, permance em q_2.
  • Ao ler 0: sufixo passa a terminar em um zero, já vimos 00 — ir para q_3.
Transições a partir de q_3 (já vimos 00, sufixo termina em exatamente um zero):
  • Ao ler 1: sufixo passa a não terminar em zero, continuar em q_2.
  • Ao ler 0: agora terminamos com duas zeros seguidos; já vimos 00 — ir para q_4.
Transições a partir de q_{dead}:
  • Tanto ao ler 0 quanto 1: permanecer em q_{dead} (estado absorvente).

Passo 5

Coloco a função de transição \delta em forma tabular/lista (cada entrada é \delta(\text{estado},\text{símbolo}) = \text{novo estado}í):
  • \delta(q_0,1) = q_0
  • \delta(q_0,0) = q_1
  • \delta(q_1,1) = q_0
  • \delta(q_1,0) = q_4
  • \delta(q_4,0) = q_{dead}
  • \delta(q_4,1) = q_2
  • \delta(q_2,1) = q_2
  • \delta(q_2,0) = q_3
  • \delta(q_3,1) = q_2
  • \delta(q_3,0) = q_4
  • \delta(q_{dead},0) = q_{dead}
  • \delta(q_{dead},1) = q_{dead}
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: \text{entrada} = 1001
    • Começa em q_0.
    • Ler 1 q_0.
    • Ler 0 q_1.
    • Ler 0 q_4 (aqui vimos 00).
    • Ler 1 q_2.
    • Estado final q_2 é de aceitação. A cadeia contém 00 e não contém 000 — OK.
  • Exemplo rejeitado por não conter 00: \text{entrada} = 10101
    • Passagens alternam entre q_0 e q_1, terminando em q_0 (não found), que não é estado de aceitação — rejeitado corretamente.
  • Exemplo rejeitado por conter 000: \text{entrada} = 110001
    • Em algum ponto a leitura levará q_4 seguido de um 0, entrando em q_{dead}, e permanecerá nele — rejeitado corretamente.

Passo 7

Argumento de correção (por que este AFD reconhece exatamente a linguagem solicitada):
  • Invariantes dos estados:
    • Em q_0 e q_1 o autômato ainda não encontrou nenhum 00 em qualquer prefixo lido (flag found = falso). Em q_0 o sufixo atual não termina em zero; em q_1 termina em exatamente um zero.
    • Em q_2, q_3, q_4 o autômato já encontrou pelo menos um 00 (flag found = verdadeiro). O sufixo atual termina em 0 zeros (em q_2), em 1 zero (em q_3) ou em 2 zeros (em q_4). Nunca se chega a um estado com runZeros = 3; ao ocorrer isso, o autômato vai para q_{dead}.
    • Em q_{dead} já apareceu 000, logo qualquer continuação deve ser rejeitada.
  • Aceitação: os estados de aceitação são exatamente os que correspondem ao fato "já vimos 00" (ou seja, q_2,q_3,q_4), e como não incluímos q_{dead} entre aceitos garantimos que qualquer cadeia que contenha 000 será rejeitada.
  • Portanto, a máquina aceita se e somente se a cadeia contém 00 em algum ponto e nunca contém 000.

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 00?” com o contador de zeros consecutivos até 2. É fácil de construir à mão durante uma prova.
  • Em termos práticos, o autômato tem 6 estados: \{q_0,q_1,q_2,q_3,q_4,q_{dead}\}. 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
\Big(Q,\Sigma,\delta,q_0,F\Big)
com
Q=\{q_0,q_1,q_2,q_3,q_4,q_{dead}\},
\Sigma=\{0,1\},
estado inicial q_0,
conjunto de aceitação F=\{q_2,q_3,q_4\},
e função de transição \delta dada por:
\begin{aligned} &\delta(q_0,1)=q_0,\quad \delta(q_0,0)=q_1,\\[4pt] &\delta(q_1,1)=q_0,\quad \delta(q_1,0)=q_4,\\[4pt] &\delta(q_4,0)=q_{dead},\quad \delta(q_4,1)=q_2,\\[4pt] &\delta(q_2,1)=q_2,\quad \delta(q_2,0)=q_3,\\[4pt] &\delta(q_3,1)=q_2,\quad \delta(q_3,0)=q_4,\\[4pt] &\delta(q_{dead},0)=q_{dead},\quad \delta(q_{dead},1)=q_{dead}. \end{aligned}]

Exercícios relacionados