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 pelo menos três “a” e pelo menos dois “b”}.

Passo 1

O enunciado pede: construir um AFD (determinístico) sobre o alfabeto \Sigma=\{\mathrm{a},\mathrm{b}\} que reconheça a linguagem
\{\,w \mid w \text{ tem pelo menos três } \mathrm{a}\text{ e pelo menos dois } \mathrm{b}\,\}.ê
Informações dadas:
  • Alfabeto: \Sigma=\{\mathrm{a},\mathrm{b}\}.
  • A condição que a palavra deve satisfazer é dupla: "pelo menos três \mathrm{a}" E "pelo menos dois \mathrm{b}".
    O objetivo é construir um AFD que aceite exatamente as palavras que satisfazem ambas as condições ao mesmo tempo (intersecção das duas propriedades).

Passo 2

Ideia geral (sem pular etapas): uma forma direta é construir dois AFDs simples, um que conte \mathrm{a}s até garantir “pelo menos três” e outro que conte \mathrm{b}s até garantir “pelo menos dois”, e então usar o produto (construção por produto cartesiano) para obter um AFD que verifica as duas condições simultaneamente. Vou explicar cada parte com calma.
Primeiro, como representar “contar até um limite” num AFD:
  • Para "pelo menos três \mathrm{a}" não precisamos contar além de 3: basta ter estados que representem "vi 0 \mathrm{a}", "vi 1 \mathrm{a}", "vi 2 \mathrm{a}" e "vi 3 ou mais \mathrm{a}". O estado “3 ou mais” é uma classe absorvente para contagens de \mathrm{a}.
  • Analogamente, para "pelo menos dois \mathrm{b}" usamos estados "0 \mathrm{b}", "1 \mathrm{b}" e "2 ou mais \mathrm{b}".
Vou construir os dois AFDs pequenos explicitando estados e transições; isso é exatamente a técnica que você pode usar na prova.

Passo 3

Construção do AFD que checa "pelo menos três \mathrm{a}":
Defina estados que representam quantas \mathrm{a}s já apareceram (cortadas em 3+):
  • Estados: \{A_0, A_1, A_2, A_3\}, onde A_i significa "já vi i ocorrências de \mathrm{a}" para i=0,1,2, e A_3 significa "já vi 3 ou mais \mathrm{a}".
  • Estado inicial: A_0.
  • Estados aceitação: \{A_3\} (porque aceitar quando já vimos pelo menos 3 \mathrm{a}).
  • Regras de transição:
    • Ao ler \mathrm{a}: avanço a contagem de \mathrm{a} até saturar em 3, isto é, \delta_A(A_i,\mathrm{a}) = A_{\min(i+1,3)}.
    • Ao ler \mathrm{b}: a quantidade de \mathrm{a} não muda: \delta_A(A_i,\mathrm{b}) = A_i.
Explicando com exemplos: de A_0 com \mathrm{a} vou para A_1; de A_2 com \mathrm{a} vou para A_3; de A_3 com \mathrm{a} fico em A_3; qualquer \mathrm{b} não altera o componente A.

Passo 4

Construção do AFD que checa "pelo menos dois \mathrm{b}":
Defina estados que representam quantas \mathrm{b}s já apareceram (cortadas em 2+):
  • Estados: \{B_0, B_1, B_2\}, onde B_j significa "já vi j ocorrências de \mathrm{b}" para j=0,1, e B_2 significa "já vi 2 ou mais \mathrm{b}".
  • Estado inicial: B_0.
  • Estados aceitação: \{B_2\}.
  • Regras de transição:
    • Ao ler \mathrm{b}: \delta_B(B_j,\mathrm{b}) = B_{\min(j+1,2)}.
    • Ao ler \mathrm{a}: \delta_B(B_j,\mathrm{a}) = B_j.
Exemplo: de B_0 com \mathrm{b} vou a B_1; de B_1 com \mathrm{b} vou a B_2; depois fico em B_2 com qualquer \mathrm{b}; \mathrm{a}s não afetam o contador de \mathrm{b}.

Passo 5

