Construa um AFD , com alfabeto Σ={0,1}, que aceitam as linguagens:
{O símbolo mais a esquerda é diferente do símbolo mais a direita}.

Passo 1

O enunciado pede: construir um autômato finito determinístico (AFD) sobre o alfabeto \Sigma=\{0,1\} que aceita exatamente as palavras cuja primeira (mais à esquerda) e última (mais à direita) símbolos são diferentes. Informações relevantes fornecidas:
\Sigma=\{0,1\}.
A condição de aceitação: o símbolo mais à esquerda é diferente do símbolo mais à direita.
Observações importantes que vou usar (sem resolver ainda): a cadeia vazia \varepsilon não tem primeiro nem último símbolo, então não pertence à linguagem; uma cadeia de comprimento 1 tem primeiro igual ao último, logo deve ser rejeitada.

Passo 2

Ideia geral da construção (explicada passo a passo, com intuição):
Para decidir se o primeiro símbolo difere do último, o autômato precisa lembrar qual foi o primeiro símbolo lido e, enquanto lê, ir atualizando qual é o símbolo atual (que, ao final da leitura, será o último símbolo). Como só há dois símbolos possíveis, podemos guardar essa informação em estados do autômato: “primeiro = 0, último = 0”, “primeiro = 0, último = 1”, “primeiro = 1, último = 0” e “primeiro = 1, último = 1”. Também precisamos de um estado inicial onde ainda não lemos nada (para distinguir a entrada vazia). No fim a palavra é aceita exatamente quando primeiro e último são diferentes, ou seja, quando estamos em estados do tipo \text{(0,1)} ou \text{(1,0)}.

Passo 3

Definição formal do AFD e explicação de cada componente (a “aula” sobre o que cada parte significa):
Um AFD é uma quíntupla (Q,\Sigma,\delta,q_0,F), onde:
  • Q é o conjunto finito de estados;
  • \Sigma é o alfabeto de entrada ( \{0,1\} aqui);
  • \delta: Q\times\Sigma\to Q é a função de transição (diz para qual estado ir ao ler um símbolo);
  • q_0\in Q é o estado inicial (onde começamos antes de ler qualquer símbolo);
  • F\subseteq Q é o conjunto de estados de aceitação (se a leitura terminar em um desses estados, a palavra é aceita).
    Vou escolher os estados para representar explicitamente o par (primeiro, último) e um estado inicial sem símbolo lido.

Passo 4

Escolha dos estados e seu significado (explicando por que cada um existe):
Defino os estados seguintes (explicando o que cada nome significa):
  • q_{start}: estado inicial, ainda não lemos nenhum símbolo.
  • s_{0,0}: significa “primeiro símbolo lido = 0” e “último símbolo lido até agora = 0”.
  • s_{0,1}: significa “primeiro = 0” e “último = 1”.
  • s_{1,0}: significa “primeiro = 1” e “último = 0”.
  • s_{1,1}: significa “primeiro = 1” e “último = 1”.
    Intuição: assim que lemos o primeiro símbolo, saímos de q_{start} para um dos estados correspondentes ao par (primeiro,último)ú. Depois disso, cada novo símbolo somente atualiza o componente “último” do par.

Passo 5

Construção explícita da função de transição \delta (mostrando cada caso e explicando a lógica):
  1. Transições a partir do estado inicial q_{start} (a leitura do primeiro símbolo):
  • Se do estado q_{start} lemos \,0, então o primeiro símbolo é 0 e o último lido passa a ser 0:
\delta(q_{start},0)=s_{0,0}.
  • Se do estado q_{start} lemos \,1, então o primeiro símbolo é 1 e o último lido passa a ser 1:
\delta(q_{start},1)=s_{1,1}.
  1. Transições em estados que já têm primeiro=0:
  • No estado s_{0,0}: ao ler 0 o último continua 0, ao ler 1 o último vira 1:
\delta(s_{0,0},0)=s_{0,0},\qquad \delta(s_{0,0},1)=s_{0,1}.
  • No estado s_{0,1}: ao ler 0 o último vira 0, ao ler 1 o último fica 1:
\delta(s_{0,1},0)=s_{0,0},\qquad \delta(s_{0,1},1)=s_{0,1}.
  1. Transições em estados que já têm primeiro=1:
  • No estado s_{1,1}: ao ler 1 o último continua 1, ao ler 0 o último vira 0:
