Construa os seguintes AFDs para reconhecer as intersecção entre as linguagens solicitadas, todo os alfabetos são \Sigma=\{\mathrm{a}, \mathrm{b}\} :
\{\mathrm{w} \mid \mathrm{w} tem exatamente dois “a” e pelo menos dois “b” }.

Passo 1

O que o enunciado pede: construir um AFD que reconheça a linguagem de todas as palavras w sobre o alfabeto \Sigma=\{\mathrm{a},\mathrm{b}\} tais que w tem exatamente dois \mathrm{a} e pelo menos dois \mathrm{b}.
Informações relevantes dadas:
  • Alfabeto: \Sigma=\{\mathrm{a},\mathrm{b}\}.
  • Condições simultâneas (intersecção):
    • exatamente dois \mathrm{a};
    • pelo menos dois \mathrm{b}.

Passo 2

Ideia geral de construção (sem detalhes ainda): para reconhecer a intersecção de duas condições sobre contas de símbolos, um caminho natural é construir dois AFDs simples que testem cada condição separadamente e depois formar o AFD produto (autômato composto) para a intersecção. Vou explicar cada autômato simples e depois a construção do produto passo a passo.
Breve lembrete sobre AFDs (didático): um AFD é definido por um quíntuplo (Q,\Sigma,\delta,q_0,F), onde
Q
é o conjunto de estados, \Sigma o alfabeto, \delta a função de transição, q_0 o estado inicial e F o conjunto de estados finais. Para contar ocorrências limitadas de um símbolo, usamos estados que representam “quantos já vimos até agora” (ex.: 0,1,2, e um estado que indica “mais que 2”).

Passo 3

Construção do AFD que reconhece “exatamente dois \mathrm{a}” (vou chamar de A).
Definição do autômato A:
Q_A=\{q_{0}^{a},\,q_{1}^{a},\,q_{2}^{a},\,q_{3}^{a}\}
Interpretação dos estados:
  • q_{0}^{a}: já vimos 0 letras \mathrm{a};
  • q_{1}^{a}: já vimos 1 letra \mathrm{a};
  • q_{2}^{a}: já vimos exatamente 2 letras \mathrm{a};
  • q_{3}^{a}: já vimos mais de 2 letras \mathrm{a} (estado “sink” para excesso).
Estado inicial:
q_{0}^{a}
Estados finais:
F_A=\{q_{2}^{a}\}
Função de transição \delta_A (explicação: ler uma \mathrm{a} incrementa o contador; ler \mathrm{b} deixa contador de \mathrm{a} inalterado):
\delta_A(q_{0}^{a},\mathrm{a})=q_{1}^{a},\qquad \delta_A(q_{1}^{a},\mathrm{a})=q_{2}^{a},
\delta_A(q_{2}^{a},\mathrm{a})=q_{3}^{a},\qquad \delta_A(q_{3}^{a},\mathrm{a})=q_{3}^{a},
\delta_A(q_{0}^{a},\mathrm{b})=q_{0}^{a},\qquad \delta_A(q_{1}^{a},\mathrm{b})=q_{1}^{a},
\delta_A(q_{2}^{a},\mathrm{b})=q_{2}^{a},\qquad \delta_A(q_{3}^{a},\mathrm{b})=q_{3}^{a}.
Motivação curta: aceitar somente se, ao final da leitura, estivermos em q_{2}^{a} (exatamente duas \mathrm{a}). Se exceder duas \mathrm{a}, vamos para q_{3}^{a} que é não-aceitante.

Passo 4

Construção do AFD que reconhece “pelo menos dois \mathrm{b}” (vou chamar de B).
Definição do autômato B:
Q_B=\{q_{0}^{b},\,q_{1}^{b},\,q_{2}^{b}\}
Interpretação dos estados:
  • q_{0}^{b}: já vimos 0 letras \mathrm{b};
  • q_{1}^{b}: já vimos 1 letra \mathrm{b};
  • q_{2}^{b}: já vimos pelo menos 2 letras \mathrm{b} (estado absorbente).
Estado inicial:
q_{0}^{b}
Estados finais:
F_B=\{q_{2}^{b}\}
Função de transição \delta_B (explicação: ler uma \mathrm{b} incrementa o contador de \mathrm{b}; ler \mathrm{a} não altera o contador de \mathrm{b}):
\delta_B(q_{0}^{b},\mathrm{b})=q_{1}^{b},\qquad \delta_B(q_{1}^{b},\mathrm{b})=q_{2}^{b},\qquad \delta_B(q_{2}^{b},\mathrm{b})=q_{2}^{b},
\delta_B(q_{0}^{b},\mathrm{a})=q_{0}^{b},\qquad \delta_B(q_{1}^{b},\mathrm{a})=q_{1}^{b},\qquad \delta_B(q_{2}^{b},\mathrm{a})=q_{2}^{b}.
Motivação curta: aceitar se ao final estivermos em q_{2}^{b}, que significa “já vi pelo menos duas \mathrm{b}”.

