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 M_{1} with language L(M_{1}) = A Automaton M_{2} with language L(M_{2}) = B 

Output:  intersected automaton N = M_{1} x M_{2} accepting the language L(N) = A ∩ B  
Applicable Types:  all 
For the intersection algorithm we have two arbitrary automata M_{1} and M_{2}, 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 onthefly algorithm only constructs the reachable part of the new states whereas the other algorithm always builds the full cartesian product.
Union
Input: 
Automaton M_{1} with language L(M_{1}) = A Automaton M_{2} with language L(M_{2}) = B 

Output:  union automaton N = M_{1} x M_{2} accepting the language L(N) = A ∪ B  
Applicable Types:  all 
For the union algorithm we have two arbitrary automata M_{1} and M_{2}, 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 onthefly 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 wellknown powerset construction is applied in an onthefly 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 nonfinal 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.