1^{\circ} ) Desenvolva Autômatos Finitos Determinísticos que reconheçam as seguintes linguagens sobre \Sigma=\{\mathrm{a}, \mathrm{b}\} : (cada resposta correta vale 1,0 ponto)
{w \mid o sufixo de w é \mathbf{a a}\}

Passo 1

O enunciado dá a seguinte informação:
  • Alfabeto: \Sigma=\{\mathrm{a},\mathrm{b}\}.
  • Linguagem pedida: o conjunto de todas as palavras w tal que o sufixo de w é \mathrm{aa}; em outras palavras, todas as palavras que terminam com as duas letras \mathrm{a}\mathrm{a}.
O que é pedido:
  • Desenvolver um Autômato Finito Determinístico (AFD) que reconheça exatamente essa linguagem.

Passo 2

Ideia-chave (explicada devagar e com calma):
  • Para decidir se uma palavra termina em \mathrm{aa} basta observar as últimas duas letras lidas. Logo o autômato só precisa “lembrar” até as duas últimas letras.
  • Vamos representar essa lembrança por estados: um estado para “nenhuma \mathrm{a} recente” (ou seja, a última letra não é \mathrm{a}), um estado para “a última letra foi \mathrm{a} (mas ainda não duas \mathrm{a})” e um estado de aceitação para "as duas últimas letras lidas são \mathrm{a}\mathrm{a}".
  • Esse raciocínio já sugere que três estados são suficientes e necessários: 0 \mathrm{a} final, 1 \mathrm{a} final, 2 \mathrm{a} finais.

Passo 3

Definição formal do autômato (anotando o que cada símbolo significa):
  • Q será o conjunto de estados.
  • \Sigma=\{\mathrm{a},\mathrm{b}\} é o alfabeto.
  • \delta é a função de transição.
  • q_0 é o estado inicial.
  • F é o conjunto de estados de aceitação.
Escolha concreta dos estados (com interpretação):
  • q_0: não há \mathrm{a} chegando ao fim (ou seja, a última letra lida não é \mathrm{a}, ou ainda a palavra é vazia).
  • q_1: a última letra lida foi \mathrm{a}, mas as duas últimas não são \mathrm{a}\mathrm{a}.
  • q_2: as duas últimas letras lidas são \mathrm{a}\mathrm{a} (estado de aceitação).
Portanto:
Q=\{q_0,q_1,q_2\},\qquad q_0\\ \text{inicial},\qquad F=\{q_2\}.

Passo 4

Definir a função de transição \delta e justificar cada caso (explicação didática):
  • Se estou em q_0 (último símbolo não é \mathrm{a} ou palavra vazia):
    • ao ler \mathrm{a} a última letra passa a ser \mathrm{a}, então vou para q_1;
    • ao ler \mathrm{b} continuo sem \mathrm{a} no fim, fico em q_0.
  • Se estou em q_1 (última letra foi \mathrm{a}):
    • ao ler \mathrm{a} agora as duas últimas são \mathrm{a}\mathrm{a}, vou para q_2;
    • ao ler \mathrm{b} a sequência \mathrm{a} é “quebrada” por \mathrm{b}, volto para q_0.
  • Se estou em q_2 (últimas duas letras são \mathrm{a}\mathrm{a}):
    • ao ler \mathrm{a} as duas últimas ainda serão \mathrm{a}\mathrm{a} (a nova última e a anterior continuam \mathrm{a}\mathrm{a}), então permaneço em q_2;
    • ao ler \mathrm{b} a sequência final deixa de terminar em \mathrm{a}, volto para q_0.
Escrevendo \delta de forma direta:
\delta(q_0,\mathrm{a})=q_1,\qquad \delta(q_0,\mathrm{b})=q_0,
\delta(q_1,\mathrm{a})=q_2,\qquad \delta(q_1,\mathrm{b})=q_0,
\delta(q_2,\mathrm{a})=q_2,\qquad \delta(q_2,\mathrm{b})=q_0.

Passo 5

Verificação por exemplos (mostrando passo a passo as leituras, para aprender a usar o autômato na prova):
  • Palavra \mathrm{aa}:
    • começo em q_0,
    • leio primeira \mathrm{a}: q_0 \xrightarrow{\mathrm{a}} q_1,
    • leio segunda \mathrm{a}: q_1 \xrightarrow{\mathrm{a}} q_2,
    • termino em q_2 que é de aceitação → aceita (correto).
  • Palavra \mathrm{aba}:
    • q_0 \xrightarrow{\mathrm{a}} q_1,
    • q_1 \xrightarrow{\mathrm{b}} q_0,
    • q_0 \xrightarrow{\mathrm{a}} q_1,
    • termino em q_1 (não aceito) → correta, \mathrm{aba} não termina em \mathrm{aa}.
  • Palavra \mathrm{baa}:
    • q_0 \xrightarrow{\mathrm{b}} q_0,
    • q_0 \xrightarrow{\mathrm{a}} q_1,
    • q_1 \xrightarrow{\mathrm{a}} q_2,
    • termino em q_2 → aceita.

Passo 6

Propriedades finais e observações para a prova:
  • O autômato é determinístico: para cada par (estado, símbolo) há exatamente uma transição definida.
  • É completo: \delta está definida para todos os q\in Q e para ambos os símbolos \mathrm{a},\mathrm{b}.
  • Minimalidade (intuição): não é possível ter menos de três estados porque é preciso distinguir entre as situações “nenhuma \mathrm{a} recente”, “uma \mathrm{a} recente” e “duas \mathrm{a} recentes”. Formalmente, existem palavras que exigem que esses três estados sejam distinguíveis por extensão (por exemplo, distinguir \varepsilon, \mathrm{a} e \mathrm{aa} com sufixos adicionados).
  • Dica prática para a prova: desenhe os três estados em linha: q_0 --a–> q_1 --a–> q_2 (aceitável), com setas de retorno por \mathrm{b} para q_0 e laço em q_2 por \mathrm{a}. Isso é rápido e claro num gabarito.

Resposta

M=\bigl(Q,\Sigma,\delta,q_0,F\bigr)
Q=\{q_0,q_1,q_2\},\qquad \Sigma=\{\mathrm{a},\mathrm{b}\},\qquad q_0\\ \text{inicial},\qquad F=\{q_2\}
\delta(q_0,\mathrm{a})=q_1,\quad \delta(q_0,\mathrm{b})=q_0,
\delta(q_1,\mathrm{a})=q_2,\quad \delta(q_1,\mathrm{b})=q_0,
\delta(q_2,\mathrm{a})=q_2,\quad \delta(q_2,\mathrm{b})=q_0.

Exercícios relacionados