Construa os seguintes AFDs para reconhecer as intersecção entre as linguagens solicitadas, todo os alfabetos são
:
tem tamanho par e um número ímpar de “a”}.
Passo 1
O que o enunciado pede e o que ele dá:
- O alfabeto é
. - Queremos um AFD que reconheça a linguagem formada por todas as palavras
tais que: -
tem tamanho par (ou seja, o número de símbolos de é par); -
tem um número ímpar de .
-
- Em outras palavras, a linguagem é a interseção de duas propriedades: “tamanho par” e "número ímpar de
". 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
: já li um número par de símbolos (começa aqui, pois a palavra vazia tem comprimento , que é par). - Estado
: já li um número ímpar de símbolos.
- Estado
- Transições:
- Ao ler qualquer símbolo (
ou ) alternamos entre e (pois cada símbolo altera a paridade do comprimento).
- Ao ler qualquer símbolo (
- Estado inicial:
. - Estado de aceitação:
(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
".
- Ideia: só precisamos lembrar a paridade da quantidade de
s lidas. Novamente usamos dois estados. - Definição informal:
- Estado
: já li um número par de s (começa aqui, pois zero é par). - Estado
: já li um número ímpar de s.
- Estado
- Transições:
- Ao ler
: alternamos entre e (pois cada muda a paridade da contagem de s). - Ao ler
: permanecemos no mesmo estado (pois não altera a contagem de s).
- Ao ler
- Estado inicial:
. - Estado de aceitação:
(porque queremos número ímpar de s). - Observação didática: este AFD também tem 2 estados; apenas a leitura de
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
com e . Vamos renomear para ficar prático e curto: -
— comprimento par, número de par. -
— comprimento par, número de ímpar. -
— comprimento ímpar, número de par. -
— comprimento ímpar, número de ímpar.
-
- Estado inicial do produto:
(vazio: comprimento par e zero s). - Estados de aceitação do produto: somente aqueles pares que satisfazem ambas as propriedades: comprimento par E número ímpar de
s. Logo o único estado de aceitação é . - Regra de transição do produto (explicação): para cada símbolo
, 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
e ). - Ler
altera a paridade do número de s; ler não altera essa paridade.
- Ler qualquer símbolo altera a paridade do comprimento (alternância entre
- Usando essa ideia, calculamos as transições para cada estado par:
- A partir de
: - lendo
: comprimento troca para ímpar, número de fica ímpar → vai para . - lendo
: comprimento troca para ímpar, número de permanece par → vai para .
- lendo
- A partir de
: - lendo
: comprimento → ímpar, contagem de troca para par → vai para . - lendo
: comprimento → ímpar, contagem de permanece ímpar → vai para .
- lendo
- A partir de
: - lendo
: comprimento → par, contagem de → ímpar → vai para . - lendo
: comprimento → par, contagem de permanece par → vai para .
- lendo
- A partir de
: - lendo
: comprimento → par, contagem de → par → vai para . - lendo
: comprimento → par, contagem de permanece ímpar → vai para .
- lendo
- A partir de
- Observação didática com um exemplo prático:
- Tome a palavra
“ab”. Percurso: - start
— ler → — ler → . -
é de aceitação, então “ab” é aceita (tem comprimento par e uma — ímpar).
- start
- Tome
“aba”: percurso: -
. -
não é de aceitação → “aba” rejeitada (comprimento 3 ímpar).
-
- Tome a palavra
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:
- Alfabeto:
- Função de transição
dada pela tabela abaixo (já justificada no passo anterior): - Estado inicial:
- Conjunto de estados de aceitação:
- Conjunto de estados:
- Observação final e incentivo: esse AFD reconhece exatamente as palavras com comprimento par e número ímpar de
. 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 ) e combiná-las.