GAUTOMATA - A package for automata with BDD based alphabets

0.10

Introduction

gautomata is a package for finite-state automata with alphabets represented as BDDs. It is based on the gbdd package.

The general interface is exported by the gautomata::Nfa, which contains the interface gautomata::Nfa::Factory for creating automata for a given implementation and a number of methods on automata such as concatenation, determinization, minimization and so on.

Every implementation inherits from gautomata::Nfa and needs to define:

• A factory used to create automata with this implementation
• Methods returning alphabet, sets of states, set of starting states and set of accepting states.
• Method adding state
• Implement one of:
  • Method to return set of symbols between two sets of states
  • Method to return set of symbols between two states
  • Method to return the transition relation
• Implement on of:
  • Method to add edge between sets of states
  • Method to add edge between two states
  • Method to add transitions given a relation
• Currently, minimization and determinization also have to be defined

All other operations have default implementations inherited from gautomata::Nfa. The case where there is a choice of defining one of several methods, there are default implementation of all of them, but they are defined in terms of each other.

Factories are useful for implementing general procedures that are independent of Nfa implementation. Examples include procedures for testing and measurements.

Current implementations are:

• gautomata::BNfa, entire transition relation implemented as BDD
• gautomata::RefNfa, wrapper around gautomata::Nfa pointer

gautomata::RefNfa is just a wrapper around a pointer to a gautomata::Nfa and is a technique to get value semantics instead of pointer semantics for methods that return automata.

---