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

Passo 1

O que o enunciado pede:
  • Construir um autômato finito não determinístico (AFN) que reconheça todas as palavras w sobre o alfabeto \{a,b\} tais que w contém a substring “aa” ou contém a substring “bb”.
Informações dadas:
  • Alfabeto: \{a,b\}.
  • Palavra deve ter, em algum lugar, duas letras iguais consecutivas: “aa” ou “bb”.
  • Queremos um AFN que aceite exatamente essas palavras.

Passo 2

Ideia geral (em palavras simples): queremos um autômato que detecte a ocorrência de “aa” ou de “bb” em qualquer posição da palavra. Uma maneira natural é:
  • Ficar no estado inicial enquanto ainda não vimos nada interessante.
  • Ao ver um a pensar “ok, pode começar uma ocorrência de ‘aa’”: seguir uma transição que lembra que vimos um a.
  • Se depois vier outro a e estávamos nesse estado, aceitamos.
  • O mesmo para b com outro ramo que detecta “bb”.
  • Para não perder a capacidade de começar a buscar em qualquer posição, o estado inicial precisa permitir que, ao ler uma letra, se mantenha pronto para novos começos enquanto também abre a possibilidade de começar a sequência que leva à aceitação. Essa “dupla possibilidade” é exatamente o que o AFN (não-determinismo) permite.

Passo 3

Breve explicação didática sobre AFN (sem jargão pesado):
  • Um AFN é definido por (Q,\Sigma,\delta,q_0,F) onde: Qé o conjunto de estados, \Sigmaé o alfabeto, \deltaé a função de transição que pode dar um conjunto de estados (não apenas um), q_0é o estado inicial, e Fé o conjunto de estados finais (de aceitação).
  • O AFN aceita uma palavra se existe pelo menos uma sequência de escolhas (uma “ramificação”) que consome a palavra e termina em um estado final.
  • Usaremos essa capacidade: ao ler uma letra em q_0 o AFN pode tanto “ignorar” (ficar pronto para tentar em outra posição) quanto “começar a testar” se essa letra é o início de “aa” ou de “bb”.

Passo 4

Construção passo a passo (intuição dos estados):
  • Estado q_0: estado inicial — ainda não vimos a dupla ou estamos prontos para começar a buscar em qualquer posição.
  • Estado q_1: significa "acabamos de ver um a e estamos esperando possivelmente outro a".
  • Estado q_2: estado de aceitação para a ocorrência de “aa” (já vimos “aa”).
  • Estado q_3: significa "acabamos de ver um b e estamos esperando possivelmente outro b".
  • Estado q_4: estado de aceitação para a ocorrência de “bb” (já vimos “bb”).
Comportamento que queremos:
  • Em q_0 ao ler a devemos poder (i) permanecer em q_0 (para continuar procurando adiante) e (ii) ir para q_1 (começar a tentar formar “aa”). Em AFN isso é \delta(q_0,a)=\{q_0,q_1\}.
  • De forma análoga, \delta(q_0,b)=\{q_0,q_3\}.
  • Em q_1 só nos interessa um segundo a: \delta(q_1,a)=\{q_2\}. Se vier b a partir de q_1 esse caminho particular falha (nenhuma transição a partir de q_1 com b), mas como ainda havia a opção de ter permanecido em q_0 no passo anterior, o AFN como um todo não perde a capacidade de continuar a leitura — essa é a mágica do não-determinismo.
  • Em q_3 análogo: \delta(q_3,b)=\{q_4\}.
  • Uma vez que alcançamos q_2 (aceitação por ter visto “aa”) queremos permanecer aceitando o restante da palavra: então em q_2 colocamos laços em a e b (ou seja, \delta(q_2,a)=\{q_2\} e \delta(q_2,b)=\{q_2\}). O mesmo para q_4.
  • Conclusão: esses estados e transições capturam exatamente “contém ‘aa’ ou contém ‘bb’”.

Passo 5

