Skip to content
Python Implementation of Daciuk's Algorithm to Create Minimal Acyclic Finite-State Automata
Python Dockerfile
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information.

Daciuk Automaton

This is a basic Python implementation of Daciuk's algorithm to create minimal acyclic finite-state Automata.


Graphviz must be installed.


The Graphviz Python library is in the requirements.

pip install -r requirements.txt

Otherwise the Dockerfile could be used. However, the file was not tested yet.

Running the Script

In order to start the program you have to run the file.

At first you can choose from three options. All of them will create an automaton.

  • Choose a file that contains a list of words.
  • Enter a list of words manually on the command line.
  • Load a previously created automaton.

After you have selected one of these options, you can either draw the automaton, display all words included, search for a specific word or save this automaton to a new file.

Not Implemented

  • On-line Construction: Adding random new words to an existing automaton.
  • Tarjan Tables
  • Perfect Hashing
You can’t perform that action at this time.