Construção do AFD da intersecção via produto cartesiano (passo a passo):
Princípio: se temos dois AFDs determinísticos M_A=(Q_A,\Sigma,\delta_A,q_{A0},F_A) e M_B=(Q_B,\Sigma,\delta_B,q_{B0},F_B), um AFD que reconhece L(M_A)\cap L(M_B) é o produto
M=(Q_A\times Q_B,\Sigma,\delta,(q_{A0},q_{B0}),F)
onde a função de transição é aplicada componente a componente:
\delta\big((p,q),\sigma\big) = \big(\delta_A(p,\sigma),\delta_B(q,\sigma)\big),
e os estados de aceitação são os pares cujo primeiro componente está em F_A e o segundo em F_B:
F = F_A \times F_B.
No nosso caso:
  • Q_A=\{A_0,A_1,A_2,A_3\}, F_A=\{A_3\}.
  • Q_B=\{B_0,B_1,B_2\}, F_B=\{B_2\}.
  • O conjunto de estados do produto tem 4\times 3=12 pares: \{(A_i,B_j)\mid i\in\{0,1,2,3\},\; j\in\{0,1,2\}\}.
  • Estado inicial: (A_0,B_0).
  • Estado(s) de aceitação: exatamente os pares onde já satisfaço ambas as condições, isto é F=\{(A_3,B_2)\} (porque A_3 significa ≥3 \mathrm{a} e B_2 significa ≥2 \mathrm{b}).
Transição geral (regra compacta, fácil de aplicar na prova):
  • Para todo i\in\{0,1,2,3\}, j\in\{0,1,2\}, \delta\big((A_i,B_j),\mathrm{a}\big) = \big(A_{\min(i+1,3)},\,B_j\big),
\delta\big((A_i,B_j),\mathrm{b}\big) = \big(A_i,\,B_{\min(j+1,2)}\big).
Explicação: ao ler \mathrm{a} só aumenta a contagem de \mathrm{a} (com saturação em 3), ao ler \mathrm{b} só aumenta a contagem de \mathrm{b} (com saturação em 2).

Passo 6

Vou dar um exemplo de execução para você ver que o autômato funciona (treinamento prático para a prova). Tome a palavra w=\mathrm{aababb}.
  • Começo em (A_0,B_0).
  • Leio \mathrm{a}: vou para (A_1,B_0).
  • Leio \mathrm{a}: vou para (A_2,B_0).
  • Leio \mathrm{b}: vou para (A_2,B_1).
  • Leio \mathrm{a}: vou para (A_3,B_1).
  • Leio \mathrm{b}: vou para (A_3,B_2).
  • Leio \mathrm{b}: permaneço em (A_3,B_2).
Como terminei em (A_3,B_2), que é estado de aceitação, a palavra é aceita. Isso corresponde ao fato intuitivo: w tem pelo menos três \mathrm{a} e pelo menos dois \mathrm{b}.

Passo 7

Observações para a prova (dicas rápidas e úteis):
  • Em provas, desenhe os dois autômatos contadores (menores) e depois construa o produto mentalmente. Nomeie estados como (i,j) com i em \{0,1,2,3\} e j em \{0,1,2\} para ficar rápido.
  • A regra compacta com \min é uma forma curta de escrever as transições; se o examinador pedir, você pode listar explicitamente os 12 estados e as 24 transições.
  • Minimizar o autômato não é necessário para responder corretamente, a não ser que peçam o menor AFD; a construção por produto já é correta e determinística.

Resposta

M=(Q,\Sigma,\delta,q_0,F) com
\Sigma=\{\mathrm{a},\mathrm{b}\},
Q=\{(A_i,B_j)\mid i\in\{0,1,2,3\},\; j\in\{0,1,2\}\},
q_0=(A_0,B_0),
F=\{(A_3,B_2)\},
e, para todo i\in\{0,1,2,3\}, j\in\{0,1,2\},
\delta\big((A_i,B_j),\mathrm{a}\big)=\big(A_{\min(i+1,3)},\,B_j\big),
\delta\big((A_i,B_j),\mathrm{b}\big)=\big(A_i,\,B_{\min(j+1,2)}\big).

Exercícios relacionados