Construa AFDs para reconhecer as seguintes linguagens:
de tamanho ímpar terminadas em 1
.
Passo 1
O enunciado pede: construir um autômato finito determinístico (AFD) que reconheça a linguagem de todas as palavras sobre o alfabeto
que têm comprimento ímpar e terminam em
.\n
Informações relevantes fornecidas:
Informações relevantes fornecidas:
- Alfabeto:
. - Condição que a palavra
deve satisfazer: comprimento de é ímpar e o último símbolo de é . - Queremos um AFD (determinístico), ou seja, um autômato com transição única definida para cada par (estado, símbolo).
Passo 2
Ideia geral e memória que o AFD precisa guardar: um AFD tem memória limitada via estados. Para decidir se uma palavra tem comprimento ímpar e termina em
precisamos saber duas informações ao mesmo tempo:
- Paridade do comprimento lido até agora: par (even) ou ímpar (odd).
- Qual é o último símbolo lido (se foi
ou ) — isso importa porque queremos terminar em .\n
Portanto, o autômato precisa distinguir as quatro combinações possíveis:. Assim construiremos 4 estados que codificam exatamente essas combinações.
Passo 3
Definimos formalmente o AFD
como a quíntupla
com:
Aqui:
-
representa "comprimento lido até agora é par e o último símbolo lido (se houver) é ". Para conveniência o estado inicial terá essa interpretação para o prefixo vazio (comprimento é par e tratamos o último símbolo como arbitrariamente, pois vazio não será aceito de qualquer forma). -
representa "comprimento par e último símbolo é ". -
representa "comprimento ímpar e último símbolo é ". -
representa "comprimento ímpar e último símbolo é ".\n
Escolhemos o estado inicial
e o conjunto de estados de aceitação
porque queremos aceitar exatamente as palavras cujo comprimento é ímpar e cujo último símbolo é
.
Passo 4
Agora construímos a função de transição
. A regra intuitiva: ao ler um símbolo
trocamos a paridade (par
ímpar) e atualizamos “último símbolo” para
. Em forma de igualdade:
Explicação simples: de qualquer estado cujo comprimento atual é par, ao ler
vamos para um estado de comprimento ímpar cujo último símbolo é
(ou seja,
); ao ler
vamos para
. Analogamente para estados de comprimento ímpar.
Passo 5
Verificação rápida por exemplos (para você treinar mentalmente na prova):
- Palavra
(vazia): o autômato fica em (não aceita), correto porque comprimento não é ímpar. - Palavra
: transição . Estado final é , que é de aceitação — aceita, correto (comprimento ímpar e termina em ). - Palavra
: não-aceita — correto (comprimento ímpar mas termina em ). - Palavra
: sequência termina em — aceita; tem comprimento (ímpar) e termina em .
Passo 6
Prova de correção por invariante (esqueleto para a prova escrita):
Base: para a palavra vazia estamos em
; isso corresponde corretamente a "comprimento par (0) e último símbolo tratado como
".
Passo indutivo: suponha que após ler o autômato está no estado que representa
. Ao ler um símbolo
obtemos
; a paridade de
é a paridade oposta de
, e o último símbolo de
é
. As transições definidas enviam exatamente o estado correspondente a
para aquele correspondente a
. Logo a invariante é mantida. Com isso, no final da leitura uma palavra
é aceita sse o estado final é
, i.e., sse
é ímpar e o último símbolo de
é
. Assim o AFD reconhece exatamente a linguagem pedida.
Base: para a palavra vazia
Passo indutivo: suponha que após ler
Passo 7
Comentários de minimalidade (opcional, mas útil na prova): precisamos distinguir ao menos 4 classes de sufixos porque as propriedades “paridade” e “último símbolo” são independentes; por exemplo, as palavras
e
(ambas ímpares) não são equivalentes porque ao anexar a palavra vazia uma é aceita e outra não. Com argumentos do tipo Myhill–Nerode (escolhendo sufíxos que mostram distinção) conclui-se que 4 estados são necessários e suficientes; nosso AFD com 4 estados é portanto mínimo.
Resposta
e
dada por