Construa AFNs para reconhecer as seguintes linguagens:
{\mathrm{w} \in{\mathrm{a}, \mathrm{b}} \mid onde o terceiro caractere do início é “b” e o terceiro antes do final é “b” }.

Passo 1

O enunciado pede um autômato finito não-determinístico (AFN) que reconheça todas as palavras w sobre o alfabeto \{a,b\} tais que o terceiro caractere a partir do início é b e o terceiro caractere antes do final (ou seja, a posição n-2 se |w|=n) também é b.\n
Informações dadas:
\text{Alfabeto } \Sigma=\{a,b\}.
A propriedade a verificar para uma palavra w é simultaneamente:
\text{(i) o caráter na posição }3\text{ é }b;áçãé
\text{(ii) o caráter na posição }n-2\text{ é }b.áçãé
Nós devemos fornecer um AFN que aceite exatamente as palavras que satisfazem as duas condições acima.\n
(Reparos úteis que vou usar depois: a condição (ii) pode ser escrita como a linguagem \Sigma^* b \Sigma^2 — existe um b tal que há exatamente duas letras após ele — e a condição (i) é uma restrição fixa sobre a terceira letra.)

Passo 2

Pequena revisão didática (sem pular passos): o que é um AFN e como vou usá-lo aqui.\n
Um AFN é uma tupla \left(Q,\Sigma,\delta,q_0,F\right) onde:
Q
é o conjunto finito de estados,\n
\Sigma
é o alfabeto (aqui \{a,b\}),\n
\delta:Q\times(\Sigma\cup\{\varepsilon\})\to\mathcal P(Q)
é a função de transição (pode ser não-determinística e permitir \varepsilon-transições),\n
q_0\in Q
é o estado inicial,\n
F\subseteq Q
é o conjunto de estados de aceitação.\n
Como truque prático: é fácil construir um AFN para a linguagem “há um b que tem exatamente duas letras depois” (isto é, \Sigma^* b \Sigma^2): deixamos um laço que consome qualquer número de símbolos, num ponto consumimos um b e então exigimos exatamente duas letras e terminamos. Para a restrição "terceira letra é b" basta contar até 3 (estados que contam 0,1,2,3) e aceitar só se a terceira for b.\n
Para as duas condições juntas (interseção de linguagens regulares), podemos construir um autômato que efetua as duas verificações ao mesmo tempo: formalmente fazemos o produto entre os estados que contam a terceira letra (determinístico) e os estados do AFN que verifica a terceira antes do final (não-determinístico). O produto entre um autômato determinístico e um não-determinístico resulta num AFN (cada símbolo pode levar a múltiplos pares porque a segunda coordenada é não-determinística). Vou construir explicitamente esse AFN produto.

Passo 3

Construção do componente que garante "terceira letra é b". Vou chamar os estados desse componente de S_0,S_1,S_2,S_{3b},S_{3a} com a seguinte ideia:
  • S_0: não leu nada ainda (posição 0),
  • S_1: leu 1 símbolo,
  • S_2: leu 2 símbolos,
  • ao ler o terceiro símbolo a partir de S_2 vai para S_{3b} se for b, ou para S_{3a} se for a,
  • S_{3b} e S_{3a} significam "já passei da terceira posição; saber se a terceira foi b ou a". Em S_{3b} e S_{3a} há laços em a e b (consomem o resto da palavra sem mudar a verificação da terceira posição).\n
    Formalmente, as transições determinísticas desse componente (chamarei função \delta_S) são:
\delta_S(S_0,a)=\{S_1\},\quad \delta_S(S_0,b)=\{S_1\},
\delta_S(S_1,a)=\{S_2\},\quad \delta_S(S_1,b)=\{S_2\},
\delta_S(S_2,a)=\{S_{3a}\},\quad \delta_S(S_2,b)=\{S_{3b}\},
\delta_S(S_{3a},a)=\{S_{3a}\},\\ \delta_S(S_{3a},b)=\{S_{3a}\},
\delta_S(S_{3b},a)=\{S_{3b}\},\\ \delta_S(S_{3b},b)=\{S_{3b}\}.
Neste componente, o estado “aceitável quanto à terceira letra” é S_{3b} (se a máquina terminar ali ou depois nele, a condição (i) está satisfeita). Palavras com menos de 3 símbolos não alcançam S_{3b} e portanto não seriam aceitas quando exigirmos ambas condições.

