Construa os seguintes AFDs para reconhecer as intersecção entre as linguagens solicitadas, todo os alfabetos são \Sigma=\{\mathrm{a}, \mathrm{b}\} :
\{w \mid w tem um número ímpar de “a” e termina com “b” }.

Passo 1

O que o enunciado pede: construir um AFD que reconheça a interseção das duas propriedades seguintes sobre palavras w sobre o alfabeto \Sigma=\{\mathrm{a},\mathrm{b}\}:
  1. w tem um número ímpar de \mathrm{a}.
  2. w termina com \mathrm{b}.
Informações relevantes dadas: \Sigma=\{\mathrm{a},\mathrm{b}\} e a linguagem desejada é
\{w \mid w \text{ tem um número ímpar de }\mathrm{a}\text{ e termina com }\mathrm{b}\}.úí

Passo 2

Vamos construir, passo a passo, dois AFDs simples que reconhecem cada propriedade separadamente. Depois vamos combiná-los (produto cartesiano) para obter o AFD da interseção.
Primeiro AFD (paridade de \mathrm{a}). Ideia: precisamos apenas saber se já vimos um número par ou ímpar de \mathrm{a}. Então usamos dois estados: “par” e “ímpar”. Sempre que lemos uma \mathrm{a} trocamos de paridade; ao ler \mathrm{b} a paridade não muda.
Formalmente, definimos:
Q_1=\{E,O\},\quad q_{0,1}=E,\quad F_1=\{O\},\quad \Sigma=\{\mathrm{a},\mathrm{b}\},
onde E = estado com número de \mathrm{a} visto até agora par, O = ímpar. A função de transição \delta_1 é
\begin{aligned} \delta_1(E,\mathrm{a}) &= O, & \delta_1(E,\mathrm{b}) &= E,\\\ \delta_1(O,\mathrm{a}) &= E, & \delta_1(O,\mathrm{b}) &= O. \end{aligned}
Explicação didática: se você leu zero \mathrm{a} (estado E) e lê uma \mathrm{a}, passa para O (um \mathrm{a} = ímpar). Ler \mathrm{b} não altera a contagem de \mathrm{a}, então permanece no mesmo tipo de estado.

Passo 3

Segundo AFD (termina com \mathrm{b}). Ideia: guardamos apenas se o último símbolo lido foi \mathrm{b} ou não. Dois estados: “último não é b” e “último é b”. A palavra vazia não termina com \mathrm{b}, então o estado inicial é o de “último não é b”. O estado de aceitação é “último é b”.
Formalmente:
Q_2=\{N,B\},\quad q_{0,2}=N,\quad F_2=\{B\},\quad \Sigma=\{\mathrm{a},\mathrm{b}\},
onde N = o último símbolo lido não é \mathrm{b} (ou ainda não lemos nada), B = o último símbolo lido foi \mathrm{b}. A função de transição \delta_2 é
\begin{aligned} \delta_2(N,\mathrm{a}) &= N, & \delta_2(N,\mathrm{b}) &= B,\\\ \delta_2(B,\mathrm{a}) &= N, & \delta_2(B,\mathrm{b}) &= B. \end{aligned}
Explicação didática: ao ler \mathrm{b} vamos para o estado que lembra "termina com \mathrm{b}"; ao ler \mathrm{a} passamos para o estado que lembra "não termina com \mathrm{b}".

Passo 4

Agora a parte importante: construir o AFD da interseção usando o produto cartesiano. Regra geral (produto de dois AFDs): se temos
M_1=(Q_1,\Sigma,\delta_1,q_{0,1},F_1)\quad\text{e}\quad M_2=(Q_2,\Sigma,\delta_2,q_{0,2},F_2),
então o AFD que reconhece L(M_1)\cap L(M_2) é
M=(Q,\Sigma,\delta,q_0,F)
com
Q=Q_1\times Q_2,\quad q_0=(q_{0,1},q_{0,2}),\quad F=F_1\times F_2,
e a transição definida por
\delta\big((p,q),x\big) = \big(\delta_1(p,x),\,\delta_2(q,x)\big)
para todo x\in\Sigma.
Explicação didática: o estado no novo AFD guarda, simultaneamente, a informação de cada autômato componente. Ao ler um símbolo, atualizamos cada componente conforme seu autômato. Aceitamos somente quando ambos componentes estão em estados de aceitação (já que queremos palavras que satisfaçam as duas propriedades ao mesmo tempo).

