Assignment 9: Finite-state Automata

Deadline: 27th January, 14:00 CET

In this assignment, we will work with finite state automata, use it for an implementation of the trie data structure and implement a minimization method. A class representing the FSA is available to you with various methods already implemented, and so is a small lexicon.

For a more detailed description, please attend the lab session on Friday, 17th of January.

Starter code

• template: a9.py
• tests: test_a9.py
• data: lexicon

Exercises

Exercise 1

Implement the method insert_words() 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.

Exercise 2

Implement the method minimize(). You can use any of the minimization methods discussed in the class.

Wrapping up

Do not forget to

• indicate your name(s) in the file header
• add the honor code (I/We pledge that this code represents my/our own work)
• commit all your changes
• push it to your GitHub repository