Construa os seguintes AFDs para reconhecer as intersecção entre as linguagens solicitadas, todo os alfabetos são
:
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
formada por todas as palavras
que possuem a sub-cadeia
pelo menos duas vezes.
Informações relevantes fornecidas pelo enunciado:
Informações relevantes fornecidas pelo enunciado:
A linguagem é
O objetivo é construir um AFD que aceite exatamente as palavras de
.
Passo 2
Entendendo bem o que significa “possuir a sub-cadeia
pelo menos duas vezes”:
- Sub-cadeia
significa duas letras consecutivas em algum ponto da palavra. - Essas ocorrências podem ser sobrepostas. Exemplo: a palavra
tem duas ocorrências de : posições e . - Exemplos para fixar:
contém duas vezes? Sim, porque a parte central dá duas ocorrências sobrepostas.
contém uma vez (apenas no final) → rejeitar.
contém uma vez no começo → rejeitar.
contém duas vezes → aceitar.
É crucial que o autômato consiga:
- detectar quando aparece uma
e lembrar que ela pode formar uma com a próxima ; - contar até duas ocorrências (apenas distinguir 0, 1 e “já vi pelo menos 2”);
- lidar com sobreposição (por exemplo, ao ver
e em seguida outra , isso pode imediatamente formar nova ).
Passo 3
Ideia do método (sem formalizar o autômato ainda): usamos estados que codificam duas informações essenciais:
- Quantas ocorrências de
já foram encontradas: , ou . - Se o último símbolo lido foi uma
(ou não), porque uma pendente pode, com a próxima , formar uma nova ocorrência.
Assim, vamos construir estados que combinam “contagem parcial” e "se o último caractere foi
". Quando a contagem chega a
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):
-
: estado inicial. Ainda não vimos nenhuma ocorrência de e o último símbolo lido não é uma (ou ainda não lemos nada). -
: não vimos nenhuma ocorrência completa de ainda, mas o último símbolo lido foi uma (ou seja, temos uma “pendente” que pode formar um se vier outra ). -
: já vimos exatamente uma ocorrência de e o último símbolo lido não é uma . -
: já vimos exatamente uma ocorrência de e o último símbolo lido foi uma (ou seja, após a primeira ocorrência temos uma que pode iniciar a segunda ocorrência). -
: já vimos pelo menos duas ocorrências de . Estado aceitante e que permanece aceitante com qualquer continuação (sink aceitante).
Comentário rápido sobre sobreposição: ao estar em
(uma
pendente, zero ocorrências), ler
forma imediatamente uma ocorrência e o último símbolo continua sendo
, então devemos transitar para um estado que represente "uma ocorrência, último símbolo
" — esse é exatamente
. Isso permite contar ocorrências sobrepostas corretamente.
Passo 5
Agora construímos as transições, explicando cada caso:
Transições a partir de
(nenhuma ocorrência, último não-a):
- ler
: passo para (agora temos uma pendente). - ler
: permaneço em (a leitura de não cria e não deixa uma pendente).
Transições a partir de
(nenhuma ocorrência, último foi
):
- ler
: isso forma uma ocorrência de . Contagem passa de 0 para 1; o último símbolo é , então vamos para (uma ocorrência, último ). - ler
: a pendente é “perdida” (não forma ), voltamos para .
Transições a partir de
(já vimos 1 ocorrência, último não-a):
- ler
: vai para (mantemos 1 ocorrência, mas agora há uma pendente para possivelmente formar a segunda). - ler
: permaneço em (continua 1 ocorrência, último não-a).
Transições a partir de
(já vimos 1 ocorrência, último foi
):
- ler
: forma a segunda ocorrência (pelo menos duas ocorrências agora), vamos para (estado aceitante). - ler
: a pendente se perde; continuo com 1 ocorrência e último não-a → .
Transições a partir de
(pelo menos 2 ocorrências):
- ler
ou : permaneço em (já aceitei; é um sink aceitante).
Essas regras cobrem todos os casos e tratam sobreposições corretamente (por exemplo, sequência
:
, aceitação).
Passo 6
Formalizando o AFD como uma 5-tupla
:
- Conjunto de estados:
- Alfabeto:
- Estado inicial:
- Conjunto de estados finais:
- Função de transição
(escrita explicitamente):
Passo 7
Verificação por exemplos rápidos para ganhar confiança:
-
: → aceito (tem duas ocorrências: posições (1,2) e (2,3)). -
: → termina em , não aceito (só uma ocorrência). -
: percorre e chega a quando a segunda ocorrência aparece → aceito.
Resumo intuitivo: os estados guardam “quantas ocorrências de
já vi (0,1,>=2)” e "se o último símbolo foi
". Isso é suficiente para reconhecer exatamente as palavras que têm pelo menos duas ocorrências de
.