Passo 4

Construção do componente AFN que garante "terceiro antes do final é b" — isto é, reconhece \Sigma^* b \Sigma^2.\n
Um AFN simples para \Sigma^* b \Sigma^2 (vou chamar os estados T_0,T_1,T_2,T_f) funciona assim:
  • T_0 tem laço em a e b (consome qualquer prefixo),
  • de T_0 existe uma transição em b para T_1 (escolhemos aquele b que pretendemos ser o terceiro antes do final),
  • de T_1 qualquer símbolo a ou b leva para T_2,
  • de T_2 qualquer símbolo a ou b leva para T_f,
  • T_f é estado de aceitação e não há transições saindo dele (isto força que, ao alcançar T_f, o input tenha exatamente terminado).\n
    Formalmente (função \delta_T):
\delta_T(T_0,a)=\{T_0\},\quad \delta_T(T_0,b)=\{T_0,T_1\}.
(Aqui notamos que em T_0 ao ler b podemos ou ficar em T_0 (ignorar esse b como candidato) ou ir para T_1 (usar esse b como candidato a ser o terceiro antes do final). É precisamente a não-determinismo que permite escolher qual b será o terceiro-a-partir-do-fim.)
\delta_T(T_1,a)=\{T_2\},\quad \delta_T(T_1,b)=\{T_2\},
\delta_T(T_2,a)=\{T_f\},\quad \delta_T(T_2,b)=\{T_f\}.
O único estado final do componente é T_f. Assim esse AFN aceita exatamente as palavras que têm um b tal que restam duas letras após ele — ou seja, cujo terceiro antes do final é b.

Passo 5

Construção do AFN produto que aceita a interseção: "terceira letra é b" E "terceiro antes do final é b".\n
Vamos combinar os dois componentes mantendo a informação simultânea. Os estados do AFN final serão pares (S_i,T_j) com S_i estado do componente da terceira letra e T_j estado do componente do terceiro-antes-do-final.\n
Defino:
Q=\{(S_0,T_0),(S_1,T_0),(S_2,T_0),\dots,(S_{3b},T_f),\ldots\},
ou seja, todos os pares possíveis S-coordenação por T-coordenação. O estado inicial é
q_0=(S_0,T_0).
A transição do AFN produto \delta em um símbolo x\in\{a,b\} é:
\delta\big((S_i,T_j),x\big)=\{(S_{i'},T_{j'}) \mid S_{i'}\in\delta_S(S_i,x)\\ \text{e}\\ T_{j'}\in\delta_T(T_j,x)\}.
Observe que \delta_T é não-determinística (por exemplo \delta_T(T_0,b)=\{T_0,T_1\}), então para um par fixo a imagem pode conter múltiplos pares — isso produz um AFN (não preciso determinizar).\n
O conjunto de estados finais do AFN produto é:
F=\{(S_{3b},T_f)\}.
Isto significa: aceitamos exatamente se, ao final da leitura, a componente S assegura que a terceira letra foi b (estado S_{3b}) e a componente T assegura que escolhemos um b que fica a duas letras do fim (estado T_f).\n
Em palavras: o AFN simula simultaneamente a contagem da terceira letra e a busca não-determinística por um b que seja terceiro antes do final; aceita somente se ambas as verificações forem verdadeiras.

Passo 6