Escrevendo a função de transição com precisão (cada caso):
\delta(q_0,a)=\{q_0,q_1\},\qquad \delta(q_0,b)=\{q_0,q_3\},
\delta(q_1,a)=\{q_2\},\qquad \delta(q_1,b)=\varnothing,
\delta(q_3,b)=\{q_4\},\qquad \delta(q_3,a)=\varnothing,
\delta(q_2,a)=\{q_2\},\qquad \delta(q_2,b)=\{q_2\},
\delta(q_4,a)=\{q_4\},\qquad \delta(q_4,b)=\{q_4\}.

Passo 6

Um exemplo concreto para ver como o AFN aceita:
  • Considere a palavra w= “babba”.
  • Leitura passo a passo (mostro uma ramificação que aceita):
    • No primeiro símbolo b: a partir de q_0 o AFN pode tanto permanecer em q_0 quanto ir para q_3. Suponha que uma ramificação escolhe ir para q_3 (esta ramificação lembra que começamos um possível “bb”).
    • No segundo símbolo a: de q_3 não há transição por a, então essa ramificação morre; mas outra ramificação que ficou em q_0 continuou (pois \delta(q_0,b) também continha q_0). Seguindo a ramificação que ficou em q_0, ao ver o segundo símbolo a ela pode ir para q_1 (começando possível “aa”) ou ficar em q_0.
    • No terceiro símbolo b: ramificações em q_0 consomem b e ainda podem tentar ir para q_3 etc.
    • No quarto símbolo b: existe uma ramificação que estava em q_3 no terceiro passo (porque ao ver o terceiro símbolo b a partir de q_0 essa ramificação foi criada), e então ao ler o quarto b essa ramificação faz \delta(q_3,b)=\{q_4\} e alcança q_4, que é estado de aceitação. Depois q_4 aceita o último símbolo a por seu laço e a palavra é aceita.
  • Moral: o AFN consegue “escolher” onde começa a verificar uma dupla e, se existe alguma dupla “aa” ou “bb” na palavra, alguma ramificação irá encontrá-la e terminará em um estado final.

Passo 7

Justificativa formal curta de correção:
  • Se w contém “aa” em alguma posição, então existe uma posição onde se lê um a seguido de outro a. Ao chegar nesse primeiro a o AFN tem a opção de ir para q_1; ao ler o segundo a faz q_1\overset{a}{\to}q_2 e então termina em q_2 (aceita). Análogo para “bb” com q_3 e q_4.
  • Se o AFN aceita w, então alguma ramificação chegou a q_2 ou q_4. Para chegar a q_2 foi preciso realizar uma transição q_1\overset{a}{\to}q_2, o que implica que em w apareceu “aa” consecutivo naquela posição; análogo para q_4 e “bb”. Portanto o AFN aceita exatamente as palavras que contêm “aa” ou “bb”.

Passo 8

Vibrações finais (um empurrãozinho motivacional): esse AFN é bem padrão para linguagens do tipo “contém a substring X”. Em prova, desenhe os estados com os significados acima (inicial, esperando 2ª letra, aceitação) e explique rápida e claramente que o não-determinismo permite tentar começar a buscar a substring em qualquer posição — isso costuma agradar quem corrige 😃

Resposta

N=(Q,\Sigma,\delta,q_0,F)
Q=\{q_0,q_1,q_2,q_3,q_4\},\quad \Sigma=\{a,b\},\quad q_0\text{ é o estado inicial},\quad F=\{q_2,q_4\},é
\delta(q_0,a)=\{q_0,q_1\},\qquad \delta(q_0,b)=\{q_0,q_3\},
\delta(q_1,a)=\{q_2\},\qquad \delta(q_1,b)=\varnothing,
\delta(q_3,b)=\{q_4\},\qquad \delta(q_3,a)=\varnothing,
\delta(q_2,a)=\{q_2\},\qquad \delta(q_2,b)=\{q_2\},
\delta(q_4,a)=\{q_4\},\qquad \delta(q_4,b)=\{q_4\}.

Exercícios relacionados