Construa AFDs para reconhecer as seguintes linguagens:
\mathrm{w} \in{0,1} \mid w 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 \{0,1\} que têm comprimento ímpar e terminam em 1.\n
Informações relevantes fornecidas:
  • Alfabeto: \{0,1\}.
  • Condição que a palavra w deve satisfazer: comprimento de w é ímpar e o último símbolo de w é 1.
  • 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 1 precisamos saber duas informações ao mesmo tempo:
  1. Paridade do comprimento lido até agora: par (even) ou ímpar (odd).
  2. Qual é o último símbolo lido (se foi 0 ou 1) — isso importa porque queremos terminar em 1.\n
    Portanto, o autômato precisa distinguir as quatro combinações possíveis: \text{(paridade, último símbolo)} \in \{\text{even, odd}\}\times\{0,1\}úí. Assim construiremos 4 estados que codificam exatamente essas combinações.

Passo 3

Definimos formalmente o AFD M como a quíntupla M=(Q,\Sigma,\delta,q_0,F) com:
\Sigma=\{0,1\}
Q=\{\,q_{e,0},\; q_{e,1},\; q_{o,0},\; q_{o,1}\,\}
Aqui:
  • q_{e,0} representa "comprimento lido até agora é par e o último símbolo lido (se houver) é 0". Para conveniência o estado inicial terá essa interpretação para o prefixo vazio (comprimento 0 é par e tratamos o último símbolo como 0 arbitrariamente, pois vazio não será aceito de qualquer forma).
  • q_{e,1} representa "comprimento par e último símbolo é 1".
  • q_{o,0} representa "comprimento ímpar e último símbolo é 0".
  • q_{o,1} representa "comprimento ímpar e último símbolo é 1".\n
    Escolhemos o estado inicial
q_0 = q_{e,0}
e o conjunto de estados de aceitação
F=\{\,q_{o,1}\,\}
porque queremos aceitar exatamente as palavras cujo comprimento é ímpar e cujo último símbolo é 1.

Passo 4

Agora construímos a função de transição \delta. A regra intuitiva: ao ler um símbolo a\in\{0,1\} trocamos a paridade (par \leftrightarrow ímpar) e atualizamos “último símbolo” para a. Em forma de igualdade:
\delta(q_{e,0},0)=q_{o,0},\qquad \delta(q_{e,0},1)=q_{o,1},
\delta(q_{e,1},0)=q_{o,0},\qquad \delta(q_{e,1},1)=q_{o,1},
\delta(q_{o,0},0)=q_{e,0},\qquad \delta(q_{o,0},1)=q_{e,1},
\delta(q_{o,1},0)=q_{e,0},\qquad \delta(q_{o,1},1)=q_{e,1}.
Explicação simples: de qualquer estado cujo comprimento atual é par, ao ler 0 vamos para um estado de comprimento ímpar cujo último símbolo é 0 (ou seja, q_{o,0}); ao ler 1 vamos para q_{o,1}. Analogamente para estados de comprimento ímpar.

Passo 5

Verificação rápida por exemplos (para você treinar mentalmente na prova):
  • Palavra w=\epsilon (vazia): o autômato fica em q_{e,0} (não aceita), correto porque comprimento 0 não é ímpar.
  • Palavra w=1: transição q_{e,0}\xrightarrow{1}q_{o,1}. Estado final é q_{o,1}, que é de aceitação — aceita, correto (comprimento 1 ímpar e termina em 1).
  • Palavra w=0: q_{e,0}\xrightarrow{0}q_{o,0} não-aceita — correto (comprimento ímpar mas termina em 0).
  • Palavra w=101: sequência q_{e,0}\xrightarrow{1}q_{o,1}\xrightarrow{0}q_{e,0}\xrightarrow{1}q_{o,1} termina em q_{o,1} — aceita; 101 tem comprimento 3 (ímpar) e termina em 1.

Passo 6

Prova de correção por invariante (esqueleto para a prova escrita):
Base: para a palavra vazia \epsilon estamos em q_{e,0}; isso corresponde corretamente a "comprimento par (0) e último símbolo tratado como 0".
Passo indutivo: suponha que após ler x o autômato está no estado que representa (\text{paridade}(|x|), \text{último}(x))ú. Ao ler um símbolo a obtemos xa; a paridade de |xa| é a paridade oposta de |x|, e o último símbolo de xa é a. As transições definidas enviam exatamente o estado correspondente a (\text{paridade}(|x|),\text{último}(x))ú para aquele correspondente a (\text{paridade}(|xa|),a). Logo a invariante é mantida. Com isso, no final da leitura uma palavra w é aceita sse o estado final é q_{o,1}, i.e., sse |w| é ímpar e o último símbolo de w é 1. Assim o AFD reconhece exatamente a linguagem pedida.

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 1 e 0 (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

M=(Q,\Sigma,\delta,q_0,F) com
\Sigma=\{0,1\},
Q=\{q_{e,0},q_{e,1},q_{o,0},q_{o,1}\},
q_0=q_{e,0},\qquad F=\{q_{o,1}\},
e \delta dada por
\delta(q_{e,0},0)=q_{o,0},\quad \delta(q_{e,0},1)=q_{o,1},
\delta(q_{e,1},0)=q_{o,0},\quad \delta(q_{e,1},1)=q_{o,1},
\delta(q_{o,0},0)=q_{e,0},\quad \delta(q_{o,0},1)=q_{e,1},
\delta(q_{o,1},0)=q_{e,0},\quad \delta(q_{o,1},1)=q_{e,1}.

Exercícios relacionados