Construa os seguintes AFDs para reconhecer as intersecção entre as linguagens solicitadas, todo os alfabetos são
:
tem exatamente dois “a” e pelo menos dois “b” }.
Passo 1
O que o enunciado pede: construir um AFD que reconheça a linguagem de todas as palavras
sobre o alfabeto
tais que
tem exatamente dois
e pelo menos dois
.
Informações relevantes dadas:
- Alfabeto:
. - Condições simultâneas (intersecção):
- exatamente dois
; - pelo menos dois
.
- exatamente dois
Passo 2
Ideia geral de construção (sem detalhes ainda): para reconhecer a intersecção de duas condições sobre contas de símbolos, um caminho natural é construir dois AFDs simples que testem cada condição separadamente e depois formar o AFD produto (autômato composto) para a intersecção. Vou explicar cada autômato simples e depois a construção do produto passo a passo.
Breve lembrete sobre AFDs (didático): um AFD é definido por um quíntuplo
, onde
é o conjunto de estados,
o alfabeto,
a função de transição,
o estado inicial e
o conjunto de estados finais. Para contar ocorrências limitadas de um símbolo, usamos estados que representam “quantos já vimos até agora” (ex.: 0,1,2, e um estado que indica “mais que 2”).
Passo 3
Construção do AFD que reconhece “exatamente dois
” (vou chamar de
).
Definição do autômato
:
Interpretação dos estados:
-
: já vimos letras ; -
: já vimos letra ; -
: já vimos exatamente letras ; -
: já vimos mais de letras (estado “sink” para excesso).
Estado inicial:
Estados finais:
Função de transição
(explicação: ler uma
incrementa o contador; ler
deixa contador de
inalterado):
Motivação curta: aceitar somente se, ao final da leitura, estivermos em
(exatamente duas
). Se exceder duas
, vamos para
que é não-aceitante.
Passo 4
Construção do AFD que reconhece “pelo menos dois
” (vou chamar de
).
Definição do autômato
:
Interpretação dos estados:
-
: já vimos letras ; -
: já vimos letra ; -
: já vimos pelo menos letras (estado absorbente).
Estado inicial:
Estados finais:
Função de transição
(explicação: ler uma
incrementa o contador de
; ler
não altera o contador de
):
Motivação curta: aceitar se ao final estivermos em
, que significa “já vi pelo menos duas
”.
Passo 5
Construção do AFD produto
que reconhece a intersecção “exatamente dois
E pelo menos dois
”.
Regra do produto (explicação didática): os estados de
são pares
onde
é um estado de
e
é um estado de
. A leitura de um símbolo atualiza ambos os componentes simultaneamente usando as suas respectivas funções de transição. Aceitamos exatamente quando ambos os autômatos componentes estariam em estados finais.
Definição do produto
:
Estado inicial:
Conjunto de estados finais (intersecção dos finais):
Função de transição
(regra componente a componente):
para todo
.
Exemplos para fixar a ideia:
Observação sobre número de estados:
tem
estados. Desses, apenas o estado
é final. Estados com
(mais de duas
) nunca serão finais — servem como “sumidouro” para palavras com muitas
.
Passo 6
Comentário prático para a prova (útil e motivador): se precisar desenhar o autômato no caderno, você pode desenhar os 12 estados como uma grade
(linhas para o contador de
, colunas para o contador de
) e desenhar as setas segundo a regra componente-a-componente. Outra opção prática é simplesmente descrever o autômato produto pela regra geral dada em
, porque isso já é uma especificação formal válida para um AFD.
Algumas palavras-testes (verificação rápida):
-
(por exemplo, ) tem exatamente duas e duas → aceita. -
( ) tem duas e duas → aceita. -
( ) tem duas mas só uma → rejeita. -
( ) tem duas e três → aceita. -
( ) tem três → rejeita.
Resposta
e para todo
e todo
vale
onde
e
são dadas por