Construa AFNs para reconhecer as seguintes linguagens:
onde o terceiro caractere do início é “b” e o terceiro antes do final é “b”
.
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
sobre o alfabeto
tais que o terceiro caractere a partir do início é
e o terceiro caractere antes do final (ou seja, a posição
se
) também é
.\n
Informações dadas:
Informações dadas:
A propriedade a verificar para uma palavra
é simultaneamente:
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 — existe um
tal que há exatamente duas letras após ele — e a condição (i) é uma restrição fixa sobre a terceira letra.)
(Reparos úteis que vou usar depois: a condição (ii) pode ser escrita como a linguagem
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 onde:
Um AFN é uma tupla
é o conjunto finito de estados,\n
é o alfabeto (aqui
),\n
é a função de transição (pode ser não-determinística e permitir
-transições),\n
é o estado inicial,\n
é o conjunto de estados de aceitação.\n
Como truque prático: é fácil construir um AFN para a linguagem “há um que tem exatamente duas letras depois” (isto é,
): deixamos um laço que consome qualquer número de símbolos, num ponto consumimos um
e então exigimos exatamente duas letras e terminamos. Para a restrição "terceira letra é
" basta contar até 3 (estados que contam 0,1,2,3) e aceitar só se a terceira for
.\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.
Como truque prático: é fácil construir um AFN para a linguagem “há um
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 é
". Vou chamar os estados desse componente de
com a seguinte ideia:
-
: não leu nada ainda (posição 0), -
: leu 1 símbolo, -
: leu 2 símbolos, - ao ler o terceiro símbolo a partir de
vai para se for , ou para se for , -
e significam "já passei da terceira posição; saber se a terceira foi ou ". Em e há laços em e (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) são:
Neste componente, o estado “aceitável quanto à terceira letra” é
(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
e portanto não seriam aceitas quando exigirmos ambas condições.
Passo 4
Construção do componente AFN que garante "terceiro antes do final é
" — isto é, reconhece
.\n
Um AFN simples para (vou chamar os estados
) funciona assim:
Um AFN simples para
-
tem laço em e (consome qualquer prefixo), - de
existe uma transição em para (escolhemos aquele que pretendemos ser o terceiro antes do final), - de
qualquer símbolo ou leva para , - de
qualquer símbolo ou leva para , -
é estado de aceitação e não há transições saindo dele (isto força que, ao alcançar , o input tenha exatamente terminado).\n
Formalmente (função):
(Aqui notamos que em
ao ler
podemos ou ficar em
(ignorar esse
como candidato) ou ir para
(usar esse
como candidato a ser o terceiro antes do final). É precisamente a não-determinismo que permite escolher qual
será o terceiro-a-partir-do-fim.)
O único estado final do componente é
. Assim esse AFN aceita exatamente as palavras que têm um
tal que restam duas letras após ele — ou seja, cujo terceiro antes do final é
.
Passo 5
Construção do AFN produto que aceita a interseção: "terceira letra é
" E "terceiro antes do final é
".\n
Vamos combinar os dois componentes mantendo a informação simultânea. Os estados do AFN final serão pares com
estado do componente da terceira letra e
estado do componente do terceiro-antes-do-final.\n
Defino:
Vamos combinar os dois componentes mantendo a informação simultânea. Os estados do AFN final serão pares
Defino:
ou seja, todos os pares possíveis
-coordenação por
-coordenação. O estado inicial é
A transição do AFN produto
em um símbolo
é:
Observe que
é não-determinística (por exemplo
), 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 é:
O conjunto de estados finais do AFN produto é:
Isto significa: aceitamos exatamente se, ao final da leitura, a componente
assegura que a terceira letra foi
(estado
) e a componente
assegura que escolhemos um
que fica a duas letras do fim (estado
).\n
Em palavras: o AFN simula simultaneamente a contagem da terceira letra e a busca não-determinística por um que seja terceiro antes do final; aceita somente se ambas as verificações forem verdadeiras.
Em palavras: o AFN simula simultaneamente a contagem da terceira letra e a busca não-determinística por um
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:
(escrevo as letras apenas para raciocinar). . A terceira letra (posição 3) é ? Sim, se . O terceiro antes do final é a posição ; se então aceita. O AFN produto verificará -componente chega em ao ler a terceira letra; paralelamente, o -componente pode escolher um em que resulte em exatamente ao final. Se ambos derem certo, o par ficará em e assim aceita.\n - Exemplo 2:
(comprimento 3). Terceira letra é (sim); terceiro antes do final é posição , que é também (sim). Nosso AFN produto aceita: o componente após 3 símbolos está em ; o componente pode, desde , ao ler o primeiro ir para , então consumir os dois símbolos seguintes e alcançar . Assim o par final será . Então palavras curtas onde as posições se sobrepõem também são tratadas corretamente.\n - Exemplo 3 (rejeitada):
. Aqui a terceira letra é (logo condição (i) falha), mesmo que possa haver um na posição terceiro-antes-do-final; o produto só aceita se ambas componentes acabarem nos seus estados aceitáveis simultaneamente. Como acabará em , nenhum par final será ; 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 =
).\n - Construa autômatos para cada condição (um determinístico simples para a terceira posição; um AFN simples para
).\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
onde
o estado inicial é
, o conjunto de aceitação é
e a função de transição
é dada por
com
definida por
e
definida por
e
para todo
.