Interprète machine finie

Question

Je suis en train de faire une méthode formelle et l'un des projets consiste à créer un interpréteur de machine fini en utilisant Java. Il doit lire NFA à partir d'un fichier texte, puis convertir NFA en DFA. Il doit également sortir DFA dans un fichier texte. Ensuite, il passe à travers l'entrée de symbole et le processus DFA montrant le résultat si accepter ou rejeter.

Je n'ai pas beaucoup de problème avec le codage mais avec la conception. Je veux avoir une bonne façon de l'implémenter. Que devrais-je commencer? quelles classes devrais-je avoir?

Answer 1

Une façon de concevoir une application consiste à examiner le problème et à décrire la solution en anglais. Décrivez chaque étape, y compris les hypothèses que vous remarquez en cours de route. Chaque paragraphe probablement devrait être une méthode différente. Les méthodes qui font un travail très similaire devraient être des classes. Donc, pouvez-vous mettre à jour votre réponse pour décrire verbalement, sous forme de paragraphe, ce que votre programme doit faire? Oh, et juste pour donner un petit conseil: lorsque vous décrivez le NFA/DFA sous la forme d'un paragraphe, essayez de le décrire comme si vous alliez dessiner une image (vous pouvez remplacer le dessin "draw" par quelque chose, plus tard , dans l'application actuelle, mais il peut être un bon espace réservé pour l'instant)

Answer 2

Je voudrais baser le design sur le fonctionnement des classes Stream. Vous pouvez avoir un flux d'entrée NFA et un flux de sortie DFA. Ensuite, une classe de convertisseur pourrait utiliser une instance de chacun.

Answer 3

Vous pouvez réécrire le "codeur" que j'utilise pour créer le mien.

Je l'ai conçu pour prendre une table d'états finis (disposée en code), mais j'ai résumé l'analyseur assez bien et vous pourriez juste réécrire cette partie, le reste des classes devrait fonctionner plutôt bien tel quel.

http://code.google.com/p/state-machine/