Passo 5

Aplicando o produto aos dois AFDs acima: os estados são pares (\text{paridade de a},\text{último simb.})ú.
Listamos explicitamente os elementos:
Q = \{(E,N),\\ (E,B),\\ (O,N),\\ (O,B)\},
o estado inicial é
q_0=(E,N),
e o conjunto de aceitação, por F=F_1\times F_2, é
F=\{(O,B)\}.
Agora calculemos as transições usando \delta((p,q),x)=(\delta_1(p,x),\delta_2(q,x)). Temos:
\begin{aligned} \delta\big((E,N),\mathrm{a}\big) &= (\delta_1(E,\mathrm{a}),\delta_2(N,\mathrm{a})) = (O,N),\\\ \delta\big((E,N),\mathrm{b}\big) &= (\delta_1(E,\mathrm{b}),\delta_2(N,\mathrm{b})) = (E,B),\\[4pt] \delta\big((E,B),\mathrm{a}\big) &= (\delta_1(E,\mathrm{a}),\delta_2(B,\mathrm{a})) = (O,N),\\\ \delta\big((E,B),\mathrm{b}\big) &= (\delta_1(E,\mathrm{b}),\delta_2(B,\mathrm{b})) = (E,B),\\[4pt] \delta\big((O,N),\mathrm{a}\big) &= (\delta_1(O,\mathrm{a}),\delta_2(N,\mathrm{a})) = (E,N),\\\ \delta\big((O,N),\mathrm{b}\big) &= (\delta_1(O,\mathrm{b}),\delta_2(N,\mathrm{b})) = (O,B),\\[4pt] \delta\big((O,B),\mathrm{a}\big) &= (\delta_1(O,\mathrm{a}),\delta_2(B,\mathrm{a})) = (E,N),\\\ \delta\big((O,B),\mathrm{b}\big) &= (\delta_1(O,\mathrm{b}),\delta_2(B,\mathrm{b})) = (O,B). \end{aligned}
Explicação didática com exemplo: comece em (E,N). Para a palavra \mathrm{ab}: primeiro \mathrm{a} leva a (O,N) (agora há um \mathrm{a}, ímpar, e último símbolo não é \mathrm{b}); depois \mathrm{b} leva a (O,B) que é estado de aceitação — a palavra tem número ímpar de \mathrm{a} e termina com \mathrm{b}, OK.]

Passo 6

Verificação rápida: todos os quatro estados são alcançáveis a partir de q_0 (por exemplo, (E,B) por \mathrm{b}, (O,N) por \mathrm{a}, (O,B) por \mathrm{ab}), e apenas (O,B) é de aceitação. Esse AFD reconhece exatamente as palavras que simultaneamente têm número ímpar de \mathrm{a} e terminam em \mathrm{b}.

Resposta

M=(Q,\Sigma,\delta,q_0,F)
Q=\{(E,N),\\ (E,B),\\ (O,N),\\ (O,B)\}
\Sigma=\{\mathrm{a},\mathrm{b}\}
q_0=(E,N)
F=\{(O,B)\}
\begin{aligned} \delta\big((E,N),\mathrm{a}\big) &= (O,N), & \delta\big((E,N),\mathrm{b}\big) &= (E,B),\\\ \delta\big((E,B),\mathrm{a}\big) &= (O,N), & \delta\big((E,B),\mathrm{b}\big) &= (E,B),\\\ \delta\big((O,N),\mathrm{a}\big) &= (E,N), & \delta\big((O,N),\mathrm{b}\big) &= (O,B),\\\ \delta\big((O,B),\mathrm{a}\big) &= (E,N), & \delta\big((O,B),\mathrm{b}\big) &= (O,B). \end{aligned}

Exercícios relacionados