Construa AFNs para reconhecer as seguintes linguagens:
{\mathrm{w} \in{\mathrm{a}, \mathrm{b}} \mid 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 w sobre o alfabeto \{a,b\} tais que "todo a em w é seguido por b ou por ab".\n
Informações relevantes dadas pelo enunciado:
\text{alfabeto } \Sigma=\{a,b\}.
A condição sobre as cadeias é: cada ocorrência da letra a deve obedecer a uma das duas opções (imediatamente após ela):
\text{(i) a próxima letra é } b\quad\text{ou}\quad\text{(ii) as próximas duas letras são }ab.óéóã
Observações que já podemos listar (sem ainda resolver):
  • A cadeia vazia \varepsilon tem zero ocorrências de a, então deve ser aceita (a condição é satisfeita vacuamente).
  • Uma cadeia que termine em a não pode satisfazer a condição (pois um a final não é seguido por nada).
  • Precisamos garantir que nenhuma ocorrência de a 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 a e b são permitidas. Tome uma ocorrência de a em posição i da cadeia w. As duas opções do enunciado significam:
  • opção 1: w_{i+1}=b (o próximo símbolo é b);
  • opção 2: w_{i+1}=a e w_{i+2}=b (os próximos dois símbolos são ab).
Dessas condições segue uma propriedade equivalente e mais simples de usar para construir autômatos:
  1. Não pode haver um a como último símbolo da cadeia (pois ele não seria seguido por nada).
  2. Não pode haver três as consecutivos. Explicação: se existir um trecho \,aaa\, então a primeira a tem w_{i+1}=a e w_{i+2}=a, logo não é nem seguida por b nem por ab; portanto tal cadeia é proibida.
Mostrando a equivalência (intuição):
  • Se toda a é seguida por b ou por ab, então obviamente a cadeia não termina em a. Além disso, se houvesse \,aaa\, em algum lugar, a primeira a da tripla teria as próximas duas letras iguais a aa, não a ab, contradizendo a regra. Logo não há \,aaa\,.
  • Reciprocamente, se a cadeia não termina em a e não contém \,aaa\,, então para qualquer a que apareça: ou o próximo símbolo é b (ok), ou o próximo símbolo é a; nesse caso o símbolo após esse a não pode ser a (porque proibimos \,aaa\,), então deve ser b, e a condição "seguido por ab" é satisfeita.
Portanto podemos projetar um autômato que vigie apenas:
  • quantas as consecutivas foram lidas (0,1 ou 2),
  • proíba a leitura de uma terceira a consecutiva,
  • aceite apenas quando não estamos no "estado que indica que a última letra lida foi a" (ou seja, aceite apenas se a cadeia não terminar em a).

Passo 3

Estratégia de construção do AFN (ideia prática):
Vamos usar estados que representam quantas as consecutivas acabamos de ler (0, 1 ou 2). O autômato deve:
  • começar em um estado que indica “não há a pendente” (também aceita \varepsilon);
  • ao ler a avançar para o estado “uma a vista”;
  • ao ler mais um a ir para “duas as consecutivas”;
  • ao ler uma terceira a ir para um estado de morte (cadeia rejeitada);
  • ao ler b em qualquer desses estados voltar para o estado que indica “nenhuma a pendente” (pois um b resolve as condições das as anteriores);
  • aceitar exatamente quando a leitura terminou num estado que não indica que a última letra foi a, isto é, aceitar apenas se a cadeia não termina em a.
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: Q=\{q_0,q_1,q_2,q_d\}.
    • q_0: estado inicial e de aceitação. Significa “a cadeia lida até agora ou terminou com b (ou é vazia) — nenhuma a pendente”.
    • q_1: significa "a última símbolo lido foi a (uma a pendente) — estamos esperando garantir que essa a é seguida por b ou por ab".
    • q_2: significa “as duas últimas letras lidas foram aa (duas as consecutivas) — ainda falta um b logo em seguida”.
    • q_d: estado morto (quando apareceu \,aaa\, ou outra violação). Não é de aceitação.
  • Estado inicial: q_0.
  • Estados de aceitação: F=\{q_0\} (apenas q_0, porque queremos rejeitar cadeias que terminam com a, isto é, que deixam o autômato em q_1 ou q_2 ao final).
  • Transições (função \delta; 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):
\begin{aligned} \delta(q_0,a)&=\{q_1\},\\\ \delta(q_0,b)&=\{q_0\},\\[4pt] \delta(q_1,a)&=\{q_2\},\\\ \delta(q_1,b)&=\{q_0\},\\[4pt] \delta(q_2,a)&=\{q_d\},\\\ \delta(q_2,b)&=\{q_0\},\\[4pt] \delta(q_d,a)&=\{q_d\},\\\ \delta(q_d,b)&=\{q_d\}. \end{aligned}
Aqui \delta está escrita como conjunto de estados (padrão de AFN). O estado q_d simplesmente captura qualquer violação (por exemplo a leitura de uma terceira a 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 \varepsilon: o autômato permanece em q_0 (inicial), que é de aceitação, logo aceita. Isso condiz com a condição (vazia é aceita).
  • Se a cadeia terminar com b: sempre que um b é lido voltamos a q_0. Assim a leitura termina em q_0 e é aceita — isto corresponde ao fato de que não existe a final sem símbolo seguinte.
  • Caso haja um a isolado seguido imediatamente por b: leitura \dots a b \dots significa ir q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_0. O b “satisfez” a exigência do a.
  • Caso haja duas as seguidas e depois um b: \dots a a b \dots corresponde a q_0 \xrightarrow{a} q_1 \xrightarrow{a} q_2 \xrightarrow{b} q_0. A primeira a foi seguida por ab, a segunda por b.
  • Se aparecer uma terceira a seguida ( \,aaa\,), então q_2 \xrightarrow{a} q_d e o autômato vai para q_d e fica lá; q_d não é de aceitação, então a cadeia é rejeitada. Isso impede a ocorrência de \,aaa\,.
  • Se a cadeia terminar em a (ou seja, terminar em estado q_1 ou q_2), esses estados não são de aceitação e, portanto, a cadeia é rejeitada — isso corresponde à exigência de que nenhum a fique sem símbolos seguintes que o satisfaçam.
  • Assim, qualquer cadeia aceita pelo autômato satisfaz simultaneamente "não termina em a" e "não contém \,aaa\,", 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 q_d e terminará em q_0, 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: ab.
q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_0 \quad\text{(fim em }q_0\text{, aceito)}
  • Aceita: aab.
q_0 \xrightarrow{a} q_1 \xrightarrow{a} q_2 \xrightarrow{b} q_0 \quad\text{(aceito)}
  • Aceita: baba ? Não — vamos verificar: baba termina em a, então deverá ser rejeitado.
q_0 \xrightarrow{b} q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_0 \xrightarrow{a} q_1\quad\text{(fim em }q_1\text{, rejeitado)}
Isso está correto: o último a não é seguido por nada, então a cadeia viola a condição.
  • Rejeita: aaa.
q_0 \xrightarrow{a} q_1 \xrightarrow{a} q_2 \xrightarrow{a} q_d \quad\text{(fim em }q_d\text{, rejeitado)}

Resposta

\displaystyle M=(Q,\Sigma,\delta,q_0,F) com
Q=\{q_0,q_1,q_2,q_d\},\qquad \Sigma=\{a,b\},\qquad q_0\text{ inicial},
F=\{q_0\},
e função de transição \delta dada por
\begin{aligned} \delta(q_0,a)&=\{q_1\},&\delta(q_0,b)&=\{q_0\},\\[2pt] \delta(q_1,a)&=\{q_2\},&\delta(q_1,b)&=\{q_0\},\\[2pt] \delta(q_2,a)&=\{q_d\},&\delta(q_2,b)&=\{q_0\},\\[2pt] \delta(q_d,a)&=\{q_d\},&\delta(q_d,b)&=\{q_d\}. \end{aligned}]

Exercícios relacionados