Construa AFNs para reconhecer as seguintes linguagens:
{\mathrm{w} \in{\mathrm{a}, \mathrm{b}} \mid \mathrm{w} contém ambas as substring “aa” e “bb” ou nenhuma delas }.

Passo 1

O que o enunciado pede e o que já foi dado.
  • O alfabeto é \{a,b\}.
  • A linguagem é L=\{\,w\in\{a,b\}^*\mid \text{\(w\) contém ambas as substrings "aa" e "bb" ou nenhuma delas}\,\}.é
  • Objetivo: construir um AFN (autômato finito não determinístico, com \epsilon-transições permitidas) que reconheça exatamente L.
  • Informações úteis explícitas extraídas do enunciado:
    1. Devemos aceitar cadeias que têm tanto “aa” quanto “bb” (em qualquer ordem e possivelmente sobrepostas).
    2. Devemos também aceitar cadeias que não contenham nem “aa” nem “bb” (ou seja, não têm duas letras iguais consecutivas).
    3. Devemos rejeitar cadeias que tenham exatamente uma das substrings “aa” ou “bb” (por exemplo, “aaa” contém “aa” mas não “bb” → rejeitar).

Passo 2

Ideia geral de construção (sem ainda construir): decomposição em duas partes e união por \epsilon.
  • É natural dividir L em duas partes disjuntas: L = L_{\text{both}}\\ \cup\\ L_{\text{none}},onde L_{\text{both}}=\{w \mid w \text{ contém "aa" e contém "bb"}\},éé
L_{\text{none}}=\{w \mid w \text{ contém nem "aa" nem "bb"}\}.é
  • Construiremos dois AFNs (um para cada parte) e então faremos a união dos dois AFNs com uma \epsilon-transição do estado inicial para os inícios dos dois sub-autômatos. Em AFNs a união por \epsilon é direta e simples.
  • Por que dividir assim? Porque é mais simples detectar “nenhuma dupla letra” (estado lembrando o último símbolo) e é simples, com não-determinismo, detectar “tem aa e tem bb” explorando duas ramificações que procuram as substrings em ordens diferentes (primeiro aa depois bb, OU primeiro bb depois aa).

Passo 3

Construção do AFN que reconhece L_{\text{none}}: cadeias sem “aa” nem “bb” (ou seja, sem duas letras iguais consecutivas).
  • Ideia didática: para garantir que não apareça duas letras iguais seguidas, basta lembrar qual foi a última letra lida (ou que ainda não lemos nada). Se a última foi a e vem outro a, entramos em estado de rejeição; se vem b, atualizamos e seguimos.
  • Definição do AFN (vai ser na prática determinístico, mas um AFN também o aceita):
    Estados: \{N_0,N_a,N_b,N_{\text{dead}}\}.
    • \,N_0 = estado inicial (também de aceitação). Representa “inicio, nenhuma letra anterior”.
    • \,N_a = último símbolo lido foi a (aceitação).
    • \,N_b = último símbolo lido foi b (aceitação).
    • \,N_{\text{dead}} = já apareceu “aa” ou “bb” (estado de rejeição, não aceitante).
    Alfabeto: \{a,b\}.
    Transições (descritivas):
    • \delta(N_0,a)=\{N_a\}.
    • \delta(N_0,b)=\{N_b\}.
    • \delta(N_a,a)=\{N_{\text{dead}}\} (dupla aa → rejeitar).
    • \delta(N_a,b)=\{N_b\}.
    • \delta(N_b,b)=\{N_{\text{dead}}\} (dupla bb → rejeitar).
    • \delta(N_b,a)=\{N_a\}.
    • \delta(N_{\text{dead}},a)=\{N_{\text{dead}}\}.
    • \delta(N_{\text{dead}},b)=\{N_{\text{dead}}\}.
    Estado inicial: \,N_0.
    Estados de aceitação: \{N_0,N_a,N_b\}.
  • Observação e exemplo prático:
    • A cadeia vazia \epsilon fica em N_0 → aceita.
    • “a” vai N_0 \xrightarrow{a} N_a → aceita.
    • “ababa” percorre N_0\xrightarrow{a}N_a\xrightarrow{b}N_b\xrightarrow{a}N_a\cdots → aceito.
    • “aaa” entra em N_{\text{dead}} ao ler o segundo a → rejeitado.

Passo 4

