Construa AFNs para reconhecer as seguintes linguagens:
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
sobre o alfabeto tais que contém a substring “aa” ou contém a substring “bb”.
Informações dadas:
- Alfabeto:
. - 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
pensar “ok, pode começar uma ocorrência de ‘aa’”: seguir uma transição que lembra que vimos um . - Se depois vier outro
e estávamos nesse estado, aceitamos. - O mesmo para
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
onde: é o conjunto de estados, é o alfabeto, é a função de transição que pode dar um conjunto de estados (não apenas um), é o estado inicial, e é 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
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
: estado inicial — ainda não vimos a dupla ou estamos prontos para começar a buscar em qualquer posição. - Estado
: significa "acabamos de ver um e estamos esperando possivelmente outro ". - Estado
: estado de aceitação para a ocorrência de “aa” (já vimos “aa”). - Estado
: significa "acabamos de ver um e estamos esperando possivelmente outro ". - Estado
: estado de aceitação para a ocorrência de “bb” (já vimos “bb”).
Comportamento que queremos:
- Em
ao ler devemos poder (i) permanecer em (para continuar procurando adiante) e (ii) ir para (começar a tentar formar “aa”). Em AFN isso é . - De forma análoga,
. - Em
só nos interessa um segundo : . Se vier a partir de esse caminho particular falha (nenhuma transição a partir de com ), mas como ainda havia a opção de ter permanecido em 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
análogo: . - Uma vez que alcançamos
(aceitação por ter visto “aa”) queremos permanecer aceitando o restante da palavra: então em colocamos laços em e (ou seja, e ). O mesmo para . - 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):
Passo 6
Um exemplo concreto para ver como o AFN aceita:
- Considere a palavra
“babba”. - Leitura passo a passo (mostro uma ramificação que aceita):
- No primeiro símbolo
: a partir de o AFN pode tanto permanecer em quanto ir para . Suponha que uma ramificação escolhe ir para (esta ramificação lembra que começamos um possível “bb”). - No segundo símbolo
: de não há transição por , então essa ramificação morre; mas outra ramificação que ficou em continuou (pois também continha ). Seguindo a ramificação que ficou em , ao ver o segundo símbolo ela pode ir para (começando possível “aa”) ou ficar em . - No terceiro símbolo
: ramificações em consomem e ainda podem tentar ir para etc. - No quarto símbolo
: existe uma ramificação que estava em no terceiro passo (porque ao ver o terceiro símbolo a partir de essa ramificação foi criada), e então ao ler o quarto essa ramificação faz e alcança , que é estado de aceitação. Depois aceita o último símbolo por seu laço e a palavra é aceita.
- No primeiro símbolo
- 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
contém “aa” em alguma posição, então existe uma posição onde se lê um seguido de outro . Ao chegar nesse primeiro o AFN tem a opção de ir para ; ao ler o segundo faz e então termina em (aceita). Análogo para “bb” com e . - Se o AFN aceita
, então alguma ramificação chegou a ou . Para chegar a foi preciso realizar uma transição , o que implica que em apareceu “aa” consecutivo naquela posição; análogo para 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 😃