Geração de AFD a partir de AFND

4264 palavras 18 páginas
Algoritmo de Geração de AFD
O algoritmo a seguir foi criado de maneira a simplificar a geração manual de AFDs a partir de AFNDs. O mesmo algoritmo pode ser codificado em qualquer linguagem de programação.
Para exemplificar o processo, vamos tomar o seguinte AFND:
A seguir iremos ver as etapas necessárias para a construção do AFD
1.1 Encontre os Fechos-
Para cada estado X, determine para quais estados pode-se ir sem que nenhum caracter seja lido. Isto inclui o próprio estado X e todos os estados que se pode atingir a partir dele seguindo transições com . O Fecho- de X é o conjunto com todos os estados assim determinados.
Note que estamos falando de conjuntos, portanto usaremos chaves para descrever Fechos-.
A tabela a seguir mostra o resultado desta etapa para o nosso exemplo. Repare principalmente no Fecho- de D.

Estado Fecho-
A {A, F}
B {B}
C {C}
D {A, D, F}
E {E}
F {F}
1.2 Determine Possíveis Próximos Estados
Para cada estado do AFND podemos encontrar todos os estados aonde podemos chegar seguindo um determinado símbolo: basta seguir as transições indicadas com o símbolo indicado, que podem ser várias. Por exemplo, do estado E lendo o símbolo a podemos ir para o próprio E ou para D. Estas são as únicas transições mostradas com o símbolo a a partir de E.
No entanto, após chegarmos nestes estados ainda podemos seguir transições . Os estados obtidos também seriam alcançados lendo-se o símbolo indicado. Assim, no nosso exemplo, a partir de E com símbolo a chegaríamos em E, D, A ou F.
Para determinar todos os possíveis próximos estados precisamos então:
• Determinar todos os estados para onde podemos ir seguindo apenas o símbolo indicado, e
• Fazer a união de todos os Fechos- dos estados determinados.
Alguns de vocês podem estar pensando “por que não verificar as transições com  também antes de verificar as transições com o símbolo?”. Isto não faria mal, de fato, mas o procedimento global que iremos mostrar torna isto dispensável. Por

Relacionados

  • kkhhjk
    6628 palavras | 27 páginas
  • Teoria da computação
    25589 palavras | 103 páginas
  • Artigo de Teoria dos Autômatos
    5053 palavras | 21 páginas
  • Técnicas de inteligência artificial aplicadas ao problema das redes de regulação biológicas
    7370 palavras | 30 páginas
  • exercícios de tecnologia da computação
    3247 palavras | 13 páginas
  • normas academicas
    6821 palavras | 28 páginas
  • radiacais
    224418 palavras | 898 páginas