Un simulateur pour un automate push-down non-déterministe

Question

Eh bien, j'ai besoin de faire un simulateur pour un automate Push-Down non-déterministe. Tout va bien, je sais que je dois faire une récursion ou quelque chose de similaire. Mais je ne sais pas comment faire cette fonction qui simulerait un automate. Je fais tout le reste sous contrôle, générateur d'automates, pile ... Je le fais en Java, donc c'est peut-être seulement un problème que l'homme peut rencontrer, et je l'ai fait. Donc, si quelqu'un a fait quelque chose de similaire, je pourrais utiliser des conseils.

Ceci est mon organisation actuelle de code:

Classes: class transit: 
    list<transit> -contains non deterministic transitions 
    state 
    input sign 
    stack sign class generator 
    it generate automaton from file clas NPA 
    public boolean start() - this function I am having trouble with 

Bien sûr problème de piles séparées, et une entrée pour chaque branche.

J'ai essayé de le résoudre avec la collection d'objets NPA et essayer de démarrer chaque objet, mais cela ne fonctionne pas.

Answer 1

Bon, pensez à la définition de l'automate. Vous avez des états et une fonction de transition d'état. Vous avez la pile. Ce qui rend la vie passionnante, c'est le non-déterminisme. Cependant, c'est un théorème (recherche) que chaque automate fini non déterministe a un FSA déterministe équivalent.

Une approche que vous pourriez essayer est de construire l'équivalent DFA. Toutefois, dans le pire des cas, il s'agit d'un espace exponentiel: chaque état du DFA est mappé à un sous-ensemble de l'ensemble des états NFA.

Donc, vous pouvez l'essayer "en ligne" à la place. Maintenant, au lieu de construire le DFA équivalent, vous simulez le NFA; lors des transitions d'état, vous construisez tous les états suivants que vous atteignez et vous les mettez dans une structure de données; puis revenez en arrière et voir ce qui se passe ensuite pour chacun de ces états.

Answer 2

JFLAP est open source et fait cela (et bien plus encore!) - pourquoi ne pas le vérifier?