Format for Automata

One can use the Grail and FAdo formats for nondeterministic finite automata (those with nonempty transitions). The format of FAdo files must be as follows:

  1. '#' begins a comment
  2. @NFA, or @DFA, begins a new automaton (and determines its type) and must be followed by the list of the final states separated by blanks
  3. Transitions are written one per line and consist of three fields separated by blanks: "state" "symbol" "new state"
  4. The source state of the first transition is the initial state, or initial states can be specified by listing them after the end states and an asterisk.

Here is an example of an automaton accepting ab* using both, Grail and FAdo formats:

Grail:   
(START) |- 1
1 a 2
2 b 2
2 -| (FINAL)
        
FAdo:   
@NFA 2
1 a 2
2 b 2
        

More examples follow:

Automaton accepting aaa(aaa)*b + aa(ba)*a(aa(ba)*a)*b:

Grail:   
(START) |- 1
1 a 2
2 a 3
3 b 2
3 a 4
4 a 2
4 b 8
1 a 5
5 a 6
6 a 7
7 a 5
7 b 8
8 -| (FINAL)
        
FAdo: 
@NFA 8
1 a 2
2 a 3
3 b 2
3 a 4
4 a 2
4 b 8
1 a 5
5 a 6
6 a 7
7 a 5
7 b 8
        

Automaton accepting ab + bba:

Grail:         
(START) |- 1
1 a 2
2 b 3
1 b 4
4 b 5
5 a 3
3 -| (FINAL)
        
FAdo:  
@NFA 3
1 a 2
2 b 3
1 b 4
4 b 5
5 a 3