Construa um AFD , com alfabeto Σ={0,1}, que aceitam as linguagens:
{Toda sub-cadeia de tamanho 4 deve ter no máximo dois " 0 " \}. obs. As cadeias 001110, 011001 são aceitas. Mas as cadeias 10010 não é aceita.

Passo 1

O enunciado pede: construir um autômato finito determinístico (AFD) com alfabeto \Sigma=\{0,1\} que aceite exatamente as cadeias em que "toda sub-cadeia de tamanho 4 deve ter no máximo dois 0". Informações dadas/observações do enunciado:
  • Exemplos aceitos: 001110 e 011001.
  • Exemplo rejeitado: 10010.
  • Interpretação precisa: para cada posição da palavra onde existe uma subcadeia de comprimento 4, essa subcadeia não pode conter 3 ou 4 zeros (ou seja, deve ter no máximo dois zeros).
  • Para palavras com comprimento menor que 4 a condição vale trivialmente (são aceitas).

Passo 2

Idea central (sem resolver ainda): para verificar a condição "toda sub-cadeia de tamanho 4 tem no máximo dois 0", quando eu leio o próximo símbolo eu preciso saber quais foram os últimos 3 símbolos lidos, porque ao concatenar o símbolo atual com os últimos 3 eu obtenho a sub-cadeia de tamanho 4 que precisa ser checada. Então o autômato deve “lembrar” o sufixo (sufixo = final) da palavra lida de tamanho até 3. Se ao formar uma janela de 4 símbolos essa janela tiver 3 ou mais zeros, vamos para um estado isolado de rejeição (estado morte) e ficamos nele para sempre. Por isso construiremos estados que representam todos os sufixos possíveis de comprimento 0,1,2,3 e um estado morte.
Explicação curta de por que isso basta:
  • Se eu sempre guardo os últimos 3 símbolos, quando chega um novo símbolo eu consigo formar a janela de 4 (últimos 3 + novo) e checar o número de zeros nela. Isso é exatamente o que um DFA precisa: memória finita (aqui os 3 últimos símbolos) para decidir cada próxima transição.

Passo 3

Definição dos estados (intuição): cada estado corresponde ao sufixo lido mais recente de tamanho até 3. Vou nomear os estados exatamente pelo sufixo que representam. Os estados são:
\begin{aligned} &\varepsilon\quad(\text{nenhum símbolo lido}),\\\ &0,\;1,\\\ &00,\;01,\;10,\;11,\\\ &000,\;001,\;010,\;011,\;100,\;101,\;110,\;111,\\\ &d\quad(\text{estado morte / rejeição}). \end{aligned}íçã
Aqui \varepsilon é o sufixo vazio; d é o estado que representa que já foi encontrada alguma janela de tamanho 4 com 3 ou 4 zeros (violação).

Passo 4

Estado inicial e estados de aceitação:
  • Estado inicial q_0 = \varepsilon.
  • Estados de aceitação F: todas as cadeias que não caíram em violação são aceitas, portanto
F = \{\varepsilon,\,0,\,1,\,00,\,01,\,10,\,11,\,000,\,001,\,010,\,011,\,100,\,101,\,110,\,111\}.
O estado d não é de aceitação. Observação: palavras de comprimento menor que 4 ficam em algum estado que não é d, então são aceitas, como queremos.

Passo 5

Regra geral de transição (descrição do \delta):
  • Se o autômato está em um estado que representa um sufixo s com |s|<3 e lê o símbolo a\in\{0,1\}, então o novo sufixo é simplesmente s concatenado com a; o estado passa a ser o sufixo final de |s|+1 símbolos:
\delta(s,a) = \text{últimos }\big(|s|+1\big)\text{ símbolos de }(s a).úí
(Ex.: de s=01 com a=1 vai para o estado 011 se |s|+1=3; de s=0 com a=1 vai para 01.)
  • Se o autômato está em um estado que representa um sufixo s com |s|=3 e lê a, então formamos a janela s a de tamanho 4. Se essa janela contém \ge 3 zeros (ou seja, exatamente 3 ou 4 zeros), houve violação e