Construção do AFN que reconhece L_{\text{both}}: cadeias que contêm tanto “aa” quanto “bb” (em qualquer ordem).
  • Estratégia didática: usar não-determinismo para escolher qual substring procurar primeiro:
    • Ramificação A: procurar “aa” em alguma posição, depois procurar “bb” depois disso.
    • Ramificação B: procurar “bb” em alguma posição, depois procurar “aa” depois disso.
    • Cada ramo é um pequeno AFN que primeiro “varre” (aceita qualquer prefixo), detecta a primeira substring, e então varre o que vier procurando a segunda substring; quando ambas foram encontradas, chegamos a um estado de aceitação que consome o resto da cadeia (loop em a,b).
  • Vamos descrever o ramo que procura “aa” antes de “bb” (ramo simétrico fará o inverso).
    Estados do ramo “aa então bb”:
    \{A_0,A_1,A_{aa},A_{b},A_{\text{acc}}\}.
    • A_0: estado de varredura inicial do ramo (lê qualquer prefixo até decidir começar a testar por um ‘a’ inicial de “aa”). Terá loop em a,b.
    • A_1: viu um a que pode ser o começo de “aa” (está esperando o próximo símbolo).
    • A_{aa}: já encontrou “aa” (agora só procura “bb” depois).
    • A_{b}: viu um b potencial início de “bb” (após já ter achado “aa”).
    • A_{\text{acc}}: já encontrou “aa” e “bb” (estado de aceitação), com loop em a,b para consumir o resto.
    Transições essenciais (ramo “aa→bb”):
    • \delta(A_0,a) contém \{A_0,A_1\}. Explicação: ao ler a podemos permanecer varrendo ( A_0) ou iniciar uma tentativa de formar “aa” (ir para A_1).
    • \delta(A_0,b)=\{A_0\}.
    • \delta(A_1,a)=\{A_{aa}\} (achou “aa”).
    • \delta(A_1,b)=\{A_0\} (falhou tentativa de “aa”, volta a varrer).
    • \delta(A_{aa},a)=\{A_{aa}\} e \delta(A_{aa},b)=\{A_{aa},A_{b}\}. Explicação: após ter “aa”, continuamos varrendo (ficando em A_{aa}), mas um b também pode iniciar a tentativa de formar “bb” (vai para A_{b}).
    • \delta(A_{b},b)=\{A_{\text{acc}}\} (achou “bb” após “aa”).
    • \delta(A_{\text{acc}},a)=\{A_{\text{acc}}\} e \delta(A_{\text{acc}},b)=\{A_{\text{acc}}\}.
  • Ramo “bb então aa” é simétrico; usamos estados:
    \{B_0,B_1,B_{bb},B_{a},B_{\text{acc}}\} com a mesma ideia trocando a\leftrightarrow b:
    • \delta(B_0,b) contém \{B_0,B_1\}, \delta(B_0,a)=\{B_0\}.
    • \delta(B_1,b)=\{B_{bb}\}, \delta(B_1,a)=\{B_0\}.
    • \delta(B_{bb},b)=\{B_{bb}\}, \delta(B_{bb},a)=\{B_{bb},B_{a}\}.
    • \delta(B_{a},a)=\{B_{\text{acc}}\}.
    • \delta(B_{\text{acc}},a)=\{B_{\text{acc}}\}, \delta(B_{\text{acc}},b)=\{B_{\text{acc}}\}.
  • Observações sobre não-determinismo usado:
    • Em A_0 a transição \delta(A_0,a)\ni A_1 é a “tentativa” de começar a reconhecer “aa”. Caso a tentativa não funcione, outra cópia do ramo que ficou em A_0 continua varrendo; por isso colocamos também A_0 entre as imagens, dando flexibilidade.
    • Assim podemos encontrar “aa” e “bb” em qualquer lugar e em qualquer ordem: se estiver na cadeia “b…aa…bb…” o ramo “aa→bb” terá sucesso; se for “a…bb…aa…” o ramo “bb→aa” terá sucesso.

Passo 5

Combinação final: união do AFN de L_{\text{none}} com o AFN de L_{\text{both}}.
  • Crie um novo estado inicial S.
  • Coloque \epsilon-transições de S para os três pontos iniciais das submáquinas:
    • \epsilon para N_0 (início do AFN que aceita “nenhuma dupla”),
    • \epsilon para A_0 (início do ramo “aa→bb”),
    • \epsilon para B_0 (início do ramo “bb→aa”).
  • Estados de aceitação do autômato global são:
    • todos os estados aceitantes do AFN “nenhuma dupla”: \{N_0,N_a,N_b\},
    • os estados aceitantes dos ramos que já encontraram as duas substrings: \{A_{\text{acc}},B_{\text{acc}}\}.
  • O autômato resultante é um AFN com \epsilon-transições que reconhece a união das duas partes, logo reconhece exatamente L.

