Program: 6

Objective: Write program to convert NFA to DFA

#include <stdio.h>

#include <string.h>

#include <math.h>

int ninputs;

int dfa[100][2][100] = {0};

int state[10000] = {0};

char str[1000];

int go[10000][2] = {0};

int arr[10000] = {0};

int main()

int st, fin, in;

int f[10];

int i, j, k, l;

int curr1, flag;

int p, q, r, rel;

printf("\nFollow one-based indexing\n");

printf("\nEnter number of states: ");

scanf("%d", &st);

printf("Give state numbers from 0 to %d\n", st - 1);

for (i = 0; i < st; i++)

state[(int)pow(2, i)] = 1;

printf("\nEnter number of final states: ");

scanf("%d", &fin);

printf("Enter final states:\n");

for (i = 0; i < fin; i++)

scanf("%d", &f[i]);

printf("\nEnter number of transition rules: ");

printf("\nEnter rules as: initial_state input(0/1) final_state\n");

for (i = 0; i < rel; i++)

scanf("%d %d %d", &p, &q, &r);

dfa[p][q][r] = 1;

printf("\nEnter initial state: ");

scanf("%d", &in);

in = pow(2, in);

printf("\n--- DFA Transitions ---\n");

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 += 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 (i = 0; i < x; i++)

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);

new |= go[h][j];

if (state[new] == 0)

arr[x++] = new;

state[new] = 1;

go[arr[i]][j] = new;

printf("\n--- DFA Table ---\n");

printf("STATE\t0\t1\n");

for (i = 0; i < 10000; i++)

if (state[i] == 1)

int y = 0;

if (i == 0)

printf("q0 ");

else
 {

for (j = 0; j < st; j++)

if (i & (1 << j))

printf("q%d ", j);

y += pow(2, j);

printf("\t%d\t%d\n", go[y][0], go[y][1]);

for (int test = 0; test < 3; test++)

printf("\nEnter string: ");

scanf("%s", str);

l = strlen(str);

curr1 = in;

flag = 0;

printf("Path: %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("String Accepted\n");

else

printf("String Rejected\n");

return 0;

}
 Program: 7

Objective: Write a program for construction of minimized DFA from a given regular expression
using C.

Algorithm:

1. Get the start state, final state, input symbols as input and also give the edge value for each state.

2. Maintain a stack required for transition from one state to other state.

3. Using Pop or push function perform the insertion and deletion of elements when required.

4. Finally conversion has been made to change from regular expression tominimized DFA and the
output is displayed as DFA transition table.

Program:

#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];

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--];

int popB()

return stackB[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, t;

for (i = 0; i < Bptr; i++)

for (j = 0; j < (Bptr - i); j++)

if (stackB[j] > stackB[j + 1])

t = stackB[j];

stackB[j] = stackB[j + 1];

stackB[j + 1] = t;

void tostring()

int i = 0;

sort();

for (i = 0; i <= Bptr; i++)

temp[i] = stackB[i] + '0';

temp[i] = '\0';

void copy(int i)

int k = 0;

Bptr = -1;

while (Dstates[i].StateString[k] != '\0')

pushB(Dstates[i].StateString[k] - '0');
 k++;

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)

pushA(in_state);

}
}

void display_DTran()

int i, j;

printf("\n\t\t DFA transition table");

printf("\n\t ---------------------------------------------- ");

printf("\n States \tString \t");

for (i = 0; i < noi; i++)

printf("%c\t", 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\t", Dstates[i].StateString);

for (j = 0; j < noi; j++)

printf("%c\t", Dstates[i].trans[j]);

printf("\n");

int main()

int i, final[20], start, fin = 0;

char c, ans;

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 state: ");

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);

getchar();

printf("Enter the input symbols:\n");

for (i = 0; i < noi; i++)

scanf("%c", &inp[i]);

getchar();

inp[noi] = '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;

nods = 0;

pushA(start);

lambda_closure(start);

tostring();

strcpy(Dstates[0].StateString, temp);

Dstates[0].name = 'A';

nods++;

i = 0;

while (i < nods)

for (j = 0; j < noi; j++)

fin = 0;

copy(i);

while (Bptr != -1)

move(popB(), j);

while (Aptr != -1)

lambda_closure(stackA[Aptr]);

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++)

if (seek(stackB, Bptr, final[k]))

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();

return 0;

OUTPUT: