Peut-on dire que DFA est plus efficace que NFA?

Je viens de commencer à lire sur la théorie du calcul. Si nous comparons ce qui est le plus puissant (en acceptant des chaînes), les deux sont identiques. Mais qu'en est-il de l'efficacité? DFA sera rapide par rapport à NFA, car il n'a qu'un seul bord sortant et il n'y aura aucune ambiguïté. Mais en cas de NFA, nous devons vérifier tous les cas possibles et cela prend sûrement du temps. Pouvons-nous donc dire que DFA est plus efficace que NFA?

Mais, mon autre partie du cerveau pense également que NFA n'existe qu'en théorie, donc nous ne pouvons pas comparer son efficacité avec DFA.

Il existe deux réponses, selon la façon dont vous définissez efficace.

Compacité de la représentation

Dire plus avec moins : les NFA sont plus efficaces.

La conversion d'un DFA en NFA est simple et n'augmente pas la taille de la représentation.

Cependant, il existe des langues régulières pour lesquelles le plus petit DFA est exponentiellement plus grand que le plus petit NFA. Un exemple typique est pour k fixe.$(a|b)^*b(a|b)^k$$k$

Calcul

Courez vite : les DFA sont plus efficaces.

Les ordinateurs que nous utilisons aujourd'hui sont de nature déterministe. Cela les rend mal à faire face au non-déterminisme. Il existe deux façons courantes de traiter de manière déterministe les NFA: revenir en arrière d'un côté, ce qui est assez coûteux, ou garder une trace des états actifs, ce qui signifie que chaque transition prendra jusqu'à fois plus longtemps (où N est la taille de la NFA) .$N$$N$

En termes de puissance, ils sont équivalents comme vous l'avez dit et il existe un algorithme (construction de sous-ensemble) pour convertir un NFA en un DFA équivalent. Comme vous pouvez le voir d'après le nom de l'algorithme, il construit des sous-ensembles d'états du NFA. Si votre NFA a états, l'algorithme peut sortir un DFA avec 2 n états mais c'est une limite supérieure. Parfois, le nombre d'états ne change pas du tout ou même diminue. Donc, dans la pratique, il importe moins de savoir lequel utiliser.$n$$2^n$

La correspondance DFA est linéaire dans la taille de la chaîne d'entrée. La correspondance NFA implique un retour en arrière afin que les NFA fassent plus de travail. Ainsi, les DFA sont plus efficaces.

Ajout aux réponses ci-dessus:

Les NFA peuvent être plus efficaces en termes de calcul que les DFA, dans le sens où ils peuvent être simulés sur un processeur parallèle.

BTW: Je vois des gens dire que les NFA ne peuvent pas exister dans la réalité. Je ne suis pas d'accord. Un ordinateur avec un grand nombre de processeurs peut exécuter de nombreuses tâches en parallèle et peut être considéré comme une machine non déterministe. On pourrait assigner chaque branche de calcul à un nouveau processeur et les arrêter toutes chaque fois que l'un d'eux accepte.

$\epsilon$

Comme d'autres l'ont fait remarquer, vous devez définir ce que signifie «efficacité». Pour illustrer cela, je donne un modèle raisonnable avec une réponse différente.

En ne regardant que le (s) modèle (s) d'automate, c'est-à-dire en ignorant notamment comment vous les implémenteriez sur des machines réelles, la mesure d'efficacité évidente est "le nombre de transitions effectuées sur un (plus court) cycle d'acceptation".

En ce qui concerne cette mesure, les deux modèles d'automates sont équivalents , car les deux prennent exactement une transition par symbole d'entrée (wlog nous n'avons pas$\varepsilon$-transitions). Notez que la taille des automates considérés ne prend pas en compte ici.

Techniquement parlant, un NFA est un concept plus général qu'un DFA, car il n'est pas nécessaire d'utiliser le non-déterminisme. En d'autres termes: chaque DFA est un NFA. De ce point de vue, il existe pour chaque langue un NFA qui est au moins aussi efficace que le DFA le plus efficace, quelle que soit la mesure d'efficacité que vous préférez.

A part cela, je suis d'accord avec Raphael que cela dépend beaucoup de ce que vous voulez dire avec efficacité et de la mise en œuvre.

Comme nous le savons sur les automates, c'est-à-dire la machine qui peut effectuer n'importe quelle action sans aucune puissance humaine ou sans participation directe de l'homme. par exemple: machine à laver. Automates finis signifie que nous connaissons l'état d'exécution d'une tâche par machine, comme 1 appuyez sur ON 2 appuyez sur OFF, il n'y a donc que 2 états, c'est-à-dire les automates finis. Venons-en maintenant à DFA, c'est-à-dire aux automates finis déterministes. signifie formellement que nous pouvons facilement déterminer les états, il n'y a pas d'ambiguïté et informellement, il n'a besoin que d'une transition autorisée sur 1 symbole. NFA: automates finis non déterministes. il faut plus de temps pour calculer l'état réel et il y a une ambiguïté et d indique officieusement qu'il y a plusieurs transitions autorisées sur 1 symbole. dans le cas du temps nécessaire pour atteindre la destination, NFA prend plus de temps que DFA, mais NFA peut charger plus de données que DFA. * DFA et NFA ont le même pouvoir de reconnaître la chaîne. merci .. Deepali kaushik