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 tamanho par e um número ímpar de “a”}.

Passo 1

O que o enunciado pede e o que ele dá:
  • O alfabeto é \Sigma=\{\mathrm{a},\mathrm{b}\}.
  • Queremos um AFD que reconheça a linguagem formada por todas as palavras \mathrm{w} tais que:
    1. \mathrm{w} tem tamanho par (ou seja, o número de símbolos de \mathrm{w} é par);
    2. \mathrm{w} tem um número ímpar de \mathrm{a}.
  • Em outras palavras, a linguagem é a interseção de duas propriedades: “tamanho par” e "número ímpar de \mathrm{a}". O objetivo é construir um AFD que aceite exatamente as palavras que satisfazem ambas as propriedades ao mesmo tempo.

Passo 2

Construindo um AFD simples que reconheça “tamanho par”.
  • Ideia: só precisamos lembrar se o comprimento visto até agora é par ou ímpar. Então usamos dois estados.
  • Definição informal:
    • Estado p_E: já li um número par de símbolos (começa aqui, pois a palavra vazia tem comprimento 0, que é par).
    • Estado p_O: já li um número ímpar de símbolos.
  • Transições:
    • Ao ler qualquer símbolo ( \mathrm{a} ou \mathrm{b}) alternamos entre p_E e p_O (pois cada símbolo altera a paridade do comprimento).
  • Estado inicial: p_E.
  • Estado de aceitação: p_E (porque queremos comprimento par).
  • Observação didática: este AFD tem 2 estados; qualquer símbolo muda a paridade do comprimento.

Passo 3

Construindo um AFD simples que reconheça "número ímpar de \mathrm{a}".
  • Ideia: só precisamos lembrar a paridade da quantidade de \mathrm{a}s lidas. Novamente usamos dois estados.
  • Definição informal:
    • Estado r_E: já li um número par de \mathrm{a}s (começa aqui, pois zero é par).
    • Estado r_O: já li um número ímpar de \mathrm{a}s.
  • Transições:
    • Ao ler \mathrm{a}: alternamos entre r_E e r_O (pois cada \mathrm{a} muda a paridade da contagem de \mathrm{a}s).
    • Ao ler \mathrm{b}: permanecemos no mesmo estado (pois \mathrm{b} não altera a contagem de \mathrm{a}s).
  • Estado inicial: r_E.
  • Estado de aceitação: r_O (porque queremos número ímpar de \mathrm{a}s).
  • Observação didática: este AFD também tem 2 estados; apenas a leitura de \mathrm{a} altera seu estado.

Passo 4

Construindo o AFD para a interseção: produto cartesiano dos dois AFDs.
  • Técnica usada (explicando para a prova): a interseção de duas linguagens regulares reconhecidas por AFDs pode ser feita com o produto cartesiano dos estados: cada estado do novo AFD é um par (estado do AFD1, estado do AFD2). Isso permite acompanhar simultaneamente as duas propriedades.
  • Estados do novo AFD: todos os pares (p, r) com p\in\{p_E,p_O\} e r\in\{r_E,r_O\}. Vamos renomear para ficar prático e curto:
    • q_{00}=(p_E,r_E) — comprimento par, número de \mathrm{a} par.
    • q_{01}=(p_E,r_O) — comprimento par, número de \mathrm{a} ímpar.
    • q_{10}=(p_O,r_E) — comprimento ímpar, número de \mathrm{a} par.
    • q_{11}=(p_O,r_O) — comprimento ímpar, número de \mathrm{a} ímpar.
  • Estado inicial do produto: q_{00} (vazio: comprimento par e zero \mathrm{a}s).
  • Estados de aceitação do produto: somente aqueles pares que satisfazem ambas as propriedades: comprimento par E número ímpar de \mathrm{a}s. Logo o único estado de aceitação é q_{01}.
  • Regra de transição do produto (explicação): para cada símbolo x\in\{\mathrm{a},\mathrm{b}\}, \delta_{\text{produto}}\big((p,r),x\big)=\big(\delta_{p}(p,x),\delta_{r}(r,x)\big),ou seja, aplicamos a transição em cada componente.

Passo 5

