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