Construa os seguintes AFDs para reconhecer as intersecção entre as linguagens solicitadas, todo os alfabetos são
:
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
sobre o alfabeto
:
-
tem um número ímpar de . -
termina com .
Informações relevantes dadas:
e a linguagem desejada é
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
). Ideia: precisamos apenas saber se já vimos um número par ou ímpar de
. Então usamos dois estados: “par” e “ímpar”. Sempre que lemos uma
trocamos de paridade; ao ler
a paridade não muda.
Formalmente, definimos:
onde
= estado com número de
visto até agora par,
= ímpar. A função de transição
é
Explicação didática: se você leu zero
(estado
) e lê uma
, passa para
(um
= ímpar). Ler
não altera a contagem de
, então permanece no mesmo tipo de estado.
Passo 3
Segundo AFD (termina com
). Ideia: guardamos apenas se o último símbolo lido foi
ou não. Dois estados: “último não é b” e “último é b”. A palavra vazia não termina com
, então o estado inicial é o de “último não é b”. O estado de aceitação é “último é b”.
Formalmente:
onde
= o último símbolo lido não é
(ou ainda não lemos nada),
= o último símbolo lido foi
. A função de transição
é
Explicação didática: ao ler
vamos para o estado que lembra "termina com
"; ao ler
passamos para o estado que lembra "não termina com
".
Passo 4
Agora a parte importante: construir o AFD da interseção usando o produto cartesiano. Regra geral (produto de dois AFDs): se temos
então o AFD que reconhece
é
com
e a transição definida por
para todo
.
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
.
Listamos explicitamente os elementos:
o estado inicial é
e o conjunto de aceitação, por
, é
Agora calculemos as transições usando
. Temos:
Explicação didática com exemplo: comece em
. Para a palavra
: primeiro
leva a
(agora há um
, ímpar, e último símbolo não é
); depois
leva a
que é estado de aceitação — a palavra tem número ímpar de
e termina com
, OK.]
Passo 6
Verificação rápida: todos os quatro estados são alcançáveis a partir de
(por exemplo,
por
,
por
,
por
), e apenas
é de aceitação. Esse AFD reconhece exatamente as palavras que simultaneamente têm número ímpar de
e terminam em
.