154 using namespace Extensional;
165 for (
int* f = &f_spec[0]; *f >= 0; f++)
171 for (
int i=0; i<n_trans; i++)
172 trans[i] = t_spec[i];
179 for (
int* f = &f_spec[0]; *f != -1; f++) {
181 final[n_finals++] = *f;
186 TransBySymbolI_State::sort(trans, n_trans);
192 while (j < n_trans) {
195 while ((j < n_trans) && (s == trans[j].symbol))
199 assert(j == n_trans);
208 part[i].group = is_final[i] ? 1 : 0;
209 s2g[i] = part[i].group;
216 StateGroupByGroup::sort(part,
n_states+1);
218 if (part[0].group == part[
n_states].group) {
220 g2s[0].fst = &part[0]; g2s[0].lst = &part[
n_states+1];
224 assert(part[0].group == 0);
225 do i++;
while (part[i].group == 0);
226 g2s[0].fst = &part[0]; g2s[0].lst = &part[i];
227 g2s[1].fst = &part[i]; g2s[1].lst = &part[
n_states+1];
239 for (
int g = n_groups; g--; ) {
241 if (g2s[g].lst-g2s[g].fst > 1) {
247 for (StateGroup* sg = g2s[g].fst; sg<g2s[g].lst; sg++) {
248 while ((
t < t_lst) && (
t->i_state < sg->state))
251 if ((
t < t_lst) && (
t->i_state == sg->state))
252 sg->group = s2g[
t->o_state];
257 StateGroupByGroup::sort(g2s[g].fst,
258 static_cast<int>(g2s[g].lst-g2s[g].fst));
260 if (g2s[g].fst->group != (g2s[g].lst-1)->group) {
262 StateGroup* sg = g2s[g].fst+1;
263 while ((sg-1)->group == sg->group)
266 StateGroup* lst = g2s[g].lst;
269 s2g[sg->state] = n_groups;
270 g2s[n_groups].fst = sg++;
271 while ((sg < lst) && ((sg-1)->group == sg->group)) {
272 s2g[sg->state] = n_groups; sg++;
274 g2s[n_groups++].lst = sg;
280 }
while (n_groups != m_groups);
285 for (
int g = n_groups; g--; )
286 for (StateGroup* sg = g2s[g].fst; sg < g2s[g].lst; sg++)
287 if (is_final[sg->state]) {
288 final[n_finals++] = g;
295 for (
int g=0; g<n_groups; g++)
296 s2r[g2s[g].fst->state] = g;
299 for (
int i = 0; i<n_trans; i++)
300 if (s2r[trans[i].i_state] != -1) {
302 trans[j].symbol = trans[i].symbol;
303 trans[j].o_state = s2g[trans[i].o_state];
321 TransByI_State::sort(trans, n_trans);
326 while ((j < n_trans) && (i == trans[j].i_state))
330 assert(j == n_trans);
333 state[start] = SI_FROM_START;
335 while (!visit.
empty()) {
338 if (!(state[
t->o_state] & SI_FROM_START)) {
339 state[
t->o_state] |= SI_FROM_START;
340 visit.
push(
t->o_state);
349 TransByO_State::sort(trans, n_trans);
354 while ((j < n_trans) && (i == trans[j].o_state))
358 assert(j == n_trans);
361 for (
int i=0; i<n_finals; i++) {
362 state[
final[i]] |= (SI_TO_FINAL | SI_FINAL);
363 visit.
push(
final[i]);
365 while (!visit.
empty()) {
368 if (!(state[
t->i_state] & SI_TO_FINAL)) {
369 state[
t->i_state] |= SI_TO_FINAL;
370 visit.
push(
t->i_state);
383 re[start] = m_states++;
387 if ((state[i] == (SI_FINAL | SI_FROM_START | SI_TO_FINAL)) && (re[i] < 0))
390 int final_fst = (state[start] & SI_FINAL) ? 0 : 1;
396 if ((state[i] == (SI_FROM_START | SI_TO_FINAL)) && (re[i] < 0))
401 for (
int i=n_trans; i--; )
402 if ((re[trans[i].i_state] >= 0) && (re[trans[i].o_state] >= 0))
407 d->n_states = m_states;
408 d->n_trans = m_trans;
414 for (
int i = 0; i<n_trans; i++)
415 if ((re[trans[i].i_state] >= 0) && (re[trans[i].o_state] >= 0)) {
417 r[j].i_state = re[trans[i].
i_state];
418 r[j].o_state = re[trans[i].o_state];
421 TransBySymbol::sort(
r,m_trans);
426 for (
int i = 0; i<m_trans; ) {
427 int s = d->trans[i++].symbol;
429 while ((i<m_trans) && (d->trans[i].symbol == s))
437 unsigned int* deg = region.
alloc<
unsigned int>(m_states);
440 for (
int i=0; i<m_states; i++)
442 for (
int i=0; i<m_trans; i++)
443 deg[d->trans[i].o_state]++;
444 for (
int i=0; i<m_states; i++)
448 for (
int i=0; i<m_states; i++)
450 for (
int i=0; i<m_trans; i++)
451 deg[d->trans[i].i_state]++;
452 for (
int i=0; i<m_states; i++)
458 while (i < m_trans) {
460 while ((i < m_trans) &&
461 (d->trans[j].symbol == d->trans[i].symbol))