Technical Report: DCC-2002-2

FAdo: tools for finite automata and regular expressions manipulation

 RogĂ©rio Reis and Nelma Moreiria

DCC-FC & LIACC, Universidade do Porto
R. do Campo Alegre 823, 4150-180 Porto, Portugal
Phone: 351 22 6078830, Fax: 351 22 6003654
E-mail: {rvr,nam}@ncc.up.pt
  August 2002

Abstract

FAdo is an ongoing project which goal is the development of a Python environment for manipulation of finite automata and regular expressions. Currently it provides most standard automata operations including conversion from deterministic to non-deterministic, minimisation, boolean operations, concatenation, conversion between automata and regular expressions, and word recognition. It includes, also, an innovative method for testing non-equivalence of two automata (or regular expressions) using a DFA canonical form and a witness generator of the difference of two automata. Our main motivation is the development of interactive tools for teaching concepts in automata theory and formal languages. Towards this goal we are also developing graphical tools for creating and manipulating automata and a graphical user interface.