# 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.

[1] | There are a handful of small differences: named character classes
and collating sequences are not supported. The most important difference
probably is that the character . does not match a newline. |