Complementation of an automaton.
The complement of an automaton is an automaton that recognizes precisely those strings that are not recognized by the original automaton.
Determinization of non-deterministic finite automata.
An automatons is deterministic if for each state and each character in the alphabet there is at most one transition.
Computation of the intersection of two NFAs.
The intersection of two NFAs is an NFA that accepts the intersection of the languages accepted by the two NFAs.
The intersection is computed by constructing a product automaton.
The product automaton has a state for each pair of states from the two input automata.
The transitions are constructed by taking the cartesian product of the transitions of the two input automata.
A state in a nondeterministic finite automaton.
A state is merely a collection of transitions to other states.
In a nondeterministic automaton, a state can have multiple transitions with the same input leading to different states.
If the state has no transitions, it is a dead end state.
If the state is a final state, it accepts the input.
A transition from one state to another.
The transition can be of different types, e.g. a character range or an epsilon transition.
The destination state is stored as an index that is unique within the automaton.
The type of a transition in a nondeterministic finite automaton.
Every transition in an automaton is labeled with a type that determines the behavior of the transition.
The type can be a character range, a negated character range, or an epsilon transition.
For a character range transition, the transition is taken if the input character is in the range.
For a negated character range transition, the transition is taken if the input character is not in the range.
An epsilon transition is taken without consuming any input.
Compiles the given regex into an NFA.
The NFA accepts exactly the language of the regex.
The NFA is constructed using the Thompson construction.
The returned automaton is trim but can contain epsilon transitions.