Construa AFNs para reconhecer as seguintes linguagens:
contém ambas as substring “aa” e “bb” ou nenhuma delas
.
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 linguagem é
- Objetivo: construir um AFN (autômato finito não determinístico, com
-transições permitidas) que reconheça exatamente . - Informações úteis explícitas extraídas do enunciado:
- Devemos aceitar cadeias que têm tanto “aa” quanto “bb” (em qualquer ordem e possivelmente sobrepostas).
- Devemos também aceitar cadeias que não contenham nem “aa” nem “bb” (ou seja, não têm duas letras iguais consecutivas).
- 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
.
- É natural dividir
em duas partes disjuntas: onde
- Construiremos dois AFNs (um para cada parte) e então faremos a união dos dois AFNs com uma
-transição do estado inicial para os inícios dos dois sub-autômatos. Em AFNs a união por é 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
: 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
e vem outro , entramos em estado de rejeição; se vem , atualizamos e seguimos. -
Definição do AFN (vai ser na prática determinístico, mas um AFN também o aceita):Estados:
. -
= estado inicial (também de aceitação). Representa “inicio, nenhuma letra anterior”. -
= último símbolo lido foi (aceitação). -
= último símbolo lido foi (aceitação). -
= já apareceu “aa” ou “bb” (estado de rejeição, não aceitante).
Alfabeto:. Transições (descritivas):-
. -
. -
(dupla → rejeitar). -
. -
(dupla → rejeitar). -
. -
. -
.
Estado inicial:.
Estados de aceitação:. -
-
Observação e exemplo prático:
- A cadeia vazia
fica em → aceita. - “a” vai
→ aceita. - “ababa” percorre
→ aceito. - “aaa” entra em
ao ler o segundo → rejeitado.
- A cadeia vazia
Passo 4
Construção do AFN que reconhece
: 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
).
-
Vamos descrever o ramo que procura “aa” antes de “bb” (ramo simétrico fará o inverso).Estados do ramo “aa então bb”:
. -
: estado de varredura inicial do ramo (lê qualquer prefixo até decidir começar a testar por um ‘a’ inicial de “aa”). Terá loop em . -
: viu um que pode ser o começo de “aa” (está esperando o próximo símbolo). -
: já encontrou “aa” (agora só procura “bb” depois). -
: viu um potencial início de “bb” (após já ter achado “aa”). -
: já encontrou “aa” e “bb” (estado de aceitação), com loop em para consumir o resto.
Transições essenciais (ramo “aa→bb”):-
contém . Explicação: ao ler podemos permanecer varrendo ( ) ou iniciar uma tentativa de formar “aa” (ir para ). -
. -
(achou “aa”). -
(falhou tentativa de “aa”, volta a varrer). -
e . Explicação: após ter “aa”, continuamos varrendo (ficando em ), mas um também pode iniciar a tentativa de formar “bb” (vai para ). -
(achou “bb” após “aa”). -
e .
-
-
Ramo “bb então aa” é simétrico; usamos estados:
com a mesma ideia trocando : -
contém , . -
, . -
, . -
. -
, .
-
-
Observações sobre não-determinismo usado:
- Em
a transição é a “tentativa” de começar a reconhecer “aa”. Caso a tentativa não funcione, outra cópia do ramo que ficou em continua varrendo; por isso colocamos também 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.
- Em
Passo 5
Combinação final: união do AFN de
com o AFN de
.
- Crie um novo estado inicial
. - Coloque
-transições de para os três pontos iniciais das submáquinas: -
para (início do AFN que aceita “nenhuma dupla”), -
para (início do ramo “aa→bb”), -
para (início do ramo “bb→aa”).
-
- Estados de aceitação do autômato global são:
- todos os estados aceitantes do AFN “nenhuma dupla”:
, - os estados aceitantes dos ramos que já encontraram as duas substrings:
.
- todos os estados aceitantes do AFN “nenhuma dupla”:
- O autômato resultante é um AFN com
-transições que reconhece a união das duas partes, logo reconhece exatamente .
Passo 6
Verificação com exemplos e comentários finais (práticos, para você checar na prova).
- Exemplos:
-
: vai por -transição para e aceita (nenhuma dupla) → aceita. - “ababa”: nunca tem “aa” nem “bb”, caminho por
→ aceita (pelo ramo ). - “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
vai para . 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
-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 , estado inicial e conjunto de estados finais (como fizemos conceitualmente).
Resposta
Conjunto de estados (descrição compacta):
.
Alfabeto:
.
Estado inicial:
.
Transições (lista essencial;
indica
-transição):
-
União inicial:
-
.
-
-
Subautômato
: -
. -
. -
. -
. -
. -
. -
. -
.
-
-
Ramo
(“aa” então “bb”): -
. -
. -
. -
. -
. -
. -
. -
. -
.
-
-
Ramo
(“bb” então “aa”): -
. -
. -
. -
. -
. -
. -
. -
. -
.
-
Estados de aceitação:
Esse AFN (com as
-transições indicadas) reconhece exatamente a linguagem pedida: aceita cadeias que têm tanto “aa” quanto “bb” (pelos estados
ou
) e aceita também cadeias que não têm nem “aa” nem “bb” (pelos estados
).