Write program to minimize any given DFA.
Agendra-
1.Algorithm
2.Code
3.Input/output
1.Algorithms
- Get the start state, final state, input symbols as input and also give the edge value for each state.
- Maintain a stack required for transition from one state to other state.
- Using Pop or push function perform the insertion and deletion of elements when required.
- Finally conversion has been made to change from regular expression to minimized DFA and the output is displayed as DFA transition table.
2.Code-
#include<stdio.h>
#include<string.h>
#define STATES 50
struct Dstate
{
char name;
char StateString[STATES + 1];
char trans[10];
int is_final;
}
Dstates[50];
struct tran
{
char sym;
int tostates[50];
int notran;
};
struct state
{
int no;
struct tran tranlist[50];
};
int stackA[100], stackB[100], c[100], Cptr = -1, Aptr = -1, Bptr = -1;
struct state States[10];
char temp[STATES + 1], inp[10];
int nos, noi, nof, j, k, nods = -1;
void pushA(int z)
{
stackA[++Aptr] = z;
}
void pushB(int z)
{
stackB[++Bptr] = z;
}
int popA()
{
return stackA[Aptr--];
}
void copy(int i)
{
char temp[STATES + 1] = " ";
int k = 0;
Bptr = -1;
strcpy(temp, Dstates[i].StateString);
while (temp[k] != '\0')
{
pushB(temp[k] - '0');
k++;
}
}
int popB()
{
return stackB[Bptr--];
}
int peekA()
{
return stackA[Aptr];
}
int peekB()
{
return stackA[Bptr];
}
int seek(int arr[], int ptr, int s)
{
int i;
for (i = 0; i <= ptr; i++)
{
if (s == arr[i])
return 1;
}
return 0;
}
void sort()
{
int i, j, temp;
for (i = 0; i < Bptr; i++)
{
for (j = 0; j < (Bptr - i); j++)
{
if (stackB[j] > stackB[j + 1])
{
temp = stackB[j];
stackB[j] = stackB[j + 1];
stackB[j + 1] = temp;
}
}
}
}
void tostring()
{
int i = 0;
sort();
for (i = 0; i <= Bptr; i++)
{
temp[i] = stackB[i] + '0';
}
temp[i] = '\0';
}
void display_DTran()
{
int i, j;
printf("\n\t\t DFA transition table");
printf("\n\t\t ---------------------------------------------- ");
printf("\n States \tString \tInputs\n");
for (i = 0; i < noi; i++)
{
printf("\t %c", inp[i]);
}
printf("\n\t ------------------------------------------------- ");
for (i = 0; i < nods; i++)
{
if (Dstates[i].is_final == 0)
printf("\n%c", Dstates[i].name);
else
printf("\n*%c", Dstates[i].name);
printf("\t%s", Dstates[i].StateString);
for (j = 0; j < noi; j++)
{
printf("\t%c", Dstates[i].trans[j]);
}
}
printf("\n");
}
void move(int st, int j)
{
int ctr = 0;
while (ctr < States[st].tranlist[j].notran)
{
pushA(States[st].tranlist[j].tostates[ctr++]);
}
}
void lambda_closure(int st)
{
int ctr = 0, in_state = st, curst = st, chk;
while (Aptr != -1)
{
curst = popA();
ctr = 0;
in_state = curst;
while (ctr <= States[curst].tranlist[noi].notran)
{
chk = seek(stackB, Bptr, in_state);
if (chk == 0)
pushB(in_state);
in_state = States[curst].tranlist[noi].tostates[ctr++];
chk = seek(stackA, Aptr, in_state);
if (chk == 0 && ctr <= States[curst].tranlist[noi].notran)
pushA(in_state);
}
}
}
void main()
{
int i, final[20], start, fin = 0;
char c, ans, st[20];
printf("\n Enter no of states in NFA:");
scanf("%d", & nos);
for (i = 0; i < nos; i++)
{
States[i].no = i;
}
printf("\n Enter the start states:");
scanf("%d", & start);
printf("Enter the no of final states:");
scanf("%d", & nof);
printf("Enter the final states:\n");
for (i = 0; i < nof; i++)
scanf("%d", & final[i]);
printf("\n Enter the no of input symbols:");
scanf("%d", & noi);
c = getchar();
printf("Enter the input symbols:\n");
for (i = 0; i < noi; i++)
{
scanf("%c", & inp[i]);
c = getchar();
}
//g1inp[i]='e';
inp = [i] = ’e’;
printf("\n Enter the transitions:(-1 to stop)\n");
for (i = 0; i < nos; i++)
{
for (j = 0; j <= noi; j++)
{
States[i].tranlist[j].sym = inp[j];
k = 0;
ans = 'y';
while (ans == 'y')
{
printf("move(%d,%c);", i, inp[j]);
scanf("%d", & States[i].tranlist[j].tostates[k++]);
if ((States[i].tranlist[j].tostates[k - 1] == -1))
{
k--;
ans = 'n';
break;
}
}
States[i].tranlist[j].notran = k;
}
}
i = 0;
nods = 0, fin = 0;
pushA(start);
lambda_closure(peekA());
tostring();
Dstates[nods].name = 'A';
nods++;
strcpy(Dstates[0].StateString, temp);
while (i < nods)
{
for (j = 0; j < noi; j++)
{
fin = 0;
copy(i);
while (Bptr != -1)
{
move(popB(), j);
}
while (Aptr != -1)
lambda_closure(peekA());
tostring();
for (k = 0; k < nods; k++)
{
if ((strcmp(temp, Dstates[k].StateString) == 0))
{
Dstates[i].trans[j] = Dstates[k].name;
break;
}
}
if (k == nods)
{
nods++;
for (k = 0; k < nof; k++)
{
fin = seek(stackB, Bptr, final[k]);
if (fin == 1)
{
Dstates[nods - 1].is_final = 1;
break;
}
}
strcpy(Dstates[nods - 1].StateString, temp);
Dstates[nods - 1].name = 'A' + nods - 1;
Dstates[i].trans[j] = Dstates[nods - 1].name;
}
}
i++;
}
display_DTran();
}
Comments
Post a Comment