Verificação por exemplos (para entender melhor; isto também serve como mini-aula sobre execução de AFN produto).\n
  • Exemplo 1: w= \text{`abbaaa'} (escrevo as letras apenas para raciocinar). |w|=6. A terceira letra (posição 3) é b? Sim, se w[3]=b. O terceiro antes do final é a posição 6-2=4; se w[4]=b então aceita. O AFN produto verificará S-componente chega em S_{3b} ao ler a terceira letra; paralelamente, o T-componente pode escolher um b em T_0 que resulte em T_f exatamente ao final. Se ambos derem certo, o par ficará em (S_{3b},T_f) e assim aceita.\n
  • Exemplo 2: w= \text{`bab'} (comprimento 3). Terceira letra é b (sim); terceiro antes do final é posição 3-2=1, que é b também (sim). Nosso AFN produto aceita: o componente S após 3 símbolos está em S_{3b}; o componente T pode, desde T_0, ao ler o primeiro b ir para T_1, então consumir os dois símbolos seguintes e alcançar T_f. Assim o par final será (S_{3b},T_f). Então palavras curtas onde as posições se sobrepõem também são tratadas corretamente.\n
  • Exemplo 3 (rejeitada): w= \text{`aaabbb'}. Aqui a terceira letra é a (logo condição (i) falha), mesmo que possa haver um b na posição terceiro-antes-do-final; o produto só aceita se ambas componentes acabarem nos seus estados aceitáveis simultaneamente. Como S acabará em S_{3a}, nenhum par final será (S_{3b},T_f); portanto é rejeitado.

Passo 7

Resumo didático rápido de como aplicar isso numa prova:\n
  • Separe as condições que dependem do prefixo (contar até a posição 3) e do sufixo (terceiro antes do fim = \Sigma^* b \Sigma^2).\n
  • Construa autômatos para cada condição (um determinístico simples para a terceira posição; um AFN simples para \Sigma^* b \Sigma^2).\n
  • Intersecte as linguagens via produto de autômatos: crie estados pares e aceite apenas os pares onde ambas condições são satisfeitas. Como um dos fatores é não-determinístico, o produto resultante será um AFN — isso é aceitável.\n
  • Em prova, desenhe os diagramas separados (pequenos) e depois desenhe o produto (ou descreva-o formalmente) e indique o estado inicial e o(s) final(is). Se o examinador pede só um AFN, pode desenhar o produto; se pede apenas justificar que a linguagem é regular e dar um autômato, vale também dar os dois componentes e dizer “produto” (mas é melhor desenhar o produto final).

Resposta

O AFN final é a tupla
\bigl(Q,\Sigma,\delta,(S_0,T_0),F\bigr)
onde
\Sigma=\{a,b\},
Q=\{(S_i,T_j)\mid S_i\in\{S_0,S_1,S_2,S_{3a},S_{3b}\},\\ T_j\in\{T_0,T_1,T_2,T_f\}\},
o estado inicial é (S_0,T_0), o conjunto de aceitação é
F=\{(S_{3b},T_f)\},
e a função de transição \delta é dada por
\delta\big((S_i,T_j),x\big)=\{(S_{i'},T_{j'})\mid S_{i'}\in\delta_S(S_i,x)\\ \text{e}\\ T_{j'}\in\delta_T(T_j,x)\},
com \delta_S definida por
\delta_S(S_0,a)=\{S_1\},\\ \delta_S(S_0,b)=\{S_1\},
\delta_S(S_1,a)=\{S_2\},\\ \delta_S(S_1,b)=\{S_2\},
\delta_S(S_2,a)=\{S_{3a}\},\\ \delta_S(S_2,b)=\{S_{3b}\},
\delta_S(S_{3a},a)=\{S_{3a}\},\\ \delta_S(S_{3a},b)=\{S_{3a}\},
\delta_S(S_{3b},a)=\{S_{3b}\},\\ \delta_S(S_{3b},b)=\{S_{3b}\},
e \delta_T definida por
\delta_T(T_0,a)=\{T_0\},\quad \delta_T(T_0,b)=\{T_0,T_1\},
\delta_T(T_1,a)=\{T_2\},\quad \delta_T(T_1,b)=\{T_2\},
\delta_T(T_2,a)=\{T_f\},\quad \delta_T(T_2,b)=\{T_f\},
e \delta_T(T_f,x)=\varnothing para todo x\in\{a,b\}.

Exercícios relacionados