← Back to branch summary

~a-j-delaney/libamore/cunit-dev

« back to all changes in this revision

Viewing changes to src/libAMoRE/nfa2mnfa_help.c

  • Committer: buraq
  • Date: 2004-04-16 17:04:28 UTC
  • Revision ID: vcs-imports@canonical.com-20040416170428-ko6l3kyx1c5jyrll
initial

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/libAMoRE/nfa2mnfa_help.c
 
1
/*
 
2
 *  Copyright (c) ?    - 2000 Lehrstuhl fuer Informatik VII, RWTH Aachen
 
3
 *  Copyright (c) 2000 - 2002 Burak Emir
 
4
 *  This file is part of the libAMoRE library.
 
5
 *
 
6
 *  libAMoRE is  free software; you can redistribute it and/or
 
7
 *  modify it under the terms of the GNU Lesser General Public
 
8
 *  License as published by the Free Software Foundation; either
 
9
 *  version 2.1 of the License, or (at your option) any later version.
 
10
 *  You should have received a copy of the GNU Lesser General Public
 
11
 *  License along with the GNU C Library; if not, write to the Free
 
12
 *  Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
 
13
 *  02111-1307 USA.  
 
14
 */
 
15
 
 
16
/* nfa2mnfa_help.c
 
17
 */
 
18
 
 
19
#include "nfa2mnfa_help.h"
 
20
 
 
21
nfa delsta(nfa inputnfa) {
 
22
 mrkfin infin=inputnfa->infin;   /* abbreviation */
 
23
  nfa result;                     /* Automaton to be returned.       */
 
24
  b_array reach1,reach2;          /* mark reachable and productive states */
 
25
  array stack;                     
 
26
  posint height=0;                /* height of stack */
 
27
  posint state1,state2,s1,s2,letter;
 
28
  posint count=0;                 /* count reachable and productive states */
 
29
 
 
30
  reach1=newb_array(inputnfa->qno+1);
 
31
  reach2=newb_array(inputnfa->qno+1);
 
32
  stack=newarray(inputnfa->qno+1);
 
33
  /* init stack with initial states */
 
34
  for(state1=0;state1<=inputnfa->qno;state1++)
 
35
    if(isinit(infin[state1]))
 
36
      {reach1[state1]=TRUE;
 
37
       stack[height++]=state1;
 
38
      }
 
39
  while(height) /* stack not empty */
 
40
    {state1=stack[--height];
 
41
     for(letter=1;letter<=inputnfa->sno;letter++)
 
42
       for(state2=0;state2<=inputnfa->qno;state2++)
 
43
         if(testcon(inputnfa->delta,letter,state1,state2)&&(!reach1[state2]))
 
44
           {reach1[state2]=TRUE;
 
45
            stack[height++]=state2;
 
46
           }
 
47
    } 
 
48
  /* all reachable states are marked in reach1
 
49
   * initialize stack with reachable final states 
 
50
   */
 
51
  for(state1=0;state1<=inputnfa->qno;state1++)
 
52
    if(isfinal(infin[state1]) && reach1[state1])
 
53
      {reach2[state1]=TRUE;
 
54
       stack[height++]=state1;
 
55
       count++;
 
56
      }
 
57
  while(height) /* stack not empty */
 
58
    {state1=stack[--height];
 
59
     for(state2=0;state2<=inputnfa->qno;state2++)
 
60
       if(reach1[state2])
 
61
         for(letter=1;letter<=inputnfa->sno;letter++)
 
62
           if(testcon(inputnfa->delta,letter,state2,state1)&&(!reach2[state2]))
 
63
             {reach2[state2]=TRUE;
 
64
              stack[height++]=state2;
 
65
              count++;
 
66
             }
 
67
    }  
 
68
  /* in reach2 all reachable and productive states are marked
 
69
   * there are exactly count many of these states
 
70
   */
 
71
  if(count==(inputnfa->qno+1))  /* No state has to be eliminated. */
 
72
    {freebuf();return inputnfa;}
 
73
 
 
74
  /* A new automaton has to be calculated. */
 
75
  result=newnfa();
 
76
  result->sno=inputnfa->sno;
 
77
  result->is_eps=FALSE;
 
78
  result->minimal=FALSE;
 
79
  if(count)result->qno=count-1;
 
80
  else     result->qno=0;
 
81
  result->delta=newndelta(result->sno,result->qno);  
 
82
  result->infin=newfinal(result->qno);    
 
83
 
 
84
  if(count==0) /* L(na)==empty */
 
85
    {setinit(result->infin[0]);
 
86
     setfinalF(result->infin[0]);
 
87
    }
 
88
  else
 
89
    {for(state1=0,count=0;state1<=inputnfa->qno;state1++)
 
90
       if(reach2[state1]) stack[count++]=state1;
 
91
     /* stack contains all old states, that are reachable and productive */
 
92
     for(state1=0;state1<count;state1++)
 
93
       {s1=stack[state1];             /* abbreviation for old state */
 
94
        setfinal(result->infin[state1],isfinal(infin[s1]));  
 
95
        if(isinit(infin[s1]))setinit(result->infin[state1]);  
 
96
        for(state2=0;state2<count; state2++)
 
97
          {s2=stack[state1];          /* abbreviation for old state */
 
98
           for (letter=1;letter<=result->sno;letter++)
 
99
             if(testcon(inputnfa->delta,letter,s1,s2))
 
100
               connect(result->delta,letter,state1,state2); 
 
101
          }   
 
102
       }
 
103
    }
 
104
  freebuf();
 
105
  return result;              
 
106
}
 
107
 
 
108
nfa invers_d(dfa inputdfa) {
 
109
    int i,j;
 
110
    nfa result;
 
111
    
 
112
    result=newnfa();
 
113
    result->is_eps=FALSE;
 
114
  result->minimal=FALSE;
 
115
  result->sno=inputdfa->sno;                      
 
116
  result->qno=inputdfa->qno;
 
117
  result->infin=newfinal(result->qno);
 
118
  result->delta=newndelta(result->sno,result->qno);
 
119
  /* Find initial and final states and compute delta. */
 
120
  for (i=0; i<=inputdfa->qno; i++)
 
121
   {/* Test if i is a new initial state. */
 
122
    if (isfinal(inputdfa->final[i]))
 
123
      setinit(result->infin[i]);
 
124
    /* Compute delta for state i. */
 
125
    for (j=1; j<=inputdfa->sno; j++)
 
126
      connect(result->delta,j,inputdfa->delta[j][i],i);
 
127
   }    
 
128
  /* Now find only final state. */               
 
129
  setfinalT(result->infin[inputdfa->init]);
 
130
  return result;
 
131
}
 
132
/***************************************************************************/