Passo 6

Verificação com exemplos e comentários finais (práticos, para você checar na prova).
  • Exemplos:
    • \epsilon: vai por \epsilon-transição para N_0 e aceita (nenhuma dupla) → aceita.
    • “ababa”: nunca tem “aa” nem “bb”, caminho por N_0\to N_a\to N_b\to\cdots → aceita (pelo ramo L_{\text{none}}).
    • “aabb”: tem “aa” (posição 1–2) e “bb” (posição 3–4); existe caminho no ramo “aa→bb” que aceita → aceita.
    • “aaa”: contém “aa” mas não “bb”. Nos ramos de “both” não existe detector de “bb”, e no ramo “none” é rejeitado porque ao ler segundo a vai para N_{\text{dead}}. Logo cadeia rejeitada → correto.
  • Observação de projeto: o AFN que propusemos é bastante direto de desenhar como diagrama. Em prova, desenhe um estado inicial com 3 \epsilon-setas para as três submáquinas e, para cada submáquina, desenhe os estados e transições conforme descrito. Se quiser formalizar, liste o conjunto de estados, função de transição \delta, estado inicial e conjunto de estados finais (como fizemos conceitualmente).

Resposta

Conjunto de estados (descrição compacta): \{S\}\cup\{N_0,N_a,N_b,N_{\text{dead}}\}\cup\{A_0,A_1,A_{aa},A_{b},A_{\text{acc}}\}\cup\{B_0,B_1,B_{bb},B_{a},B_{\text{acc}}\}.
Alfabeto: \{a,b\}.
Estado inicial: \,S.
Transições (lista essencial; \epsilon indica \epsilon-transição):
  • União inicial:
    • \delta(S,\epsilon)=\{N_0,A_0,B_0\}.
  • Subautômato L_{\text{none}}:
    • \delta(N_0,a)=\{N_a\}.
    • \delta(N_0,b)=\{N_b\}.
    • \delta(N_a,a)=\{N_{\text{dead}}\}.
    • \delta(N_a,b)=\{N_b\}.
    • \delta(N_b,b)=\{N_{\text{dead}}\}.
    • \delta(N_b,a)=\{N_a\}.
    • \delta(N_{\text{dead}},a)=\{N_{\text{dead}}\}.
    • \delta(N_{\text{dead}},b)=\{N_{\text{dead}}\}.
  • Ramo A (“aa” então “bb”):
    • \delta(A_0,a)=\{A_0,A_1\}.
    • \delta(A_0,b)=\{A_0\}.
    • \delta(A_1,a)=\{A_{aa}\}.
    • \delta(A_1,b)=\{A_0\}.
    • \delta(A_{aa},a)=\{A_{aa}\}.
    • \delta(A_{aa},b)=\{A_{aa},A_{b}\}.
    • \delta(A_{b},b)=\{A_{\text{acc}}\}.
    • \delta(A_{\text{acc}},a)=\{A_{\text{acc}}\}.
    • \delta(A_{\text{acc}},b)=\{A_{\text{acc}}\}.
  • Ramo B (“bb” então “aa”):
    • \delta(B_0,b)=\{B_0,B_1\}.
    • \delta(B_0,a)=\{B_0\}.
    • \delta(B_1,b)=\{B_{bb}\}.
    • \delta(B_1,a)=\{B_0\}.
    • \delta(B_{bb},b)=\{B_{bb}\}.
    • \delta(B_{bb},a)=\{B_{bb},B_{a}\}.
    • \delta(B_{a},a)=\{B_{\text{acc}}\}.
    • \delta(B_{\text{acc}},a)=\{B_{\text{acc}}\}.
    • \delta(B_{\text{acc}},b)=\{B_{\text{acc}}\}.
Estados de aceitação:
F=\{N_0,N_a,N_b,A_{\text{acc}},B_{\text{acc}}\}.
Esse AFN (com as \epsilon-transições indicadas) reconhece exatamente a linguagem pedida: aceita cadeias que têm tanto “aa” quanto “bb” (pelos estados A_{\text{acc}} ou B_{\text{acc}}) e aceita também cadeias que não têm nem “aa” nem “bb” (pelos estados N_0,N_a,N_b).

Exercícios relacionados