Avantages/Inconvénients de l'ADN de plus de DFA et vice versa

Quelles sont les pro et con à la fois des DFA et de la NFA, lorsque comparés les uns aux autres?

Je sais que DFA sont plus faciles à mettre en œuvre que la NFA et que la NFA sont plus lents à arriver à l'accepter état de DFA, mais il y a tout les autres explicite, bien connue des avantages ou des inconvénients?

OriginalL'auteur user559142 | 2011-05-11

  1. 1

    L'avantage de l'ADN de plus de DFA est la propriété, à toujours "choisir le droit chemin". Puisque vous ne pouvez pas dire à un algorithme de "choisir le bon chemin", généralement une conversion à partir de l'ADN de DFA œuvres, la création de DFA états qui symbolisent les multiples NFA unis. Ainsi, lorsque votre ADN est dans l'État A et a le choix d'aller à A,B ou C, alors l'état suivant dans votre DFA serait {A,B,C}.

    C'est ce qui explique les avantages et les inconvénients:
    DFA peuvent être mis en œuvre plus facile puisque leur état suivant est déterminé par une fonction.
    La NFA est de permettre à un utilisateur plus facile à exprimer ce qu'ils veulent, parce que la NFA pouvez choisir entre de nombreux chemin de.

    OriginalL'auteur bln-tom

  2. 1

    De fan et DFAs accepter le même ensemble de langues - les langages réguliers.

    Une mise en œuvre directe de l'ADN (ce qui n'est pas un DFA, depuis DFA est un sous-ensemble de la NFA) implique généralement permettant le retour en arrière alors qu'une mise en œuvre directe d'un DFA ne nécessite que toutes les étapes de l'entrée de la longueur, donc dans ce sens, DFAs "arriver à la réponse" plus vite que l'équivalent de Fan (qui ne sont pas DFAs).

    Lorsque vous essayez de trouver une FA correspondant à une langue donnée ou RE (par exemple, par un algorithme), il est généralement plus facile d'arriver le premier à la NFA (car les règles sont moins strictes). Cela est particulièrement vrai lorsque vous tentez de démontrer l'existence d'une FA, depuis l'existence de l'ADN est aussi bon que l'existence d'un DFA. Si un DFA est nécessaire, les algorithmes existent pour (a) la conversion de l'ADN à un équivalent de DFA et (b) minimiser les DFA.

    Faisant brut des généralisations, DFAs sont plus rapides mais plus complexe (en termes de nombre d'états et de transitions) alors que les Fan sont plus lents mais plus simple (dans les mêmes termes).

    Hmm, est-ce vraiment vrai? J'ai pensé à la NFA étaient plus complexes qu'ils ont à déterminer le chemin à prendre pour une entrée donnée, alors qu'avec le DFA, c'est le chemin d'accès est purement déterminée par l'entrée, donnant ainsi les différences de vitesse entre les deux...

    OriginalL'auteur Patrick

  3. 0

    Un avantage certain de l'ADN de plus de DFA est que vous pouvez construire une FA représentant la langue qui est une union, intersection, concetanation etc. de deux langues (ou plus) facilement à l'aide de la NFA. C'est-à-dire, si vous avez légèrement un simple FA fait partie du job, vous pouvez les combiner facilement à l'aide de la NFA. Lors de l'utilisation d'un DFA, vous avez besoin de construire une nouvelle automates de faire tout le travail par lui-même.

    voir, il est plus facile à mettre en œuvre.
    mais il y a la question du temps comme vous l'avez mentionné.

    OriginalL'auteur bliss