Construa AFNs para reconhecer as seguintes linguagens:
{w \in{a, b, c} \mid w 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 \{a,b,c\} que têm tamanho 3 e em que cada símbolo aparece exatamente uma vez.
Informações relevantes extraídas do enunciado:
\begin{aligned} &\text{Alfabeto: }\Sigma=\{a,b,c\}.\\\ &\text{Comprimento das cadeias: }|w|=3.\\\ &\text{Condicional: cada símbolo aparece exatamente uma única vez em }w. \end{aligned}íú
Portanto a linguagem é exatamente o conjunto das permutações de \{a,b,c\}:
\{abc,\,acb,\,bac,\,bca,\,cab,\,cba\}.

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
M=(Q,\Sigma,\delta,q_0,F),
onde:
\begin{aligned} &Q\\ \text{é o conjunto finito de estados;}\\\ &\Sigma\\ \text{é o alfabeto;}\\\ &\delta:Q\times\Sigma\to\mathcal{P}(Q)\\ \text{é a função de transição (mapa para conjuntos de estados);}\\\ &q_0\in Q\\ \text{é o estado inicial;}\\\ &F\subseteq Q\\ \text{é o conjunto de estados finais (aceitação).} \end{aligned}éééçãçãééçã
Explicação das variáveis: por exemplo, \delta(q,a)=\{p,r\} significa que estando em q e lendo a letra a o autômato pode ir para p ou para r. 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: q_0.
  • Para a primeira letra temos três possibilidades: ler \,a\,,\;b ou \,c.
    Criaremos três estados alcançáveis a partir de q_0:
\begin{aligned} &\delta(q_0,a)=\{q_1\},\\\ &\delta(q_0,b)=\{q_4\},\\\ &\delta(q_0,c)=\{q_7\}. \end{aligned}
Aqui \,q_1 representa que já lemos um \,a no prefixo, \,q_4 que já lemos um \,b, e \,q_7 que já lemos um \,c.

Passo 5

Construção do trie — segundo símbolo para o caso em que a primeira letra foi \,a:
Se o prefixo é \,a (estado q_1), a segunda letra pode ser somente \,b ou \,c (não pode ser \,a de novo). Então:
\begin{aligned} &\delta(q_1,b)=\{q_2\},\\\ &\delta(q_1,c)=\{q_3\}. \end{aligned}
Os estados q_2 e q_3 representam os prefixos \,ab e \,ac, respectivamente.

Passo 6

Construção do trie — terceiro símbolo para os prefixos iniciados por \,a:
  • A partir de q_2 (prefixo \,ab) a terceira letra válida é somente \,c:
\delta(q_2,c)=\{q_{f1}\}.
  • A partir de q_3 (prefixo \,ac) a terceira letra válida é somente \,b:
\delta(q_3,b)=\{q_{f2}\}.
Os estados q_{f1} e q_{f2} serão estados finais que aceitam, respectivamente, \,abc e \,acb.

Passo 7

Construção do trie — ramos iniciados por \,b (simétrico ao caso de \,a):
  • Segunda letra a partir de q_4:
\begin{aligned} &\delta(q_4,a)=\{q_5\},\\\ &\delta(q_4,c)=\{q_6\}. \end{aligned}
  • Terceira letra:
\begin{aligned} &\delta(q_5,c)=\{q_{f3}\}\quad\text{(aceita \(\,bac\))},\\ &\delta(q_6,a)=\{q_{f4}\}\quad\text{(aceita \(\,bca\))}. \end{aligned}

Passo 8

Construção do trie — ramos iniciados por \,c (simétrico também):
  • Segunda letra a partir de q_7:
\begin{aligned} &\delta(q_7,a)=\{q_8\},\\\ &\delta(q_7,b)=\{q_9\}. \end{aligned}
  • Terceira letra:
\begin{aligned} &\delta(q_8,b)=\{q_{f5}\}\quad\text{(aceita \(\,cab\))},\\ &\delta(q_9,a)=\{q_{f6}\}\quad\text{(aceita \(\,cba\))}. \end{aligned}

Passo 9

Resumo e verificação por exemplo (mostrando como o autômato aceita uma palavra):
Considere a palavra \,bac.
\begin{aligned} &\text{Começamos em }q_0.\\\ &\text{Lendo }b:\\ \delta(q_0,b)=\{q_4\}.\\\ &\text{Lendo }a:\\ \delta(q_4,a)=\{q_5\}.\\\ &\text{Lendo }c:\\ \delta(q_5,c)=\{q_{f3}\}. \end{aligned}ç
Como q_{f3} é final, a palavra \,bac é aceita. Analogamente qualquer permutação de \{a,b,c\} 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 (estado, símbolo)í 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 3 até um estado final corresponde a uma das 6 permutações.

Resposta

M=(Q,\Sigma,\delta,q_0,F)
\Sigma=\{a,b,c\}
\begin{aligned} Q=\{&q_0,q_1,q_2,q_3,q_4,q_5,q_6,q_7,q_8,q_9,\\\ &q_{f1},q_{f2},q_{f3},q_{f4},q_{f5},q_{f6}\} \end{aligned}
(Transições não mencionadas são vazias.)
\begin{aligned} &\delta(q_0,a)=\{q_1\},\quad \delta(q_0,b)=\{q_4\},\quad \delta(q_0,c)=\{q_7\};\\\ &\delta(q_1,b)=\{q_2\},\quad \delta(q_1,c)=\{q_3\};\\\ &\delta(q_2,c)=\{q_{f1}\};\quad \text{(accepts }abc\text{)}\\\ &\delta(q_3,b)=\{q_{f2}\};\quad \text{(accepts }acb\text{)}\\\ &\delta(q_4,a)=\{q_5\},\quad \delta(q_4,c)=\{q_6\};\\\ &\delta(q_5,c)=\{q_{f3}\};\quad \text{(accepts }bac\text{)}\\\ &\delta(q_6,a)=\{q_{f4}\};\quad \text{(accepts }bca\text{)}\\\ &\delta(q_7,a)=\{q_8\},\quad \delta(q_7,b)=\{q_9\};\\\ &\delta(q_8,b)=\{q_{f5}\};\quad \text{(accepts }cab\text{)}\\\ &\delta(q_9,a)=\{q_{f6}\};\quad \text{(accepts }cba\text{)} \end{aligned}
q_0\\ \text{é o estado inicial}é
F=\{q_{f1},q_{f2},q_{f3},q_{f4},q_{f5},q_{f6}\}

Exercícios relacionados