Download MONA Version 1.4 User Manual

Transcript
MONA 1.4
DFA function
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
DFA
*dfaTrue();
*dfaFalse();
*dfaConst(int n, int i );
*dfaLess(int i, int j );
*dfaLesseq(int i, int j );
*dfaPlus1(int i, int j, int n );
*dfaMinus1(int i, int j, int n );
*dfaEq1(int i, int j );
*dfaEq2(int i, int j );
*dfaPlus2(int i, int j );
*dfaMinus2(int i, int j );
*dfaPlusModulo1(int i, int j, int k );
*dfaMinusModulo1(int i, int j, int k );
*dfaEmpty(int i );
*dfaIn(int i, int j );
*dfaSubset(int i, int j );
*dfaUnion(int i, int j, int k );
*dfaInter(int i, int j, int k );
*dfaSetminus(int i, int j, int k );
*dfaMax(int i, int j );
*dfaMin(int i, int j );
*dfaBoolvar(int i );
*dfaPresbConst(int i, int n );
*dfaSingleton(int i );
*dfaLastPos(int i );
*dfaAllPos(int i );
*dfaFirstOrder(int i );
MONA formula
true
false
pi = n
pi < pj
pi <= pj
pi = pj + n
pi = pj + n
pi = pj
Pi = Pj
Pi = Pj + 1
Pi = Pj - 1
pi = pj + 1 % pk
pi = pj - 1 % pk
Pi = empty
pi in Pj
Pi sub Pj
Pi = Pj union Pk
Pi = Pj inter Pk
Pi = Pj \ Pk
pi = max(Pj )
pi = min(Pj )
bi
Pi = pconst(n )
singleton(Pi )
see p. 62
see p. 62
see p. 62
Figure 13: Basic DFAs
been met, in an accept state if the first “1” was met on the previous transition, and in a reject
state otherwise. (This automaton is used for the -m compatibility option, see Section 6.5).
Constructing automata explicitly
Constructing automata like those listed in Figure 13 is done using the following functions:
void dfaSetup(int n, int len, int indices []) - prepares construction of a DFA with
n states and variable indices given by the array indices of length len .
void dfaAllocExceptions(int n ) - prepares construction of the next state allocating room
for n exceptions, i.e. n calls to dfaStoreException.
void dfaStoreException(int s, char *path ) - stores an exception: on the transitions
63