#include<stdio.h> 
#include<string.h> 
#include<math.h> 
int ninputs; 
int dfa [100][2][100] = {0}; 
int state [10000] = {0}; 
char ch [10], str [1000]; 
int go [10000][2] = {0}; 
int arr [10000] = {0}; 
int main () 
{ 
int st, fin, in; 
int f [10]; 
int i, j=3, s=0, final=0,flag=0,curr1,curr2,k,l; 
int c; 
printf ("\n follow the one based indexing\n"); 
printf ("\n enter the number of states::"); 
scanf ("%d", &st); 
printf ("\n give state numbers from 0 to %d", st-1); 
for (i=0; i<st; i++) 
state[(int) (pow (2, i))] = 1; 
printf ("\n enter number of final states\t"); 
scanf ("%d", &fin); 
printf ("\n enter final states::"); 
for (i=0; i<fin; i++) 
{ 
scanf ("%d", &f[i]); 
} 
int p, q, r, rel; 
printf ("\n enter the number of rules according to nfa::"); 
scanf ("%d", &rel); 
printf ("\n\n define transition rule as \n"); 
for (i=0; i<rel ; i++) 
{ 
scanf ("%d%d%d", &p,&q,&r); 
if (q==0) 
dfa[p][0][r] = 1; 
else 
dfa[p][1][r] = 1; 
} 
printf ("\n enter initial state::"); 
scanf ("%d", &in); 
in = pow (2, in); 
i=0; 
printf ("\n solving according to dfa"); 
int x=0; 
for (i=0; i<st; i++) 
{ 
for (j=0; j<2; j++) 
{ 
int stf=0; 
for (k=0; k<st; k++) 
{ 
if (dfa [i][j][k] ==1) 
stf = stf + pow (2, k); 
} 
go[(int) (pow (2, i))][j] = stf; 
printf("%d-%d-->%d\n", (int) (pow (2, i)), j, stf); 
if(state[stf]==0) 
arr[x++] = stf; 
state[stf] = 1; 
} 
} 
//for new states 
for (i=0; i<x; i++) 
{ 
printf ("for %d ----- ", arr[x]); 
for (j=0; j<2; j++) 
{ 
int new=0; 
for (k=0; k<st; k++) 
{ 
if(arr[i] & (1<<k)) 
{ 
int h = pow (2, k); 
if(new==0) 
new = go[h][j]; 
new = new | (go[h][j]); 
} 
} 
if(state[new]==0) 
{ 
arr[x++] = new; 
state[new] = 1; 
} 
} 
} 
printf ("\n the total number of distinct states are::\n"); 
printf ("state 0 1\n"); 
for (i=0; i<10000; i++) 
{ 
if(state[i]==1) 
{ 
//printf ("%d**", i); 
int y=0; 
if(i==0) 
printf ("q0 "); 
else 
for (j=0; j<st; j++) 
{ 
int x = 1<<j; 
if (x& i) 
{ 
printf ("q %d ", j); 
y = y+ pow (2, j); 
//printf ("y=%d ", y); 
} 
} 
//printf ("%d", y); 
printf (" %d %d", go[y][0], go[y][1]); 
printf("\n"); 
} 
} 
j=3; 
while(j--) 
{ 
printf ("\n enter string"); 
scanf ("%s", str); 
l = strlen(str); 
curr1 = in; 
flag = 0; 
printf ("\n string takes the following path-->\n"); 
printf ("%d-",curr1); 
for (i=0; i<l; i++) 
{ 
curr1 = go[curr1] [str[i]-'0']; 
printf ("%d-", curr1); 
} 
printf ("\n final state - %d\n", curr1); 
for (i=0; i<fin; i++) 
{ 
if (curr1 & (1<<f[i])) 
{ 
flag = 1; 
break; 
} 
} 
if(flag) 
printf ("\n string accepted"); 
else 
printf ("\n string rejected"); 
} 
return 0; 
}
 

