#include <stdio.h>
#include <stdlib.h>

#define REJECT 0
#define ACCEPT 1
#define STOP 2

#define MAXSIZE 100

typedef struct {
   int p; /* input state */
   int a; /* input symbol */
   int q; /* output state */
} rule;

typedef struct {
   int n;           /* number of states */
   int m;           /* number of transition rules */
   int f[MAXSIZE];  /* final states */
   rule T[MAXSIZE]; /* transition table */
} NFA;

NFA readNFA ( )
{
   NFA M;
   int p, a, q;

   printf("Enter the number of states: "); scanf("%d", &(M.n));
   printf("The states will be numbered 0 to %d\n", M.n-1);
   for (p=0; p<M.n; ++p) M.f[p] = 0;
   printf("The start state is 0\n");
   printf("Enter the final states one by one (-1 to terminate)\n");
   while (1) {
      scanf("%d", &p);
      if ((p < 0) || (p >= M.n)) break;
      M.f[p] = 1;
   }
   printf("Enter the rules one by one\n");
   printf("Enter -1 as input state to terminate\n");
   M.m = 0;
   while (1) {
      scanf("%d", &p); if ((p < 0) || (p >= M.n)) break;
      scanf("%d%d", &a, &q);
      M.T[M.m].p = p; M.T[M.m].a = a; M.T[M.m].q = q;
      ++M.m;
   }
   return M;
}

int helper1 ( NFA M, int A[] )
{
   int U[MAXSIZE], V[MAXSIZE], p, i, j;

   U[0] = 1; for (p=1; p<M.n; ++p) U[p] = 0;
   i = 0;
   while ((A[i] >= 0) && (A[i] < M.n)) {
      for (p=0; p<M.n; ++p) V[p] = 0;
      for (p=0; p<M.n; ++p) if (U[p]) {
         for (j=0; j<M.m; ++j) {
            if ((M.T[j].p == p) && (M.T[j].a == A[i])) {
               V[M.T[j].q] = 1;
            }
         }
      }
      for (p=0; p<M.n; ++p) U[p] = V[p];
      ++i;
   }
   for (p=0; p<M.n; ++p) if ((M.f[p]) && (U[p])) return ACCEPT;
   return REJECT;
}

int helper2 ( NFA M, int A[], int i, int p )
{
   int j;

   if ((A[i] < 0) || (A[i] >= M.n))
      return (M.f[p]) ? ACCEPT : REJECT;

   for (j=0; j<M.m; ++j) {
      if ((M.T[j].p == p) && (M.T[j].a == A[i])) {
         if (helper2(M,A,i+1,M.T[j].q) == ACCEPT) return ACCEPT;
      }
   }

   return REJECT;
}

int runNFA ( NFA M )
{
   int a, i, decision;
   int A[MAXSIZE];

   printf("Do you want to continue (0/1)? "); scanf("%d", &a);
   if (a == 0) return STOP;
   printf("Enter the input symbols one by one (-1 to terminate)\n");
   i = 0;
   while (1) {
      scanf("%d", &A[i]);
      if (A[i] & 0xfffffffeU) break;
      ++i;
   }
   decision = helper1(M,A);
   printf("+++ Iterative function outputs %s\n", (decision) ? "ACCEPT" : "REJECT");
   decision = helper2(M,A,0,0);
   printf("+++ Recursive function outputs %s\n", (decision) ? "ACCEPT" : "REJECT");
   return decision;
}

int main ( )
{
   NFA M;

   M = readNFA();
   while (runNFA(M) != STOP);
   exit(0);
}