[Home]
[Contents]
[Chapter]
[Previous Algorithm]
[Next Algorithm]


Build the union of two automata


short mergestates(); automata unionautom( aut1, aut2 ) automata aut1, aut2; { short *st1, *st2, ts; automata a; if( aut1->d != aut2->d ) return( NULL ); /*** different alphabets ***/ a = (automata)malloc(sizeof(struct automrec)); a->d = aut1->d; a->st = 0; ts = aut1->st + aut2->st; a->nextst = (short**) malloc( ts * sizeof(short*) ); a->final = (short*) malloc( ts * sizeof(short) ); st1 = (short*) calloc( ts, sizeof(short) ); st2 = (short*) calloc( ts, sizeof(short) ); mergestates( 0, 0, aut1, aut2, a, st1, st2 ); free(st1); free(st2); return( a ); } short mergestates( s1, s2, aut1, aut2, newaut, st1, st2 ) short s1, s2, *st1, *st2; automata aut1, aut2, newaut; { short as1, as2, i, j; /*** find if state is already stored ***/ for( i=0; i < newaut->st; i++ ) if( st1[i]==s1 && st2[i]==s2 ) return( s1<0 || s2<0 ? -i : i ); /*** create new state ***/ st1[i] = s1; st2[i] = s2; newaut->st++; as1 = s1 < 0 ? -s1 : s1; as2 = s2 < 0 ? -s2 : s2; newaut->nextst[i] = (short*) malloc( newaut->d * sizeof(short) ); for( j=0; j<newaut->d; j++ ) newaut->nextst[i][j] = mergestates( aut1->nextst[as1][j], aut2->nextst[as2][j], aut1, aut2, newaut, st1, st2 ); if( s1 < 0 ) { newaut->final[i] = (s2<0) ? max( aut1->final[-s1], aut2->final[-s2]) : aut1->final[-s1]; return(-i); } else if( s2 < 0 ) { newaut->final[i] = aut2->final[-s2]; return(-i); } return( i ); }

C source (716.unaut.c)



© Addison-Wesley Publishing Co. Inc.