Project 1. WS 2006
==================

Implement a library for manipulating finite automata and regular expressions.

1. Representation of finite automata and regular expressions. Bringing regular expressions into star normal form (optional). 
2. Constructing finite automata from regular expressions.
3. Algorithms on automata:
   - Powerset construction (converting an NFA into a DFA which recognizes the same formal language).
   - Given a finite automaton and a natural number n, return a list of all words of length n accepted by the automaton.
   - Minimization.
   - Operations on automata: Complement, union, composition, intersection, difference, equivalence, Kleene star.
4. Translating finite automata into corresponding regular expressions.



Literature

John E. Hopcroft, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. 
Addison Wesley, 1979 (Chapter 2).

Anne Brüggermann-Klein, Regular Expressions into Finite Automata, Proceedings of Latin '92, 1992.
http://www11.in.tum.de/~brueggem/papers/nfaTCS.ps