Construa AFNs para reconhecer as seguintes linguagens:
onde todo “a” é seguido por “b” ou “ab”
.
onde todo “a” é seguido por “b” ou “ab” .
Passo 1
O enunciado pede: construir autômatos finitos não-determinísticos (AFNs) que reconheçam a linguagem dos cadeias
sobre o alfabeto
tais que "todo
em
é seguido por
ou por
".\n
Informações relevantes dadas pelo enunciado:
Informações relevantes dadas pelo enunciado:
A condição sobre as cadeias é: cada ocorrência da letra
deve obedecer a uma das duas opções (imediatamente após ela):
Observações que já podemos listar (sem ainda resolver):
- A cadeia vazia
tem zero ocorrências de , então deve ser aceita (a condição é satisfeita vacuamente). - Uma cadeia que termine em
não pode satisfazer a condição (pois um final não é seguido por nada). - Precisamos garantir que nenhuma ocorrência de
viole a regra acima.
Passo 2
Interpretação formal e simplificação da condição (a parte teórica que usamos para projetar o AFN).
Queremos caracterizar exatamente quais sequências de
e
são permitidas. Tome uma ocorrência de
em posição
da cadeia
. As duas opções do enunciado significam:
- opção 1:
(o próximo símbolo é ); - opção 2:
e (os próximos dois símbolos são ).
Dessas condições segue uma propriedade equivalente e mais simples de usar para construir autômatos:
- Não pode haver um
como último símbolo da cadeia (pois ele não seria seguido por nada). - Não pode haver três
s consecutivos. Explicação: se existir um trecho então a primeira tem e , logo não é nem seguida por nem por ; portanto tal cadeia é proibida.
Mostrando a equivalência (intuição):
- Se toda
é seguida por ou por , então obviamente a cadeia não termina em . Além disso, se houvesse em algum lugar, a primeira da tripla teria as próximas duas letras iguais a , não a , contradizendo a regra. Logo não há . - Reciprocamente, se a cadeia não termina em
e não contém , então para qualquer que apareça: ou o próximo símbolo é (ok), ou o próximo símbolo é ; nesse caso o símbolo após esse não pode ser (porque proibimos ), então deve ser , e a condição "seguido por " é satisfeita.
Portanto podemos projetar um autômato que vigie apenas:
- quantas
s consecutivas foram lidas (0,1 ou 2), - proíba a leitura de uma terceira
consecutiva, - aceite apenas quando não estamos no "estado que indica que a última letra lida foi
" (ou seja, aceite apenas se a cadeia não terminar em ).
Passo 3
Estratégia de construção do AFN (ideia prática):
Vamos usar estados que representam quantas
s consecutivas acabamos de ler (0, 1 ou 2). O autômato deve:
- começar em um estado que indica “não há
pendente” (também aceita ); - ao ler
avançar para o estado “uma vista”; - ao ler mais um
ir para “duas s consecutivas”; - ao ler uma terceira
ir para um estado de morte (cadeia rejeitada); - ao ler
em qualquer desses estados voltar para o estado que indica “nenhuma pendente” (pois um resolve as condições das s anteriores); - aceitar exatamente quando a leitura terminou num estado que não indica que a última letra foi
, isto é, aceitar apenas se a cadeia não termina em .
Este projeto é determinístico, portanto é também um AFN válido (todo DFA é um caso particular de NFA). É simples e direto de implementar.
Passo 4
Definição formal do AFN — descrição dos estados e semântica:
- Conjunto de estados:
. -
: estado inicial e de aceitação. Significa “a cadeia lida até agora ou terminou com (ou é vazia) — nenhuma pendente”. -
: significa "a última símbolo lido foi (uma pendente) — estamos esperando garantir que essa é seguida por ou por ". -
: significa “as duas últimas letras lidas foram (duas s consecutivas) — ainda falta um logo em seguida”. -
: estado morto (quando apareceu ou outra violação). Não é de aceitação.
-
- Estado inicial:
. - Estados de aceitação:
(apenas , porque queremos rejeitar cadeias que terminam com , isto é, que deixam o autômato em ou ao final). - Transições (função
; como AFN usamos conjuntos como imagens, aqui todas as imagens são conjuntos unitários para deixar claro, mas é aceitável que seja determinístico):
Aqui
está escrita como conjunto de estados (padrão de AFN). O estado
simplesmente captura qualquer violação (por exemplo a leitura de uma terceira
consecutiva).]
Passo 5
Explicação passo a passo de por que o autômato reconhece exatamente a linguagem pedida (prova de correção, com exemplos):
- Cadeia vazia
: o autômato permanece em (inicial), que é de aceitação, logo aceita. Isso condiz com a condição (vazia é aceita). - Se a cadeia terminar com
: sempre que um é lido voltamos a . Assim a leitura termina em e é aceita — isto corresponde ao fato de que não existe final sem símbolo seguinte. - Caso haja um
isolado seguido imediatamente por : leitura significa ir . O “satisfez” a exigência do . - Caso haja duas
s seguidas e depois um : corresponde a . A primeira foi seguida por , a segunda por . - Se aparecer uma terceira
seguida ( ), então e o autômato vai para e fica lá; não é de aceitação, então a cadeia é rejeitada. Isso impede a ocorrência de . - Se a cadeia terminar em
(ou seja, terminar em estado ou ), esses estados não são de aceitação e, portanto, a cadeia é rejeitada — isso corresponde à exigência de que nenhum fique sem símbolos seguintes que o satisfaçam. - Assim, qualquer cadeia aceita pelo autômato satisfaz simultaneamente "não termina em
" e "não contém ", e por Passo 2 isso é equivalente à condição original do enunciado. Recíprocamente, se uma cadeia satisfaz a condição original, o autômato nunca vai para e terminará em , logo será aceita.
Passo 6
Exemplos de execução (mostrando as transições para fixar o método — você consegue reproduzir isso na prova):
- Aceita:
.
- Aceita:
.
- Aceita:
? Não — vamos verificar: termina em , então deverá ser rejeitado.
Isso está correto: o último
não é seguido por nada, então a cadeia viola a condição.
- Rejeita:
.
Resposta
e função de transição
dada por