\delta(s,a) = d.
Caso contrário (a janela tem 0, 1 ou 2 zeros), então o novo sufixo de tamanho 3 é os últimos 3 símbolos de s a, então
\delta(s,a) = \text{últimos 3 símbolos de }(s a).úí
  • Para o estado morte d, qualquer símbolo leva de volta a d:
\delta(d,a)=d\quad\text{para }a\in\{0,1\}.

Passo 6

Vou dar alguns exemplos concretos de transições para fixar a ideia (usando a regra acima):
  • Estado s=001 e a=0: s a = 0010. Conte os zeros em 0010: há três zeros, então \delta(001,0)=d.
  • Estado s=001 e a=1: s a = 0011. Conta zeros: duas zeros apenas, então \delta(001,1)=011 (últimos 3 símbolos de 0011 são 011).
  • Estado s=11 (tamanho 2) e a=0: s a = 110. Como |s|<3, não existe janela de 4 ainda; \delta(11,0)=110.
  • Estado s=\varepsilon e a=1: \delta(\varepsilon,1)=1.

Passo 7

Traço o processamento dos exemplos do enunciado para mostrar que o autômato aceitaria/rejeitaria como pedido (aplico as regras acima passo a passo):
  1. 001110:
  • Começa em \varepsilon.
  • 0: vai para 0.
  • 0: vai para 00.
  • 1: vai para 001.
  • 1: agora |s|=3 com s=001 e a=1. s a = 0011 tem dois zeros → \delta(001,1)=011.
  • 1: |s|=3 com s=011 e a=1. s a = 0111 tem um zero → \delta(011,1)=111.
  • 0: |s|=3 com s=111 e a=0. s a = 1110 tem um zero → \delta(111,0)=110.
    Termina em 110, que é um estado de aceitação → palavra aceita.
  1. 011001:
  • \varepsilon \xrightarrow{0} 0 \xrightarrow{1} 01 \xrightarrow{1} 011 \xrightarrow{0} 110 (pois 0110 tem dois zeros?) — verificar: 0110 tem dois zeros? Na verdade 0110 tem dois zeros (os extremos). Logo \delta(011,0)=110.
  • Continua 110 \xrightarrow{0} 100 (pois 1100 não foi formado ainda? atenção: de 110 ao ler 0 formamos 1100 que tem três zeros? contar zeros em 1100: dois zeros → \delta(110,0)=100)).
  • Continua 100 \xrightarrow{1} 001 (pois 1001 tem dois zeros → últimos 3 símbolos são 001).
    Termina em 001 (aceitação). Portanto aceita.
  1. 10010:
  • \varepsilon \xrightarrow{1} 1 \xrightarrow{0} 10 \xrightarrow{0} 100 \xrightarrow{1} 001 (pois 1001 tem dois zeros) \xrightarrow{0} agora s=001 e a=0: 0010 tem três zeros → vai para d.
    Termina em d (rejeição). Portanto rejeitado, como desejado.

Passo 8

Observações finais: o autômato descrito é determinístico, aceita exatamente as cadeias em que nenhuma janela de tamanho 4 tem 3 ou 4 zeros. A construção é mecânica e direta: reter os últimos 3 símbolos basta para checar a condição ao ler o próximo símbolo. O único estado não aceitante é o estado morte d.

Resposta

M=(Q,\Sigma,\delta,q_0,F) onde
\Sigma=\{0,1\},
Q=\{\varepsilon,\,0,\,1,\,00,\,01,\,10,\,11,\,000,\,001,\,010,\,011,\,100,\,101,\,110,\,111,\,d\},
q_0=\varepsilon,
F=Q\setminus\{d\},
e \delta definida por:
\begin{cases} \text{se }s\in Q\setminus\{d\}\text{ e }|s|<3,\\ \delta(s,a)=\text{últimos }(|s|+1)\text{ símbolos de }(s a),\\[4pt] \text{se }s\in Q\setminus\{d\}\text{ e }|s|=3,\\ \delta(s,a)=\begin{cases} d, & \text{se }s a\text{ (janela de 4) contém }\ge 3\text{ zeros},\\\ \text{últimos 3 símbolos de }(s a), & \text{caso contrário}, \end{cases}\\[6pt] \delta(d,a)=d\quad\text{para }a\in\{0,1\}. \end{cases}úíéúíá]

Exercícios relacionados