\delta(s_{1,1},1)=s_{1,1},\qquad \delta(s_{1,1},0)=s_{1,0}.
  • No estado s_{1,0}: ao ler 1 o último vira 1, ao ler 0 o último fica 0:
\delta(s_{1,0},1)=s_{1,1},\qquad \delta(s_{1,0},0)=s_{1,0}.
Explicação curta: cada transição mantém o componente “primeiro” e atualiza o componente “último” para o símbolo que acabamos de ler.

Passo 6

Definição do estado inicial e dos estados de aceitação:
  • Estado inicial: q_0 = q_{start}.
  • Conjunto de aceitação F: queremos aceitar exatamente quando o primeiro símbolo for diferente do último. Portanto aceitaremos os estados:
F = \{\,s_{0,1},\; s_{1,0}\,\}.
Observação: q_{start} não é de aceitação (rejeitamos \varepsilon); s_{0,0} e s_{1,1} também não são de aceitação (palavras de comprimento 1 ou cujo primeiro = último são rejeitadas).

Passo 7

Prova de correção (por que esse autômato reconhece exatamente a linguagem pedida):
Invariante útil: após ler pelo menos um símbolo, o autômato estará em um dos estados s_{a,b} e esse estado representa corretamente que o primeiro símbolo lido foi a e o último símbolo lido até agora é b. Demonstração por indução:
  • Base: após um símbolo lido a partir de q_{start}, as transições foram projetadas para ir a s_{0,0} ou s_{1,1}, correspondendo ao primeiro e último igual ao símbolo lido.
  • Passo indutivo: suponha que após ler n\ge1 símbolos estamos em s_{a,b} com a = primeiro e b = último. Ao ler o (n+1)-ésimo símbolo x\in\{0,1\}, as transições levam para s_{a,x}, ou seja, mantém o primeiro a e atualiza o último para x. Logo a invariante se mantém.
    No fim da palavra, o estado estará em s_{a,b} (se lemos pelo menos 1 símbolo). O autômato aceita exatamente se a\neq b, que é a condição desejada. O caso da palavra vazia termina em q_{start}, que não é de aceitação, conforme desejado.

Passo 8

Exemplos de execução (mostrando passo a passo para fixar):
  1. Palavra \,0: \,q_{start}\xrightarrow{0}s_{0,0}. Fim em s_{0,0} (não aceitante) → rejeita. (Corresponde: primeiro = último = 0 → rejeitar.)
  2. Palavra \,01: q_{start}\xrightarrow{0}s_{0,0}\xrightarrow{1}s_{0,1}. Fim em s_{0,1} (aceitante) → aceita. (Primeiro = 0, último = 1 → aceitar.)
  3. Palavra \,1010: q_{start}\xrightarrow{1}s_{1,1}\xrightarrow{0}s_{1,0}\xrightarrow{1}s_{1,1}\xrightarrow{0}s_{1,0}. Fim em s_{1,0} (aceitante) → aceita. (Primeiro = 1, último = 0.)
  4. Palavra vazia \varepsilon: começa e termina em q_{start} → rejeita.

Passo 9

Comentário sobre minimalidade (curtinho, só pra você saber):
Esse autômato usa 5 estados (incluindo o inicial que representa “ainda não li nada”). É possível mostrar que precisamos de pelo menos 3 estados para distinguir palavras de comprimento 0,1 e ≥2 com tipos distintos de primeiros/últimos; a construção com 4 estados pós-inicial é natural e direta. Para a prova prática da sua disciplina, essa construção é clara e suficiente.

Resposta

\text{AFD }M=(Q,\Sigma,\delta,q_0,F)
Q=\{q_{start},\,s_{0,0},\,s_{0,1},\,s_{1,0},\,s_{1,1}\}
\Sigma=\{0,1\}
q_0=q_{start}
F=\{s_{0,1},\,s_{1,0}\}
\begin{aligned} \delta(q_{start},0)&=s_{0,0}, &\delta(q_{start},1)&=s_{1,1},\\\ \delta(s_{0,0},0)&=s_{0,0}, &\delta(s_{0,0},1)&=s_{0,1},\\\ \delta(s_{0,1},0)&=s_{0,0}, &\delta(s_{0,1},1)&=s_{0,1},\\\ \delta(s_{1,1},0)&=s_{1,0}, &\delta(s_{1,1},1)&=s_{1,1},\\\ \delta(s_{1,0},0)&=s_{1,0}, &\delta(s_{1,0},1)&=s_{1,1}. \end{aligned}

Exercícios relacionados