) Desenvolva Autômatos Finitos Determinísticos que reconheçam as seguintes linguagens sobre
: (cada resposta correta vale 1,0 ponto)
sufixo de
é
sufixo de
Passo 1
O enunciado dá a seguinte informação:
- Alfabeto:
. - Linguagem pedida: o conjunto de todas as palavras
tal que o sufixo de é ; em outras palavras, todas as palavras que terminam com as duas letras .
O que é pedido:
- Desenvolver um Autômato Finito Determinístico (AFD) que reconheça exatamente essa linguagem.
Passo 2
Ideia-chave (explicada devagar e com calma):
- Para decidir se uma palavra termina em
basta observar as últimas duas letras lidas. Logo o autômato só precisa “lembrar” até as duas últimas letras. - Vamos representar essa lembrança por estados: um estado para “nenhuma
recente” (ou seja, a última letra não é ), um estado para “a última letra foi (mas ainda não duas )” e um estado de aceitação para "as duas últimas letras lidas são ". - Esse raciocínio já sugere que três estados são suficientes e necessários: 0
final, 1 final, 2 finais.
Passo 3
Definição formal do autômato (anotando o que cada símbolo significa):
-
será o conjunto de estados. -
é o alfabeto. -
é a função de transição. -
é o estado inicial. -
é o conjunto de estados de aceitação.
Escolha concreta dos estados (com interpretação):
-
: não há chegando ao fim (ou seja, a última letra lida não é , ou ainda a palavra é vazia). -
: a última letra lida foi , mas as duas últimas não são . -
: as duas últimas letras lidas são (estado de aceitação).
Portanto:
Passo 4
Definir a função de transição
e justificar cada caso (explicação didática):
- Se estou em
(último símbolo não é ou palavra vazia): - ao ler
a última letra passa a ser , então vou para ; - ao ler
continuo sem no fim, fico em .
- ao ler
- Se estou em
(última letra foi ): - ao ler
agora as duas últimas são , vou para ; - ao ler
a sequência é “quebrada” por , volto para .
- ao ler
- Se estou em
(últimas duas letras são ): - ao ler
as duas últimas ainda serão (a nova última e a anterior continuam ), então permaneço em ; - ao ler
a sequência final deixa de terminar em , volto para .
- ao ler
Escrevendo
de forma direta:
Passo 5
Verificação por exemplos (mostrando passo a passo as leituras, para aprender a usar o autômato na prova):
- Palavra
: - começo em
, - leio primeira
: , - leio segunda
: , - termino em
que é de aceitação → aceita (correto).
- começo em
- Palavra
: -
, -
, -
, - termino em
(não aceito) → correta, não termina em .
-
- Palavra
: -
, -
, -
, - termino em
→ aceita.
-
Passo 6
Propriedades finais e observações para a prova:
- O autômato é determinístico: para cada par (estado, símbolo) há exatamente uma transição definida.
- É completo:
está definida para todos os e para ambos os símbolos . - Minimalidade (intuição): não é possível ter menos de três estados porque é preciso distinguir entre as situações “nenhuma
recente”, “uma recente” e “duas recentes”. Formalmente, existem palavras que exigem que esses três estados sejam distinguíveis por extensão (por exemplo, distinguir , e com sufixos adicionados). - Dica prática para a prova: desenhe os três estados em linha:
--a–> --a–> (aceitável), com setas de retorno por para e laço em por . Isso é rápido e claro num gabarito.