Construindo explicitamente a função de transição e justificando cada entrada.
  • Lembrete das regras de mudança:
    • Ler qualquer símbolo altera a paridade do comprimento (alternância entre p_E e p_O).
    • Ler \mathrm{a} altera a paridade do número de \mathrm{a}s; ler \mathrm{b} não altera essa paridade.
  • Usando essa ideia, calculamos as transições para cada estado par:
    • A partir de q_{00}=(E,\text{a-par}):
      • lendo \mathrm{a}: comprimento troca para ímpar, número de \mathrm{a} fica ímpar → vai para q_{11}.
      • lendo \mathrm{b}: comprimento troca para ímpar, número de \mathrm{a} permanece par → vai para q_{10}.
    • A partir de q_{01}=(E,\text{a-ímpar})í:
      • lendo \mathrm{a}: comprimento → ímpar, contagem de \mathrm{a} troca para par → vai para q_{10}.
      • lendo \mathrm{b}: comprimento → ímpar, contagem de \mathrm{a} permanece ímpar → vai para q_{11}.
    • A partir de q_{10}=(O,\text{a-par}):
      • lendo \mathrm{a}: comprimento → par, contagem de \mathrm{a} → ímpar → vai para q_{01}.
      • lendo \mathrm{b}: comprimento → par, contagem de \mathrm{a} permanece par → vai para q_{00}.
    • A partir de q_{11}=(O,\text{a-ímpar})í:
      • lendo \mathrm{a}: comprimento → par, contagem de \mathrm{a} → par → vai para q_{00}.
      • lendo \mathrm{b}: comprimento → par, contagem de \mathrm{a} permanece ímpar → vai para q_{01}.
  • Observação didática com um exemplo prático:
    • Tome a palavra \mathrm{w}= “ab”. Percurso:
      • start q_{00} — ler \mathrm{a} q_{11} — ler \mathrm{b} q_{01}.
      • q_{01} é de aceitação, então “ab” é aceita (tem comprimento 2 par e uma \mathrm{a} — ímpar).
    • Tome \mathrm{w}= “aba”: percurso:
      • q_{00}\xrightarrow{\mathrm{a}}q_{11}\xrightarrow{\mathrm{b}}q_{01}\xrightarrow{\mathrm{a}}q_{10}.
      • q_{10} não é de aceitação → “aba” rejeitada (comprimento 3 ímpar).

Passo 6

Apresentando de forma formal e finalizada (pronto para a prova).
  • Vamos colocar o AFD final explicitamente com seus componentes (concreta descrição que você pode desenhar ou escrever na prova):
    • Conjunto de estados: Q=\{q_{00},q_{01},q_{10},q_{11}\}.
    • Alfabeto: \Sigma=\{\mathrm{a},\mathrm{b}\}.
    • Função de transição \delta dada pela tabela abaixo (já justificada no passo anterior): \begin{array}{c|cc} & \mathrm{a} & \mathrm{b} \\\ \hline q_{00} & q_{11} & q_{10} \\\ q_{01} & q_{10} & q_{11} \\\ q_{10} & q_{01} & q_{00} \\\ q_{11} & q_{00} & q_{01} \end{array}
    • Estado inicial: q_0=q_{00}.
    • Conjunto de estados de aceitação: F=\{q_{01}\}.
  • Observação final e incentivo: esse AFD reconhece exatamente as palavras com comprimento par e número ímpar de \mathrm{a}. A construção por produto é padrão e muito útil — com prática você faz isso rapidinho na prova. Você já tem as ferramentas: lembrar duas paridades (comprimento e contagem de \mathrm{a}) e combiná-las.

Resposta

M=(Q,\Sigma,\delta,q_0,F)
Q=\{q_{00},q_{01},q_{10},q_{11}\}
\Sigma=\{\mathrm{a},\mathrm{b}\}
\delta\text{ dada por } \begin{array}{c|cc} & \mathrm{a} & \mathrm{b} \\\ \hline q_{00} & q_{11} & q_{10} \\\ q_{01} & q_{10} & q_{11} \\\ q_{10} & q_{01} & q_{00} \\\ q_{11} & q_{00} & q_{01} \end{array}
q_0=q_{00},\qquad F=\{q_{01}\}

Exercícios relacionados