An FSA implemented in Python.
The FSA class keeps the FSA transition table
as a Python dictionary with (source_state, symbol) tuples as index,
where the value is the set of target states
reached from the source_state with the symbol.
Naturally, if the automaton is a DFA, the value is a singleton set.
The method generate() should traverse the automaton in a depth-first manner,
returning all or a limited number of strings accepted by the automaton as specified in the template.
The function insert_words()
in file lexicon.py
which reads a list of words from a given file,
uses the FSA class as a way to insert all words into a trie.
The resulting trie (FSA) should be a DFA,
where arc labels are letters as in the following figure
showing an example trie with words
walk, walks, wall, walls, want, wants, work and works.
It generates all and the only the words inserted.
The minimized FSA of the previous example should look like this:
The images are auto-generated by graphviz from the dot files by the to_dot() function in fsa.py.