Exercicios Resolvidos - Automatos Finitos Nao Deterministicos AFN e Deterministicos AFD

1 50 Considere o Autômato Finito Nãodeterminístico AFN definido por N1 q0 q1 q2 q3 a b c δ q0 q3 em que δ é dada por δ a b c q0 q0 q0 q0 q1 q1 q2 q2 q3 q3 Gere um PDF contendo os seguintes documentos a 05 Desenhe um diagrama de estados desse AFN N1 b 10 Através de uma tabela mostre o passo a passo da computação da cadeia acacab com comentários para cada passo parecido com o que foi apresentado nos slides introdutórios de AFN parte 1 e indicando no final se a cadeia acacab foi aceita ou rejeitada pelo AFN N1 Adicionalmente inclua uma árvore que mostre os diferentes caminhos ou ramificações que o autômato teve que seguir c 10 Transforme o AFN N1 para um AFD M1 utilizando qualquer um dos dois métodos ensinados em sala de aula d 05 Compute sobre M1 a mesma cadeia acacab deixando claro quais os estados que foram seguidos até o ultimo símbolo lido da cadeia e indicando se a cadeia foi aceita ou rejeitada pelo AFD M1 e 10 Repita os passos b e d para a cadeia abbc f 10 Repita os passos b e d para a cadeia abb 2 50 Considere o Autômato Finito Nãodeterminístico AFN definido por N2 q0 q1 q2 q3 q4 a b c δ q0 q3 q4 em que δ é dada por δ a b c ε q0 q1 q2 q1 q1 q3 q1 q1 q2 q2 q2 q2 q4 q3 q4 Gere um PDF contendo os seguintes documentos a 05 Desenhe um diagrama de estados desse AFN N2 Considere o Autômato Finito Nãodeterminístico AFN definido por N q0 q1 q2 ₁ q3 a b c δ q0q3 em que δ é dada por δ a b c q0 q0 q0 q0q1 q1 q2 ø ø q2 ø q3 ø q3 ø ø ø a Desenhe um diagrama de estados desse AFN N ₁ cada estado é representado por um quadrado com o nome do estado dentro As setas indicam as transições entre os estados e são rotuladas com os símbolos que causam a transição O estado inicial é indicado por uma seta apontando para ele e os estados finais são indicados por um quadrado duplo Neste caso o estado inicial é q0 e o estado final é q3 b Através de uma tabela mostre o passo a passo da computação da cadeia acacab com comentários para cada passo parecido com o que foi apresentado nos slides introdutórios de AFN parte 1 e indicando no final se a cadeia acacab foi aceita ou rejeitada pelo AFN N Adicionalmente inclua uma árvore que mostre os ₁ diferentes caminhos ou ramificações que o automato teve que seguir Estado atual Símbolo lido Próximos estados Comentários q0 a q0q1 O AFN começa no estado inicial q0 e lê o primeiro símbolo a De acordo com a função de transição δ ele pode permanecer em q0 ou ir para q1 q0q1 c q0 O AFN está agora em dois estados possíveis q0 e q1 Ele lê o próximo símbolo c De acordo com a função de transição δ ele pode permanecer em q0 ou ir para nenhum estado a partir de q1 q0 a q0q1 O AFN está agora em um único estado possível q0 Ele lê o próximo símbolo a De acordo com a função de transição δ ele pode permanecer em permanecer em q0 ou ir para q1 q0q1 c q0 O AFN está agora em dois estados possíveis q0 e q1 Ele lê o próximo símbolo c De acordo com a função de transição δ ele pode permanecer em q0 ou ir para nenhum estado a partir de q1 q0 a q0q1 O AFN está agora em um único estado possível q0 Ele lê o próximo símbolo a De acordo com a função de transição δ ele pode permanecer em q0 ou ir para q1 q0q1 b q2 O AFN está agora em dois estados possíveis q0 e q1 Ele lê o próximo símbolo b De acordo com a função de transição δ ele pode ir para nenhum estado a partir de q0 ou ir para q2 a partir de q1 No final da computação o AFN está no estado q2 que não é um estado final Portanto a cadeia acacab é rejeitada pelo AFN N ₁ árvore que mostra os diferentes caminhos que o autômato teve que seguir durante a computação Cada nível da árvore representa um passo na computação e cada ramo representa um caminho possível que o autômato pode seguir No final da computação apenas um ramo chega ao estado q2 que não é um estado final Portanto a cadeia acacab é rejeitada pelo AFN N ₁ c Transforme o AFN N para um AFD M utilizando qualquer um dos dois métodos ₁ ₁ ensinados em sala de aula d Compute sobre M a mesma cadeia acacab deixando claro quais os estados que ₁ foram seguidos até o ultimo símbolo lido da cadeia e indicando se a cadeia foi aceita ou rejeitada pelo AFD M ₁ e Repita os passos b e d para a cadeia abbc f Repita os passos b e d para a cadeia abb Questão 2 Considere o Autômato Finito Nãodeterminístico AFN definido por N ₂ q0 q1 q2 q3 q4 abc δ q0 q3 q4 em que δ é dada por δ a b c ε q0 ø ø ø q1q2 q1 q1q3 q1 q1 ø q2 q2 q2 q2q4 ø q3 ø ø ø ø q4 ø ø ø ø Desenhe um diagrama de estados desse AFN N ₂ Consiste em um autômato finito nãodeterminístico com cinco estados q0 q1 q2 q3 e q4 Ele possui um conjunto de três símbolos de entrada a b e c As transições do AFN N são as seguintes ₂ A partir do estado q0 é possível fazer uma transição vazia ε para os estados q1 e q2 A partir do estado q1 há três tipos de transições É possível permanecer no estado q1 consumindo os símbolos a b ou c É possível fazer uma transição para o estado q3 consumindo o símbolo a A partir do estado q2 também há três tipos de transições É possível permanecer no estado q2 consumindo os símbolos a b ou c É possível fazer uma transição para o estado q4 consumindo o símbolo c O estado q3 não possui transições para outros estados O estado q4 também não possui transições para outros estados O estado q4 é um estado de aceitação o que significa que se o AFN terminar nesse estado ele aceita a sequência de entrada O conjunto de estados finais do AFN N é ₂ q3 q4 Em resumo o AFN N tem a capacidade de aceitar sequências de entrada que possuam ₂ um a no meio seguido ou não de b e terminando em c Ele utiliza transições vazias ε para percorrer diferentes estados e realizar múltiplas escolhas durante o processamento da entrada