Pourquoi devrions-nous étudier les trois formes de représentation des automates finis?

DFA, NFA et epsilon NFA tous les trois nous permettent de représenter une langue régulière particulière. Avec n'importe laquelle de ces représentations, nous pouvons arriver à la même expression régulière, alors pourquoi devons-nous étudier les trois formes de représentation des automates finis? Il peut y avoir des explications sur ce que NFA peut faire, ce que DFA ne peut pas faire, c'est-à-dire que NFA pourrait nous aider à concevoir des incertitudes. Par exemple, lors de la conception d'un jeu (échecs), nous avons de nombreuses options pour déplacer une pièce particulière d'un endroit particulier qui peut être facilement représenté à l'aide de NFA. Mais à quoi sert epsilon NFA quand on peut faire de même avec NFA ou DFA?

Ajoutez des grammaires régulières pour un quatrième. Il y en a d'autres ...

L'intérêt de DFA + NFA réside en partie dans le fait qu'il s'agit de modèles de calcul simples, avec des exemples de non-déterminisme NFA (et -NFA) (une idée cruciale pour des modèles plus élaborés). Pour prouver que DFA et NFA acceptent le même ensemble de langues, il s'agit également d'explorer un phénomène très important dans un cadre simple et compréhensible.$\epsilon$

Les expressions régulières (et aussi les grammaires régulières) sont des formalismes complètement différents, qui décrivent le même ensemble de langues. Encore une fois, la preuve de ce fait explore des relations croisées importantes, et est un exemple que les formalismes peuvent sembler très différents, être basés sur des concepts radicalement différents, mais décrire les mêmes langages. Encore une fois, dans un cadre assez simple.

Pour une utilisation "réelle", vous pouvez commencer par une expression régulière et obtenir un DFA minimal pour une recherche haute performance. Les circuits numériques sont essentiellement des DFA, leur compréhension est au cœur de l'ingénierie informatique. Enfin et surtout, les systèmes peuvent souvent être modélisés comme "étant dans un état" et "se déplaçant vers un autre" sur des stimuli externes, même si le système est très loin d'un véritable DFA, le voir de cette façon pourrait aider à le comprendre.

Ajouté plus tard: Comme l'a noté Raphael, il peut être plus efficace d'interpréter un NFA directement pour la recherche, car la création d'un DFA peut être coûteuse et un NFA peut être beaucoup plus petit.

il existe une grande variété de raisons d'étudier les différentes formes / correspondances des DFA par rapport aux NFA. voici quelques faits saillants sélectionnés, certains issus de la théorie de la complexité avancée.

• Les NFA sont un modèle intéressant pour le "calcul parallèle". on peut considérer l'avancement des États à travers la NFA comme une version parallèle du calcul DFA. les calculs DFA vs NFA reflètent donc une partie de la distinction entre calcul séquentiel et parallèle. en comparant les deux contextes, il aide également à étudier la complexité algorithmique inhérente aux problèmes.

• Les NFA sont souvent utilisés dans les systèmes de correspondance d'expressions régulières (assez omniprésents dans toutes les langues, en particulier les langues modernes générées à l'ère Unix), qui permettent généralement des descriptions d'expressions régulières qui sont converties en NFA, puis éventuellement converties en DFA pour faciliter la recherche.

• il y a pas mal de problèmes ouverts qui subsistent dans les régions et ils sont souvent étudiés sur la base de la correspondance DFA / NFA. voir par exemple, y a-t-il des problèmes ouverts sur les DFA (cstheory stackexchange). de façon assez étonnante, certains d'entre eux sont liés à des zones très profondes de CS, y compris le problème P vs NP, c'est-à-dire la non- vide d'intersection des DFA . un autre domaine ouvert est par exemple le calcul du NFA minimal pour un DFA .

• aussi pour quelques informations connexes, voir cette question semi-célèbre / à haute voix sur cstheory.se : Quelle est l'illumination que je suis censé atteindre après avoir étudié les automates finis?

• il existe des applications très diverses des DFA par rapport aux NFA et la correspondance entre les deux y est souvent exploitée. la correspondance de motifs de chaînes est mentionnée ci-dessus, mais les constructions DFA / NFA sont souvent utilisées dans la reconnaissance vocale (automatisée). voir par exemple cet article très cité: Transducteurs à états finis pondérés dans la reconnaissance vocale / Mohri, Pereira, Riley

Les DFA ont une implémentation plus facile que NFA car leur état suivant est déterminé par une fonction et les NFA aident un utilisateur à exprimer facilement ce qu'il veut comme sortie, car le NFA peut choisir entre plusieurs chemins. et epsilon-NFA est une extension de NFA où les transitions peuvent être effectuées sans prendre de symboles d'entrée.

Il y a une mauvaise chose au sujet du nombre d'états des DFA. Ça explose, parfois .

En bref, si le nombre d'états est tout simplement trop élevé (toujours fini mais nous vivons dans un monde physique.), Alors vous devez augmenter le niveau d'abstraction pour faire face à la complexité des dépenses d'un certain ralentissement. Les autres modèles, comme les NFA et les AFA, doivent fournir des moyens plus succincts de représenter les langues régulières.