Construa um AFD , com alfabeto Σ={0,1}, que aceitam as linguagens:
{Toda sub-cadeia 00 deve ser seguida imediatamente por um 1 }. obs. As cadeias 101, 0010, 0010011001 são aceitas. Mas as cadeias 0001, 00100 não deve ser aceitas.

Passo 1

O que o enunciado pede: construir um AFD que aceite exatamente as cadeias sobre o alfabeto \Sigma=\{0,1\} que satisfazem a condição "toda sub-cadeia \,00, deve ser seguida imediatamente por um \,1". \n
Informações dadas e exemplos:
  • Alfabeto: \Sigma=\{0,1\}.
  • Deve aceitar cadeias como "101", "0010", "0010011001".
  • Não deve aceitar cadeias como "0001" (porque há um "00" seguido por 0) e "00100" (porque a cadeia termina em "00", sem o 1 obrigatório após esse "00").\n
    Observação importante: cadeias que não contêm "00" (por exemplo a cadeia vazia ou "1", "10") também devem ser aceitas, já que não violam a condição.

Passo 2

Ideia principal (intuição): para decidir se uma cadeia é aceita precisamos, ao ler da esquerda para a direita, lembrar se acabamos de ver um 0 ou dois zeros consecutivos sem ter visto ainda o símbolo que deve obrigatoriamente vir depois. Em outras palavras precisamos de memória finita sobre o sufixo lido recentemente:
  • Se o último símbolo lido não foi 0 (ou ainda não lemos nada), não há problema imediato.
  • Se acabamos de ver um único 0, pode vir outro 0 e aí teremos que exigir que o próximo símbolo seja 1.
  • Se acabamos de ver "00", então o próximo símbolo tem de ser 1; se for 0 ou se a cadeia terminar nesse ponto, a cadeia deve ser rejeitada.
  • Se em algum momento vemos um padrão proibido (por exemplo um 0 depois de "00", ou a cadeia acaba quando estamos esperando um 1 depois de "00"), então entramos num estado de erro (sink) que rejeita tudo a partir daí.
Portanto vamos criar estados que representam essas situações e transições que implementam essa exigência.

Passo 3

Definição formal do AFD. Vou apresentar o autômato como o quíntuplo
M=(Q,\Sigma,\delta,q_0,F).
Escolhemos
Q=\{q_0,q_1,q_2,q_{dead}\},
\Sigma=\{0,1\},
q_0 \text{ é o estado inicial},é
F=\{q_0,q_1\}.
Significado intuitivo dos estados:
  • q_0: o sufixo lido não termina em 0 (ou início); não há nenhuma exigência pendente. Estado de aceitação.
  • q_1: o sufixo lido termina em exatamente um 0 (último símbolo é 0, mas não há um "00" pendente). Estado de aceitação.
  • q_2: acabamos de ver "00" e estamos obrigados a ver imediatamente um 1 a seguir; se a cadeia terminar aqui ou vier 0, devemos rejeitar. Estado não aceitante.
  • q_{dead}: estado de erro/sink (não aceitante) — já houve violação da condição.
Transição \delta (tabela):
\delta\!:\! \begin{array}{c|cc} & 0 & 1 \\\ \hline q_0 & q_1 & q_0 \\\ q_1 & q_2 & q_0 \\\ q_2 & q_{dead} & q_0 \\\ q_{dead} & q_{dead} & q_{dead} \end{array}
Explicando a tabela:
  • Em q_0: ao ler 0 passamos para q_1 (agora terminamos em um único 0); ao ler 1 permanecemos em q_0.
  • Em q_1: ao ler 0 formamos "00" e passamos para q_2 (precisamos que o próximo seja 1); ao ler 1 voltamos para q_0.
  • Em q_2: ao ler 1 satisfazemos a exigência após "00" e voltamos para q_0; ao ler 0 ou terminar aqui, a condição é violada, então vamos para q_{dead} (se vier 0) ou não aceitamos caso a cadeia termine em q_2.
  • Em q_{dead}: loop em ambos símbolos — é um sink rejeitante.

Passo 4

Por que os estados de aceitação são q_0 e q_1: uma cadeia é aceita se, ao terminar a leitura, não houver uma ocorrência de "00" que não tenha sido seguida por 1. Se terminamos em q_0 ou q_1 isso significa que não estamos no meio de uma obrigação não satisfeita; mas se terminamos em q_2 significa que a cadeia terminou logo após "00" (ou seja, não houve o 1 exigido) — então devemos rejeitar. q_{dead} também é rejeitante por representar violação já detectada.
Testando com os exemplos (vou mostrar o percurso de estados, usando as cadeias entre aspas):
  • Para \\ "101": \,q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_0. Termina em q_0\in F → aceita.
  • Para \\ "0010": \,q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2 \xrightarrow{1} q_0 \xrightarrow{0} q_1. Termina em q_1\in F → aceita.
  • Para \\ "0010011001": (passando pelos blocos) sempre que ocorre "00" o próximo símbolo é 1, então o automato passa por q_2 seguido de q_0; ao final chega em q_0 ou q_1. Portanto aceita (pelo percurso concreto o automato nunca entra em q_{dead} nem termina em q_2).
  • Para \\ "0001": \,q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2 \xrightarrow{0} q_{dead} \xrightarrow{1} q_{dead}. Termina em q_{dead}\notin F → rejeita, como desejado.
  • Para \\ "00100": \,q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2. Termina em q_2\notin F → rejeita, como desejado.

Passo 5

Argumento de correção (por invariantes): Definimos os estados com significados precisos sobre o sufixo lido; a função de transição implementa exatamente a política "se você vê "00" então o próximo símbolo deve ser 1". \n
  • Invariante de posição: após processar qualquer prefixo x, o autômato fica em um estado que descreve corretamente a situação do sufixo relevante de x: se o sufixo relevante não exige um 1 (ou seja, não há um "00" ainda sem confirmar), então estamos em q_0 ou q_1; se temos "00" sem o 1 seguinte, estamos em q_2; se já houve violação, estamos em q_{dead}.
  • Assim, uma cadeia é aceita sse ela termina em um estado que não exige um 1 (ou seja, em q_0 ou q_1). Então o autômato aceita exatamente as cadeias que satisfazem a condição pedida.
Se quiser, este autômato pode ser desenhado graficamente com os quatro estados e as setas conforme a tabela de transição. Ele é também minimal no sentido intuitivo: precisamos distinguir pelo menos as situações “nenhum zero pendente”, “um zero pendente”, “dois zeros esperando 1” e “violação”, portanto quatro estados são naturais aqui.

Resposta

M=(Q,\Sigma,\delta,q_0,F)
Q=\{q_0,q_1,q_2,q_{dead}\},\qquad \Sigma=\{0,1\},\qquad q_0\\ \text{inicial},\qquad F=\{q_0,q_1\}
\delta\!:\! \begin{array}{c|cc} & 0 & 1 \\\ \hline q_0 & q_1 & q_0 \\\ q_1 & q_2 & q_0 \\\ q_2 & q_{dead} & q_0 \\\ q_{dead} & q_{dead} & q_{dead} \end{array}

Exercícios relacionados