Construa AFNs para reconhecer as seguintes linguagens:
tem tamanho 3 e cada caractere aparece uma única vez
.
tem tamanho 3 e cada caractere aparece uma única vez .
Passo 1
O enunciado pede um autômato finito não-determinístico (AFN) que reconheça todas as palavras sobre o alfabeto
que têm tamanho
e em que cada símbolo aparece exatamente uma vez.
Informações relevantes extraídas do enunciado:
Informações relevantes extraídas do enunciado:
Portanto a linguagem é exatamente o conjunto das permutações de
:
Passo 2
Breve explicação do que vamos construir (sem ainda construir): uma maneira direta e confiável de reconhecer um conjunto finito de palavras é construir um “trie” (árvore de prefixos) que aceita exatamente essas palavras. Esse trie pode ser visto como um AFN (na verdade é um AFD também) onde seguimos transições de acordo com cada letra lida e somente chegamos num estado final se a sequência lida corresponde a uma das palavras desejadas. Vou usar esse método porque é simples, não requer raciocínio complexo durante a prova e é fácil de desenhar e provar correto.
Passo 3
Definição formal do tipo de autômato que usarei (explicando cada componente):
Um AFN (autômato finito não-determinístico) é uma tupla
Um AFN (autômato finito não-determinístico) é uma tupla
onde:
Explicação das variáveis: por exemplo,
significa que estando em
e lendo a letra
o autômato pode ir para
ou para
. Para nosso caso particular podemos usar um AFN determinístico (cada transição dá um único próximo estado) — isso é permitido porque todo DFA é também um AFN.
Passo 4
Construção do trie — primeiros níveis (letras iniciais):
- Estado inicial:
. - Para a primeira letra temos três possibilidades: ler
ou .
Criaremos três estados alcançáveis a partir de:
Aqui
representa que já lemos um
no prefixo,
que já lemos um
, e
que já lemos um
.
Passo 5
Construção do trie — segundo símbolo para o caso em que a primeira letra foi
:
Se o prefixo é (estado
), a segunda letra pode ser somente
ou
(não pode ser
de novo). Então:
Se o prefixo é
Os estados
e
representam os prefixos
e
, respectivamente.
Passo 6
Construção do trie — terceiro símbolo para os prefixos iniciados por
:
- A partir de
(prefixo ) a terceira letra válida é somente :
- A partir de
(prefixo ) a terceira letra válida é somente :
Os estados
e
serão estados finais que aceitam, respectivamente,
e
.
Passo 7
Construção do trie — ramos iniciados por
(simétrico ao caso de
):
- Segunda letra a partir de
:
- Terceira letra:
Passo 8
Construção do trie — ramos iniciados por
(simétrico também):
- Segunda letra a partir de
:
- Terceira letra:
Passo 9
Resumo e verificação por exemplo (mostrando como o autômato aceita uma palavra):
Considere a palavra .
Considere a palavra
Como
é final, a palavra
é aceita. Analogamente qualquer permutação de
segue um caminho pelo trie até um dos estados finais correspondentes; qualquer palavra que repita símbolo ou tenha símbolo extra não chega a um estado final.
Passo 10
Observações finais e alternativa curta:
- O autômato que construí é efetivamente um DFA (cada par
leva a no máximo um próximo estado) — isso é totalmente permitido; todo DFA é também um AFN. - Como a linguagem é finita e pequena, a construção em forma de trie é prática e diretamente justificável na prova: mostre os estados, transições e os estados finais, e explique que cada caminho de comprimento
até um estado final corresponde a uma das permutações.
Resposta
(Transições não mencionadas são vazias.)