Passo 5

Construção do AFD produto P que reconhece a intersecção “exatamente dois \mathrm{a} E pelo menos dois \mathrm{b}”.
Regra do produto (explicação didática): os estados de P são pares (p,q) onde p é um estado de A e q é um estado de B. A leitura de um símbolo atualiza ambos os componentes simultaneamente usando as suas respectivas funções de transição. Aceitamos exatamente quando ambos os autômatos componentes estariam em estados finais.
Definição do produto P:
Q_P = Q_A\times Q_B = \{(q_{i}^{a},q_{j}^{b}) \mid i\in\{0,1,2,3\},\; j\in\{0,1,2\}\}.
Estado inicial:
(q_{0}^{a},q_{0}^{b})
Conjunto de estados finais (intersecção dos finais):
F_P = F_A\times F_B = \{(q_{2}^{a},q_{2}^{b})\}.
Função de transição \delta_P (regra componente a componente):
\delta_P\bigl((p,q),x\bigr)=\bigl(\delta_A(p,x),\,\delta_B(q,x)\bigr),
para todo x\in\{\mathrm{a},\mathrm{b}\}.
Exemplos para fixar a ideia:
\delta_P\bigl((q_{1}^{a},q_{1}^{b}),\mathrm{a}\bigr)=(q_{2}^{a},q_{1}^{b}),
\delta_P\bigl((q_{2}^{a},q_{1}^{b}),\mathrm{b}\bigr)=(q_{2}^{a},q_{2}^{b}).
Observação sobre número de estados: P tem 4\times 3=12 estados. Desses, apenas o estado (q_{2}^{a},q_{2}^{b}) é final. Estados com q_{3}^{a} (mais de duas \mathrm{a}) nunca serão finais — servem como “sumidouro” para palavras com muitas \mathrm{a}.

Passo 6

Comentário prático para a prova (útil e motivador): se precisar desenhar o autômato no caderno, você pode desenhar os 12 estados como uma grade 4\times3 (linhas para o contador de \mathrm{a}, colunas para o contador de \mathrm{b}) e desenhar as setas segundo a regra componente-a-componente. Outra opção prática é simplesmente descrever o autômato produto pela regra geral dada em \delta_P, porque isso já é uma especificação formal válida para um AFD.
Algumas palavras-testes (verificação rápida):
  • \mathrm{aab b} (por exemplo, \mathrm{aabb}) tem exatamente duas \mathrm{a} e duas \mathrm{b} → aceita.
  • \mathrm{aba}\mathrm{b} ( \mathrm{abab}) tem duas \mathrm{a} e duas \mathrm{b} → aceita.
  • \mathrm{aa b} ( \mathrm{aab}) tem duas \mathrm{a} mas só uma \mathrm{b} → rejeita.
  • \mathrm{abbb a} ( \mathrm{abbba}) tem duas \mathrm{a} e três \mathrm{b} → aceita.
  • \mathrm{aaa bb} ( \mathrm{aaabb}) tem três \mathrm{a} → rejeita.

Resposta

(Q,\Sigma,\delta,q_0,F) onde
\Sigma=\{\mathrm{a},\mathrm{b}\},
Q=\{(q_{i}^{a},q_{j}^{b}) \mid i\in\{0,1,2,3\},\; j\in\{0,1,2\}\},
q_0=(q_{0}^{a},q_{0}^{b}),
F=\{(q_{2}^{a},q_{2}^{b})\},
e para todo (p,q)\in Q e todo x\in\{\mathrm{a},\mathrm{b}\} vale
\delta\bigl((p,q),x\bigr)=\bigl(\delta_A(p,x),\delta_B(q,x)\bigr),
onde \delta_A e \delta_B são dadas por
\delta_A(q_{0}^{a},\mathrm{a})=q_{1}^{a},\quad \delta_A(q_{1}^{a},\mathrm{a})=q_{2}^{a},\quad \delta_A(q_{2}^{a},\mathrm{a})=q_{3}^{a},\quad \delta_A(q_{3}^{a},\mathrm{a})=q_{3}^{a},
\delta_A(q_{0}^{a},\mathrm{b})=q_{0}^{a},\quad \delta_A(q_{1}^{a},\mathrm{b})=q_{1}^{a},\quad \delta_A(q_{2}^{a},\mathrm{b})=q_{2}^{a},\quad \delta_A(q_{3}^{a},\mathrm{b})=q_{3}^{a},
\delta_B(q_{0}^{b},\mathrm{b})=q_{1}^{b},\quad \delta_B(q_{1}^{b},\mathrm{b})=q_{2}^{b},\quad \delta_B(q_{2}^{b},\mathrm{b})=q_{2}^{b},
\delta_B(q_{0}^{b},\mathrm{a})=q_{0}^{b},\quad \delta_B(q_{1}^{b},\mathrm{a})=q_{1}^{b},\quad \delta_B(q_{2}^{b},\mathrm{a})=q_{2}^{b}.

Exercícios relacionados