search

Oneiroe / PySimpleAutomata

Academic Python Library to manage DFA, NFA and AFW automata.
MIT License
23 stars 6 forks source link

execution hanging for big json file #6

Closed aymeric75 closed 6 months ago

aymeric75 commented 6 months ago

Hello,

I tried to generate a DFA graph with the following code:


from PySimpleAutomata import DFA, automata_IO

dfa_example = automata_IO.dfa_json_importer("exampleBIS.json")

DFA.dfa_completion(dfa_example)
new_dfa=DFA.dfa_minimization(dfa_example)

automata_IO.dfa_to_dot(new_dfa, 'outputttt-name', './')

where exampleBIS.json (see attached) is pretty big, i.e. around 5k transitions...

The execution is hanging since more than 10 minutes, is it normal ?

Thanks exampleBIS.json

Oneiroe commented 6 months ago

As stated in the readme of the project:

This library is not meant for performance nor space consumption optimization, but for academic purposes: PySimpleAutomata aims to be an easily readable but working representation of automata theory.

In other terms, the code is by-design as close as possible to the theoretical pseudo-code of the techniques implemented, in order to be easily understandable while being also executable, yet without optimization.

In this case, it is the completion which takes quite some time and space (number of final transitions= number of states * number of transitions in the alphabet). The input automaton (which is visualized in few seconds without the completion) has 2097 states and 3325 transitions, while most of the states use at most a couple of transitions... its completed automaton is going to be a spaghetti monster.

aymeric75 commented 6 months ago

Exactly and I actually don't want the "completed" automaton, thanks