#include <stdio.h>
#include<string.h>
#define MAX 10
int n;
int i , j ,sym;
int t[MAX][MAX][MAX];
int dfastates[MAX][MAX];
int dfacount=0;
int visited[MAX];
void adddfastate(int set[]){
           for( i=0; i<dfacount;i++){
                    int same=1;
                    for(j=0;j<n;j++){
                             if(dfastates[i][j]!=set[j]){
                                      same=0;
                                      break;
                             }
                    }
                    if(same) return;
           }
           for (j=0;j<n;j++){
                    dfastates[dfacount][j]=set[j];
           }
           dfacount++;
}
void printset(int set[]){
           printf("{");
           for(i=0;i<n;i++){
                    if(set[i]) printf("q%d",i);
           }
           printf("}");
}
void nfatodfa(int start){
           int q[MAX][MAX];
           int front=0,rear=0;
           int startset[MAX]={0};
           startset[start]=1;
           memcpy(q[rear++],startset,sizeof(startset));
           adddfastate(startset);
           printf("\nDFA states:\n");
           while(front<rear){
                    int current[MAX];
                    memcpy(current,q[front++],sizeof(current));
                    printf("\n State");
                    printset(current);
                    printf("->");
                    for( sym=0;sym<2;sym++){
                             int newset[MAX]={0};
                             for( i=0;i<n;i++){
                                      if(current[i]){
                                              for( j=0; j<n;j++){
                                                      if(t[i][sym][j]){
                                                               newset[j]=1;
                                                      }
                                              }
                                      }
                             }
                       printf("\n on input %c->", sym==0?'a':'b');
                       printset(newset);
                       adddfastate(newset);
                       int exists=0;
                       for( i=0;i<rear;i++){
                               if(memcmp(q[i],newset,sizeof(newset))==0){
                                       exists=1;
                                       break;
                               }
                       }
                       if(!exists){
                               memcpy(q[rear++],newset,sizeof(newset));
                       }
               }
       }
}
int main(){
       int start;
       printf("Enter number of nfa states:");
       scanf("%d",&n);
       printf("\nEnter nfa transition table(0/1) for a and b");
       for( i=0; i<n; i++){
                for( sym=0; sym<2;sym++){
                        for(j=0;j<n;j++){
                                scanf("%d",&t[i][sym][j]);
                        }
                }
       }
       printf("\nEnter start state:");
       scanf("%d",&start);
       nfatodfa(start);
       return 0;
}
