Deterministic Finite State Automata (DFA) Minimization

Usage:

Usage: ./dfa-2-mka [-i|-t] [file]

Algorithm inspired by TIN course at FIT BUT:

1. DFA is obtained via file or via stdin by excluding [file] arg
2. Input is checked and parsed to internal DFA structure
3. DFA is converted to well specified DFA (if not already)
4. State are initially splitted to two groups (classes): * Final States * Non-Final States
5. Run until two separate iterations yields the same result: * For each symbol in alphabet:
   • For each class in classes:
     • Calculate corresponding group of Final states for given symbol
     • If the final states resides within different classes, split the class
6. Obtained classes are sorted by length and renamed from 1
7. DFA is rebuilt from the original DFA data and calculated classes
8. DFA is printed out

Examples

Sample input	Output with arg -i	Output with arg -t
1,2,3 1 1,3 1,b,1 1,a,2 2,a,3 2,b,2 3,a,2 3,b,3	1,2,3 1 1,3 1,b,1 1,a,2 2,a,3 2,b,2 3,a,2 3,b,3	1,2 1 1 1,a,2 1,b,1 2,a,1 2,b,2

DFA Minimization