Construa os seguintes AFDs para reconhecer as intersecção entre as linguagens solicitadas, todo os alfabetos são \Sigma=\{\mathrm{a}, \mathrm{b}\} :
\{\mathrm{w} \mid \mathrm{w} possui a sub-cadeia “aa” pelo menos duas vezes }.

Passo 1

O enunciado pede a construção de um AFD que reconheça a linguagem sobre o alfabeto \Sigma=\{\mathrm{a},\mathrm{b}\} formada por todas as palavras \mathrm{w} que possuem a sub-cadeia "aa" pelo menos duas vezes.
Informações relevantes fornecidas pelo enunciado:
\Sigma=\{\mathrm{a},\mathrm{b}\}
A linguagem é
L=\{\mathrm{w}\in\Sigma^* \mid \text{a palavra }\mathrm{w}\text{ contém a sub-cadeia }"aa"\text{ pelo menos duas vezes}\}.é
O objetivo é construir um AFD que aceite exatamente as palavras de L.

Passo 2

Entendendo bem o que significa “possuir a sub-cadeia "aa" pelo menos duas vezes”:
  • Sub-cadeia "aa" significa duas letras consecutivas \mathrm{a}\mathrm{a} em algum ponto da palavra.
  • Essas ocorrências podem ser sobrepostas. Exemplo: a palavra \mathrm{aaa} tem duas ocorrências de "aa": posições (1,2) e (2,3).
  • Exemplos para fixar:
    \mathrm{bbaaab} contém "aa" duas vezes? Sim, porque a parte central \mathrm{aaa} dá duas ocorrências sobrepostas.
    \mathrm{abaa} contém "aa" uma vez (apenas no final) → rejeitar.
    \mathrm{aaabb} contém "aa" uma vez no começo → rejeitar.
    \mathrm{aabaa} contém "aa" duas vezes → aceitar.
É crucial que o autômato consiga:
  • detectar quando aparece uma \mathrm{a} e lembrar que ela pode formar uma "aa" com a próxima \mathrm{a};
  • contar até duas ocorrências (apenas distinguir 0, 1 e “já vi pelo menos 2”);
  • lidar com sobreposição (por exemplo, ao ver "aa" e em seguida outra \mathrm{a}, isso pode imediatamente formar nova "aa").

Passo 3

Ideia do método (sem formalizar o autômato ainda): usamos estados que codificam duas informações essenciais:
  1. Quantas ocorrências de "aa" já foram encontradas: 0, 1 ou \ge 2.
  2. Se o último símbolo lido foi uma \mathrm{a} (ou não), porque uma \mathrm{a} pendente pode, com a próxima \mathrm{a}, formar uma nova ocorrência.
Assim, vamos construir estados que combinam “contagem parcial” e "se o último caractere foi \mathrm{a}". Quando a contagem chega a 2 ou mais, entramos num estado aceitante e permanente (sink aceitante), pois a partir daí tudo deve ser aceito.

Passo 4

Definição intuitiva dos estados que vamos usar (todo isso é explicação didática do que cada estado representa):
  • q_0: estado inicial. Ainda não vimos nenhuma ocorrência de "aa" e o último símbolo lido não é uma \mathrm{a} (ou ainda não lemos nada).
  • q_1: não vimos nenhuma ocorrência completa de "aa" ainda, mas o último símbolo lido foi uma \mathrm{a} (ou seja, temos uma \mathrm{a} “pendente” que pode formar um "aa" se vier outra \mathrm{a}).
  • q_2: já vimos exatamente uma ocorrência de "aa" e o último símbolo lido não é uma \mathrm{a}.
  • q_3: já vimos exatamente uma ocorrência de "aa" e o último símbolo lido foi uma \mathrm{a} (ou seja, após a primeira ocorrência temos uma \mathrm{a} que pode iniciar a segunda ocorrência).
  • q_4: já vimos pelo menos duas ocorrências de "aa". Estado aceitante e que permanece aceitante com qualquer continuação (sink aceitante).
Comentário rápido sobre sobreposição: ao estar em q_1 (uma \mathrm{a} pendente, zero ocorrências), ler \mathrm{a} forma imediatamente uma ocorrência e o último símbolo continua sendo \mathrm{a}, então devemos transitar para um estado que represente "uma ocorrência, último símbolo \mathrm{a}" — esse é exatamente q_3. Isso permite contar ocorrências sobrepostas corretamente.

Passo 5

Agora construímos as transições, explicando cada caso:
Transições a partir de q_0 (nenhuma ocorrência, último não-a):
  • ler \mathrm{a}: passo para q_1 (agora temos uma \mathrm{a} pendente).
  • ler \mathrm{b}: permaneço em q_0 (a leitura de \mathrm{b} não cria "aa" e não deixa uma \mathrm{a} pendente).
