Construa um AFD , com alfabeto
, que aceitam as linguagens:
{O símbolo mais a esquerda é diferente do símbolo mais a direita}.
{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
que aceita exatamente as palavras cuja primeira (mais à esquerda) e última (mais à direita) símbolos são diferentes. Informações relevantes fornecidas:
.
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 não tem primeiro nem último símbolo, então não pertence à linguagem; uma cadeia de comprimento
tem primeiro igual ao último, logo deve ser rejeitada.
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
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 ou
.
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
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 , onde:
Um AFD é uma quíntupla
-
é o conjunto finito de estados; -
é o alfabeto de entrada ( aqui); -
é a função de transição (diz para qual estado ir ao ler um símbolo); -
é o estado inicial (onde começamos antes de ler qualquer símbolo); -
é 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):
Defino os estados seguintes (explicando o que cada nome significa):
-
: estado inicial, ainda não lemos nenhum símbolo. -
: significa “primeiro símbolo lido = 0” e “último símbolo lido até agora = 0”. -
: significa “primeiro = 0” e “último = 1”. -
: significa “primeiro = 1” e “último = 0”. -
: significa “primeiro = 1” e “último = 1”.
Intuição: assim que lemos o primeiro símbolo, saímos depara um dos estados correspondentes ao par . 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
(mostrando cada caso e explicando a lógica):
- Transições a partir do estado inicial
(a leitura do primeiro símbolo):
- Se do estado
lemos , então o primeiro símbolo é e o último lido passa a ser :
- Se do estado
lemos , então o primeiro símbolo é e o último lido passa a ser :
- Transições em estados que já têm
:
- No estado
: ao ler o último continua , ao ler o último vira :
- No estado
: ao ler o último vira , ao ler o último fica :
- Transições em estados que já têm
:
- No estado
: ao ler o último continua , ao ler o último vira :
- No estado
: ao ler o último vira , ao ler o último fica :
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:
. - Conjunto de aceitação
: queremos aceitar exatamente quando o primeiro símbolo for diferente do último. Portanto aceitaremos os estados:
Observação:
não é de aceitação (rejeitamos
);
e
também não são de aceitação (palavras de comprimento
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 e esse estado representa corretamente que o primeiro símbolo lido foi
e o último símbolo lido até agora é
. Demonstração por indução:
Invariante útil: após ler pelo menos um símbolo, o autômato estará em um dos estados
- Base: após um símbolo lido a partir de
, as transições foram projetadas para ir a ou , correspondendo ao primeiro e último igual ao símbolo lido. - Passo indutivo: suponha que após ler
símbolos estamos em com = primeiro e = último. Ao ler o -ésimo símbolo , as transições levam para , ou seja, mantém o primeiro e atualiza o último para . Logo a invariante se mantém.
No fim da palavra, o estado estará em(se lemos pelo menos 1 símbolo). O autômato aceita exatamente se , que é a condição desejada. O caso da palavra vazia termina em , que não é de aceitação, conforme desejado.
Passo 8
Exemplos de execução (mostrando passo a passo para fixar):
- Palavra
: . Fim em (não aceitante) → rejeita. (Corresponde: primeiro = último = 0 → rejeitar.) - Palavra
: . Fim em (aceitante) → aceita. (Primeiro = 0, último = 1 → aceitar.) - Palavra
: . Fim em (aceitante) → aceita. (Primeiro = 1, último = 0.) - Palavra vazia
: começa e termina em → 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.
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.