I2luY2x1ZGU8c3RkaW8uaD4gCiNpbmNsdWRlPHN0cmluZy5oPiAKI2luY2x1ZGU8bWF0aC5oPiAKaW50IG5pbnB1dHM7IAppbnQgZGZhIFsxMDBdWzJdWzEwMF0gPSB7MH07IAppbnQgc3RhdGUgWzEwMDAwXSA9IHswfTsgCmNoYXIgY2ggWzEwXSwgc3RyIFsxMDAwXTsgCmludCBnbyBbMTAwMDBdWzJdID0gezB9OyAKaW50IGFyciBbMTAwMDBdID0gezB9OyAKaW50IG1haW4gKCkgCnsgCmludCBzdCwgZmluLCBpbjsgCmludCBmIFsxMF07IAppbnQgaSwgaj0zLCBzPTAsIGZpbmFsPTAsZmxhZz0wLGN1cnIxLGN1cnIyLGssbDsgCmludCBjOyAKcHJpbnRmICgiXG4gZm9sbG93IHRoZSBvbmUgYmFzZWQgaW5kZXhpbmdcbiIpOyAKcHJpbnRmICgiXG4gZW50ZXIgdGhlIG51bWJlciBvZiBzdGF0ZXM6OiIpOyAKc2NhbmYgKCIlZCIsICZzdCk7IApwcmludGYgKCJcbiBnaXZlIHN0YXRlIG51bWJlcnMgZnJvbSAwIHRvICVkIiwgc3QtMSk7IApmb3IgKGk9MDsgaTxzdDsgaSsrKSAKc3RhdGVbKGludCkgKHBvdyAoMiwgaSkpXSA9IDE7IApwcmludGYgKCJcbiBlbnRlciBudW1iZXIgb2YgZmluYWwgc3RhdGVzXHQiKTsgCnNjYW5mICgiJWQiLCAmZmluKTsgCnByaW50ZiAoIlxuIGVudGVyIGZpbmFsIHN0YXRlczo6Iik7IApmb3IgKGk9MDsgaTxmaW47IGkrKykgCnsgCnNjYW5mICgiJWQiLCAmZltpXSk7IAp9IAppbnQgcCwgcSwgciwgcmVsOyAKcHJpbnRmICgiXG4gZW50ZXIgdGhlIG51bWJlciBvZiBydWxlcyBhY2NvcmRpbmcgdG8gbmZhOjoiKTsgCnNjYW5mICgiJWQiLCAmcmVsKTsgCnByaW50ZiAoIlxuXG4gZGVmaW5lIHRyYW5zaXRpb24gcnVsZSBhcyBcbiIpOyAKZm9yIChpPTA7IGk8cmVsIDsgaSsrKSAKeyAKc2NhbmYgKCIlZCVkJWQiLCAmcCwmcSwmcik7IAppZiAocT09MCkgCmRmYVtwXVswXVtyXSA9IDE7IAplbHNlIApkZmFbcF1bMV1bcl0gPSAxOyAKfSAKcHJpbnRmICgiXG4gZW50ZXIgaW5pdGlhbCBzdGF0ZTo6Iik7IApzY2FuZiAoIiVkIiwgJmluKTsgCmluID0gcG93ICgyLCBpbik7IAppPTA7IApwcmludGYgKCJcbiBzb2x2aW5nIGFjY29yZGluZyB0byBkZmEiKTsgCmludCB4PTA7IApmb3IgKGk9MDsgaTxzdDsgaSsrKSAKeyAKZm9yIChqPTA7IGo8MjsgaisrKSAKeyAKaW50IHN0Zj0wOyAKZm9yIChrPTA7IGs8c3Q7IGsrKykgCnsgCmlmIChkZmEgW2ldW2pdW2tdID09MSkgCnN0ZiA9IHN0ZiArIHBvdyAoMiwgayk7IAp9IApnb1soaW50KSAocG93ICgyLCBpKSldW2pdID0gc3RmOyAKcHJpbnRmKCIlZC0lZC0tPiVkXG4iLCAoaW50KSAocG93ICgyLCBpKSksIGosIHN0Zik7IAppZihzdGF0ZVtzdGZdPT0wKSAKYXJyW3grK10gPSBzdGY7IApzdGF0ZVtzdGZdID0gMTsgCn0gCn0gCi8vZm9yIG5ldyBzdGF0ZXMgCmZvciAoaT0wOyBpPHg7IGkrKykgCnsgCnByaW50ZiAoImZvciAlZCAtLS0tLSAiLCBhcnJbeF0pOyAKZm9yIChqPTA7IGo8MjsgaisrKSAKeyAKaW50IG5ldz0wOyAKZm9yIChrPTA7IGs8c3Q7IGsrKykgCnsgCmlmKGFycltpXSAmICgxPDxrKSkgCnsgCmludCBoID0gcG93ICgyLCBrKTsgCmlmKG5ldz09MCkgCm5ldyA9IGdvW2hdW2pdOyAKbmV3ID0gbmV3IHwgKGdvW2hdW2pdKTsgCn0gCn0gCmlmKHN0YXRlW25ld109PTApIAp7IAphcnJbeCsrXSA9IG5ldzsgCnN0YXRlW25ld10gPSAxOyAKfSAKfSAKfSAKcHJpbnRmICgiXG4gdGhlIHRvdGFsIG51bWJlciBvZiBkaXN0aW5jdCBzdGF0ZXMgYXJlOjpcbiIpOyAKcHJpbnRmICgic3RhdGUgMCAxXG4iKTsgCmZvciAoaT0wOyBpPDEwMDAwOyBpKyspIAp7IAppZihzdGF0ZVtpXT09MSkgCnsgCi8vcHJpbnRmICgiJWQqKiIsIGkpOyAKaW50IHk9MDsgCmlmKGk9PTApIApwcmludGYgKCJxMCAiKTsgCmVsc2UgCmZvciAoaj0wOyBqPHN0OyBqKyspIAp7IAppbnQgeCA9IDE8PGo7IAppZiAoeCYgaSkgCnsgCnByaW50ZiAoInEgJWQgIiwgaik7IAp5ID0geSsgcG93ICgyLCBqKTsgCi8vcHJpbnRmICgieT0lZCAiLCB5KTsgCn0gCn0gCi8vcHJpbnRmICgiJWQiLCB5KTsgCnByaW50ZiAoIiAlZCAlZCIsIGdvW3ldWzBdLCBnb1t5XVsxXSk7IApwcmludGYoIlxuIik7IAp9IAp9IApqPTM7IAp3aGlsZShqLS0pIAp7IApwcmludGYgKCJcbiBlbnRlciBzdHJpbmciKTsgCnNjYW5mICgiJXMiLCBzdHIpOyAKbCA9IHN0cmxlbihzdHIpOyAKY3VycjEgPSBpbjsgCmZsYWcgPSAwOyAKcHJpbnRmICgiXG4gc3RyaW5nIHRha2VzIHRoZSBmb2xsb3dpbmcgcGF0aC0tPlxuIik7IApwcmludGYgKCIlZC0iLGN1cnIxKTsgCmZvciAoaT0wOyBpPGw7IGkrKykgCnsgCmN1cnIxID0gZ29bY3VycjFdIFtzdHJbaV0tJzAnXTsgCnByaW50ZiAoIiVkLSIsIGN1cnIxKTsgCn0gCnByaW50ZiAoIlxuIGZpbmFsIHN0YXRlIC0gJWRcbiIsIGN1cnIxKTsgCmZvciAoaT0wOyBpPGZpbjsgaSsrKSAKeyAKaWYgKGN1cnIxICYgKDE8PGZbaV0pKSAKeyAKZmxhZyA9IDE7IApicmVhazsgCn0gCn0gCmlmKGZsYWcpIApwcmludGYgKCJcbiBzdHJpbmcgYWNjZXB0ZWQiKTsgCmVsc2UgCnByaW50ZiAoIlxuIHN0cmluZyByZWplY3RlZCIpOyAKfSAKcmV0dXJuIDA7IAp9Cg==