Transições a partir de q_1 (nenhuma ocorrência, último foi \mathrm{a}):
  • ler \mathrm{a}: isso forma uma ocorrência de "aa". Contagem passa de 0 para 1; o último símbolo é \mathrm{a}, então vamos para q_3 (uma ocorrência, último \mathrm{a}).
  • ler \mathrm{b}: a \mathrm{a} pendente é “perdida” (não forma "aa"), voltamos para q_0.
Transições a partir de q_2 (já vimos 1 ocorrência, último não-a):
  • ler \mathrm{a}: vai para q_3 (mantemos 1 ocorrência, mas agora há uma \mathrm{a} pendente para possivelmente formar a segunda).
  • ler \mathrm{b}: permaneço em q_2 (continua 1 ocorrência, último não-a).
Transições a partir de q_3 (já vimos 1 ocorrência, último foi \mathrm{a}):
  • ler \mathrm{a}: forma a segunda ocorrência (pelo menos duas ocorrências agora), vamos para q_4 (estado aceitante).
  • ler \mathrm{b}: a \mathrm{a} pendente se perde; continuo com 1 ocorrência e último não-a → q_2.
Transições a partir de q_4 (pelo menos 2 ocorrências):
  • ler \mathrm{a} ou \mathrm{b}: permaneço em q_4 (já aceitei; é um sink aceitante).
Essas regras cobrem todos os casos e tratam sobreposições corretamente (por exemplo, sequência \mathrm{aaa}: q_0\overset{\mathrm{a}}{\to}q_1\overset{\mathrm{a}}{\to}q_3\overset{\mathrm{a}}{\to}q_4, aceitação).

Passo 6

Formalizando o AFD como uma 5-tupla (Q,\Sigma,\delta,q_0,F):
  • Conjunto de estados:
Q=\{\,q_0,q_1,q_2,q_3,q_4\,\}.
  • Alfabeto:
\Sigma=\{\mathrm{a},\mathrm{b}\}.
  • Estado inicial:
q_0.
  • Conjunto de estados finais:
F=\{q_4\}.
  • Função de transição \delta: Q\times\Sigma\to Q (escrita explicitamente):
\begin{aligned} \delta(q_0,\mathrm{a})&=q_1,&\quad \delta(q_0,\mathrm{b})&=q_0,\\[4pt] \delta(q_1,\mathrm{a})&=q_3,&\quad \delta(q_1,\mathrm{b})&=q_0,\\[4pt] \delta(q_2,\mathrm{a})&=q_3,&\quad \delta(q_2,\mathrm{b})&=q_2,\\[4pt] \delta(q_3,\mathrm{a})&=q_4,&\quad \delta(q_3,\mathrm{b})&=q_2,\\[4pt] \delta(q_4,\mathrm{a})&=q_4,&\quad \delta(q_4,\mathrm{b})&=q_4. \end{aligned}]

Passo 7

Verificação por exemplos rápidos para ganhar confiança:
  • \mathrm{aaa}: q_0\overset{\mathrm{a}}{\to}q_1\overset{\mathrm{a}}{\to}q_3\overset{\mathrm{a}}{\to}q_4 → aceito (tem duas ocorrências: posições (1,2) e (2,3)).
  • \mathrm{abaa}: q_0\overset{\mathrm{a}}{\to}q_1\overset{\mathrm{b}}{\to}q_0\overset{\mathrm{a}}{\to}q_1\overset{\mathrm{a}}{\to}q_3 → termina em q_3, não aceito (só uma ocorrência).
  • \mathrm{bbaaabb}: percorre e chega a q_4 quando a segunda ocorrência aparece → aceito.
Resumo intuitivo: os estados guardam “quantas ocorrências de 'aa' já vi (0,1,>=2)” e "se o último símbolo foi \mathrm{a}". Isso é suficiente para reconhecer exatamente as palavras que têm pelo menos duas ocorrências de "aa".

Resposta

Q=\{q_0,q_1,q_2,q_3,q_4\}
\Sigma=\{\mathrm{a},\mathrm{b}\}
q_0\text{ (inicial)}
F=\{q_4\}
\begin{aligned} \delta(q_0,\mathrm{a})&=q_1,&\quad \delta(q_0,\mathrm{b})&=q_0,\\[4pt] \delta(q_1,\mathrm{a})&=q_3,&\quad \delta(q_1,\mathrm{b})&=q_0,\\[4pt] \delta(q_2,\mathrm{a})&=q_3,&\quad \delta(q_2,\mathrm{b})&=q_2,\\[4pt] \delta(q_3,\mathrm{a})&=q_4,&\quad \delta(q_3,\mathrm{b})&=q_2,\\[4pt] \delta(q_4,\mathrm{a})&=q_4,&\quad \delta(q_4,\mathrm{b})&=q_4. \end{aligned}]

Exercícios relacionados