-
-
Save kipawa/10fec56cab1f8d0c33a9 to your computer and use it in GitHub Desktop.
/* A program to convert NFA to DFA using conversion table | |
Author - Kipawa | |
Technique used - Bitmasking | |
NOTE - | |
1. If your states are q0, q1, q2 they will be represented as follows (in the table) | |
q0 = 2^0 = 1 | |
q1 = 2^1 = 2 | |
q2 = 2^2 = 4 | |
2. Similarly union of states will be represented as - | |
q0,q1 = 2^0 + 2^1 = 3 | |
q1, q2 = 2^1 + 2^2 = 6 | |
q0,q1,q2 = 2^0 + 2^1 + 2^2 = 7 | |
3. Do not give any condition for "phi"... | |
That case is not handled... (Coz I m Lazy :P) | |
4. Follow zero based indexing everywhere | |
5. Program assumes that if "Number of states are = n", then they are numbered as q0, q1, q2 ... q(n-1) | |
6. If you find any bug, msg me and forgive me for the errors | |
*/ | |
#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("\nFollow the one based indexing\n"); | |
printf("\nEnter the number of states::"); | |
scanf("%d",&st); | |
printf("\nGive state numbers from 0 to %d",st-1); | |
for(i=0;i<st;i++) | |
state[(int)(pow(2,i))] = 1; | |
printf("\nEnter number of final states\t"); | |
scanf("%d",&fin); | |
printf("\nEnter final states::"); | |
for(i=0;i<fin;i++) | |
{ | |
scanf("%d",&f[i]); | |
} | |
int p,q,r,rel; | |
printf("\nEnter the number of rules according to NFA::"); | |
scanf("%d",&rel); | |
printf("\n\nDefine transition rule as \"initial state input symbol final state\"\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("\nEnter initial state::"); | |
scanf("%d",&in); | |
in = pow(2,in); | |
i=0; | |
printf("\nSolving 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("\nThe 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("\nEnter string"); | |
scanf("%s",str); | |
l = strlen(str); | |
curr1 = in; | |
flag = 0; | |
printf("\nString takes the following path-->\n"); | |
printf("%d-",curr1); | |
for(i=0;i<l;i++) | |
{ | |
curr1 = go[curr1][str[i]-'0']; | |
printf("%d-",curr1); | |
} | |
printf("\nFinal state - %d\n",curr1); | |
for(i=0;i<fin;i++) | |
{ | |
if(curr1 & (1<<f[i])) | |
{ | |
flag = 1; | |
break; | |
} | |
} | |
if(flag) | |
printf("\nString Accepted"); | |
else | |
printf("\nString Rejected"); | |
} | |
return 0; | |
} | |
is a nice code,
its just when I tried running on Turbo c compiler, is reports too many global data file defined, and I don't know what to do
explain the code please
can u please tell a sample input and output for this code
try copying the code to code blocks, it will work there
Can somebody please give a sample input? Pleasee, thanks!
Can somebody please give a sample input? Pleasee, thanks!
Follow the one based indexing
Enter the number of states::3
Give state numbers from 0 to 2
Enter number of final states 1
Enter final states::4
Enter the number of rules according to NFA::4
Define transition rule as "initial state input symbol final state"
1 0 1
1 1 1
1 0 2
2 0 4
Enter initial state::1
Solving according to DFA1-0-->0
1-1-->0
2-0-->6
2-1-->2
4-0-->0
4-1-->0
for 0 ---- for 0 ----
The total number of distinct states are::
STATE 0 1
q0 0 0
q0 0 0
q1 6 2
q2 0 0
q1 q2 0 0
Follow the one based indexing
Enter the number of states::3
Give state numbers from 0 to 2
Enter number of final states 1
Enter final states::4
Enter the number of rules according to NFA::4
Define transition rule as "initial state input symbol final state"
1 0 1
1 1 1
1 0 2
2 0 4
Enter initial state::1
Solving according to DFA1-0-->0
1-1-->0
2-0-->6
2-1-->2
4-0-->0
4-1-->0
for 0 ---- for 0 ----
The total number of distinct states are::
STATE 0 1
q0 0 0
q0 0 0
q1 6 2
q2 0 0
q1 q2 0 0
Enter stringabbb
String takes the following path-->
2-0-0-0-0-
Final state - 0
String Rejected
Enter stringabba
String takes the following path-->
2-0-0-0-0-
Final state - 0
String Rejected
Enter string
Please tell what string to enter???
is this code using subset construction algorithm?
The string is getting rejected please resolve the string rejection problem thank you!!
thanks for the opportunity