Operations supported by libfa

The library supports most common operations on finite automata. See the file fa.h for the exact definition of the interface.

fa_compile

Compile a regular expression into a finite automaton. The regular expressions accepted by fa_compile are extended POSIX regular expressions [1], so that you can perform your automata calculations with libfa, but still use the much more optimized POSIX matchers out there, like the one included with glibc.

fa_as_regexp

Convert a finite automaton back into a regular expression. This is the reverse of fa_compile.

fa_minimze

Minimize a finite automaton using Hopcroft's or Brzozowski's algorithm. Which one is used can be set with the global variable fa_minimization_algorithm.

fa_concat, fa_union, fa_iter

Form the concatenation, union or iteration of automata. For regular expressions A and B, this corresponds to the regular expression AB, A|B, and constructs like A*, A+, and A{m,n}

fa_intersect

Creates an automaton that accepts the intersection of two languages.

fa_complement

Creates an automaton that accepts the complement of a regular language.

fa_minus

Creates an automaton that accepts words in the set difference of two languages.

fa_contains, fa_equals

Compare two automata and decide whether the language of one is contained in that of the other, or if their languages are equal.

fa_overlap

Compute the overlap of two regular languages. The overlap of two languages is the set of strings that can be split in more than one way into a left part in the first language and a right part in the second language.

fa_example

Generate an example of words accepted by an automaton. Picks a word from the automaton's language, trying to make the choice 'sensible'.

fa_ambig_example

Given two automata, generate a word upv so that u and up are accepted by the first automaton, and pv and v are accepted by the second automaton. The existence of such a word proves that the two languages are not unambiguously concatenable. Contrast that with fa_overlap which only returns the p from such words.

fa_dot

Generate a dot file of the automaton that can be displayed with Graphviz's dot.

If you are a finite automata aficionado, you might have noticed that there is no distinction between deterministic (DFA) and nondeterministic (NFA) automata in the interface. libfa will decide on its own when it needs to turn an NFA into a DFA and perform these conversions transparently to callers of the library.