Algorithms

This section explains the several algorithms that can be applied to automata within this tool. Some are restricted to certain types of automata by birth, while others can widely be deployed to all of them. Some use two automata as input, while others only take one to construct the outcoming automaton according to the algorithm. Here is a full list of algorithms that are supported by FAT, including a detailed description explaining how they work.

Intersection

Input:		Automaton M1 with language L(M1) = A Automaton M2 with language L(M2) = B
Output:		intersected automaton N = M1 x M2 accepting the language L(N) = A ∩ B
Applicable Types:		all

For the intersection algorithm we have two arbitrary automata M₁ and M₂, with their appropriate languages A and B respectively, as input. Then FAT constructs an automaton N out of them, accepting the intersection A ∩ B of the original languages. FAT does this by taking the cartesian product of the states of the original automata. There are two versions of the algorithm. The on-the-fly algorithm only constructs the reachable part of the new states whereas the other algorithm always builds the full cartesian product.

Union

Input:		Automaton M1 with language L(M1) = A Automaton M2 with language L(M2) = B
Output:		union automaton N = M1 x M2 accepting the language L(N) = A ∪ B
Applicable Types:		all

For the union algorithm we have two arbitrary automata M₁ and M₂, with their appropriate languages A and B respectively, as input. Then FAT constructs an automaton N out of them, accepting the union A ∪ B of the original languages. FAT does this by taking the cartesian product of the states of the original automata. There are two versions of the algorithm. The on-the-fly algorithm only constructs the reachable part of the new states whereas the other algorithm always builds the full cartesian product. This algorithm is identical to the intersection algorithm except that different sets of final states are generated.

Determinization

Input:		NFA M with language L(M) = A
Output:		DFA N accepting the same language L(N) = A
Applicable Types:		NFA

The determinization algorithm that is implemented in FAT takes a single nondeterministic finite automaton M with language A as input and constructs an equivalent deterministic finite automaton N, accepting the same language A. Here, the well-known powerset construction is applied in an on-the-fly algorithm where only those states are generated that are reachable.

Complement

Input:		DFA M with language L(M) = A
Output:		DFA N accepting the complemented language L(N) = Σ* \ A
Applicable Types:		DFA

The complementation algorithm that is implemented in FAT takes a single deterministic finite automaton M with language A as input and constructs the complemented language by just exchanging the final with the non-final states.

Minimization

Input:		DFA M with language L(M) = A
Output:		smallest DFA N accepting the same language L(N) = A
Applicable Types:		DFA

For the minimization algorithm FAT takes a single deterministic finite automaton M with language A as input and constructs the smallest (w.r.t. the number of states) deterministic finite automaton N that accepts the same language A. Here, a partition refinement algorithm is implemented.