Program no 4

Objective: Program to find ε – closure of all states of any

given NFA with ε transition.

Definition: The ε closure(P) is a set of states which are

reachable from state P on ε-transitions.

Program

#include<stdio.h>

#include<stdlib.h>

struct node

int st;

struct node *link;

};

//RAJ PATEL

//CSE 3 YEAR

//ROLL_NO- 2108390109003

void findclosure(int,int);

void insert_trantbl(int ,char, int);

int findalpha(char);

void findfinalstate(void);

void unionclosure(int);

void print_e_closure(int);

static int
set[20],nostate,noalpha,s,notransition,nofinal,start,finalstate[20],c,r,buf
fer[20];

char alphabet[20];

static int e_closure[20][20]={0};

struct node * transition[20][20]={NULL};

//RAJ PATEL

//CSE 3 YEAR

//ROLL_NO- 2108390109003

2108390109003
void main()

int i,j,k,m,t,n;

struct node *temp;

printf("enter the number of alphabets?\n");

scanf("%d",&noalpha);

getchar();

printf("NOTE:- [ use letter e as epsilon]\n");

printf("NOTE:- [e must be last character ,if it is present]\n");

printf("\nEnter alphabets?\n");

for(i=0;i<noalpha;i++) {

alphabet[i]=getchar();

getchar(); }

printf("Enter the number of states?\n");

scanf("%d",&nostate);

printf("Enter the start state?\n");

scanf("%d",&start);

printf("Enter the number of final states?\n");

scanf("%d",&nofinal);

printf("Enter the final states?\n");

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

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

printf("Enter no of transition?\n");

scanf("%d",&notransition);

printf("NOTE:- [Transition is in the form--> qno alphabet qno]\

n",notransition);

printf("NOTE:- [States number must be greater than zero]\n");

printf("\nEnter transition?\n");

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

{ scanf("%d %c%d",&r,&c,&s);

insert_trantbl(r,c,s); }

printf("\n");

for(i=1;i<=nostate;i++) {

c=0;

2108390109003
 for(j=0;j<20;j++) {

buffer[j]=0;

e_closure[i][j]=0; }

findclosure(i,i); }

printf("E-CLOSURE OF STATES ARE:\n");

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

for(i=1;i<=nostate;i++) {

printf("state_no.-%d ",i);

print_e_closure(i);

printf("\n"); }}

//RAJ PATEL

//CSE 3 YEAR

//ROLL_NO- 2108390109003

void findclosure(int x,int sta)

struct node *temp;

int i;

if(buffer[x])

return;

e_closure[sta][c++]=x;

buffer[x]=1;

if(alphabet[noalpha-1]=='e' && transition[x][noalpha-1]!=NULL)

temp=transition[x][noalpha-1];

while(temp!=NULL) {

findclosure(temp->st,sta);

temp=temp->link;

} } }

void insert_trantbl(int r,char c,int s)

int j;

struct node *temp;

j=findalpha(c);

if(j==999) {

2108390109003
 printf("error\n");

exit(0);

temp=(struct node *) malloc(sizeof(struct node));

temp->st=s;

temp->link=transition[r][j];

transition[r][j]=temp;

//RAJ PATEL

//CSE 3 YEAR

//ROLL_NO- 2108390109003

int findalpha(char c){

int i;

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

if(alphabet[i]==c)

return i;

return(999);}

//RAJ PATEL

//CSE 3 YEAR

//ROLL_NO- 2108390109003

void print_e_closure(int i)

int j;

printf("{");

for(j=0;e_closure[i][j]!=0;j++)

printf("q%d,",e_closure[i][j]);

printf("}\t");}

Output
Enter the number of alphabets?

NOTE:- [ use letter e as epsilon]

NOTE:- [e must be last character ,if it is present]

2108390109003
Enter alphabets?

Enter the number of states?

Enter the start state?

Enter the number of final states?

Enter the final states?

Enter no of transition?

NOTE:- [Transition is in the form--> qno alphabet qno]

NOTE:- [States number must be greater than zero]

Enter transition?

1 a 1

1 e 2

2 b 2

2 e 3

3 c 3

E-CLOSURE OF STATES ARE:

-----------------------------------

state_no.-1 {q1,q2,q3,}

state_no.-2 {q2,q3,}

state_no.-3 {q3,}

2108390109003
 Program no 5

Objective: Convert NFA with ε transition to NFA without ε

transition.

Steps to Convert NFA with ε transition to NFA without

ε transition.

Step-1: Consider the two vertexes having the epsilon move. Here
in Fig.1 we have vertex v1 and vertex v2 having epsilon move from
v1 to v2.

Step-2: Now find all the moves to any other vertex that start
from vertex v2 (other than the epsilon move that is
considering). After finding the moves, duplicate all the moves that
start from vertex v2, with the same input to start from vertex v1
and remove the epsilon move from vertex v1 to vertex v2.

Step-3: See that if the vertex v1 is a start state or not. If

vertex v1 is a start state, then we will also make vertex v2 as a
start state. If vertex v1 is not a start state, then there will not
be any change.

Step-4: See that if the vertex v2 is a final state or not. If

vertex v2 is a final state, then we will also make vertex v1 as a
final state. If vertex v2 is not a final state, then there will not
be any change. Repeat the steps(from step 1 to step 4) until all
the epsilon moves are removed from the NFA. Now, to explain this
conversion, let us take an example.

2108390109003
 Program
#include<stdio.h>

#include<stdlib.h>

struct node

int st;

struct node *link;

};

//RAJ PATEL

//CSE 3 YEAR

//ROLL_NO- 2108390109003

void findclosure(int,int);

void insert_trantbl(int ,char, int);

int findalpha(char);

void findfinalstate(void);

void unionclosure(int);

void print_e_closure(int);

static int
set[20],nostate,noalpha,s,notransition,nofinal,start,finalstate[20],c,r,buf
fer[20];

char alphabet[20];

static int e_closure[20][20]={0};

struct node * transition[20][20]={NULL};

//RAJ PATEL

//CSE 3 YEAR

//ROLL_NO- 2108390109003

void main()

2108390109003
{

int i,j,k,m,t,n;

struct node *temp;

printf("enter the number of alphabets?\n");

scanf("%d",&noalpha);

getchar();

printf("NOTE:- [ use letter e as epsilon]\n");

printf("NOTE:- [e must be last character ,if it is present]\n");

printf("\nEnter alphabets?\n");

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

alphabet[i]=getchar();

getchar();

printf("Enter the number of states?\n");

scanf("%d",&nostate);

printf("Enter the start state?\n");

scanf("%d",&start);

printf("Enter the number of final states?\n");

scanf("%d",&nofinal);

printf("Enter the final states?\n");

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

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

printf("Enter no of transition?\n");

scanf("%d",&notransition);

printf("NOTE:- [Transition is in the form--> qno alphabet qno]\

n",notransition);

printf("NOTE:- [States number must be greater than zero]\n");

printf("\nEnter transition?\n");

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

2108390109003
 scanf("%d %c%d",&r,&c,&s);

insert_trantbl(r,c,s);

printf("\n");

for(i=1;i<=nostate;i++)

c=0;

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

buffer[j]=0;

e_closure[i][j]=0;

findclosure(i,i);

printf("Equivalent NFA without epsilon\n");

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

printf("start state:");

print_e_closure(start);

printf("\nAlphabets:");

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

printf("%c ",alphabet[i]);

printf("\n States :" );

for(i=1;i<=nostate;i++)

print_e_closure(i);

printf("\nTnransitions are...:\n");

//RAJ PATEL

//CSE 3 YEAR

2108390109003
//ROLL_NO- 2108390109003

for(i=1;i<=nostate;i++)

for(j=0;j<noalpha-1;j++)

for(m=1;m<=nostate;m++)

set[m]=0;

for(k=0;e_closure[i][k]!=0;k++)

t=e_closure[i][k];

temp=transition[t][j];

while(temp!=NULL)

unionclosure(temp->st);

temp=temp->link;

printf("\n");

print_e_closure(i);

printf("%c\t",alphabet[j] );

printf("{");

for(n=1;n<=nostate;n++)

if(set[n]!=0)

printf("q%d,",n);

printf("}");} }

printf("\n Final states:");

findfinalstate();

//RAJ PATEL

2108390109003
//CSE 3 YEAR

//ROLL_NO- 2108390109003

void findclosure(int x,int sta)

struct node *temp;

int i;

if(buffer[x])

return;

e_closure[sta][c++]=x;

buffer[x]=1;

if(alphabet[noalpha-1]=='e' && transition[x][noalpha-1]!=NULL)

temp=transition[x][noalpha-1];

while(temp!=NULL)

findclosure(temp->st,sta);

temp=temp->link;

} }}

void insert_trantbl(int r,char c,int s)

int j;

struct node *temp;

j=findalpha(c);

if(j==999)

printf("error\n");

exit(0);

temp=(struct node *) malloc(sizeof(struct node));

temp->st=s;

temp->link=transition[r][j];

transition[r][j]=temp;

2108390109003
//RAJ PATEL

//CSE 3 YEAR

//ROLL_NO- 2108390109003

int findalpha(char c)

int i;

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

if(alphabet[i]==c)

return i;

return(999);

//RAJ PATEL

//CSE 3 YEAR

//ROLL_NO- 2108390109003

void unionclosure(int i)

int j=0,k;

while(e_closure[i][j]!=0)

k=e_closure[i][j];

set[k]=1;

j++; }}

void findfinalstate()

int i,j,k,t;

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

for(j=1;j<=nostate;j++)

for(k=0;e_closure[j][k]!=0;k++)

if(e_closure[j][k]==finalstate[i])

2108390109003
 print_e_closure(j);

} }} }}

//RAJ PATEL

//CSE 3 YEAR

//ROLL_NO- 2108390109003

void print_e_closure(int i)

int j;

printf("{");

for(j=0;e_closure[i][j]!=0;j++)

printf("q%d,",e_closure[i][j]);

printf("}\t");

Output

enter the number of alphabets?

NOTE:- [ use letter e as epsilon]

NOTE:- [e must be last character ,if it is present]

Enter alphabets?

Enter the number of states?

Enter the start state?

2108390109003
Enter the number of final states?

Enter the final states?

Enter no of transition?

NOTE:- [Transition is in the form--> qno alphabet qno]

NOTE:- [States number must be greater than zero]

Enter transition?

1 a 1

1 e 2

2 b 2

2 e 3

3 c 3

Equivalent NFA without epsilon

-----------------------------------

start state:{q1,q2,q3,}

Alphabets:a b c e

States :{q1,q2,q3,} {q2,q3,} {q3,}

Tnransitions are...:

{q1,q2,q3,} a {q1,q2,q3,}

{q1,q2,q3,} b {q2,q3,}

{q1,q2,q3,} c {q3,}

{q2,q3,} a {}

{q2,q3,} b {q2,q3,}

{q2,q3,} c {q3,}

{q3,} a {}

{q3,} b {}

{q3,} c {q3,}

Final states:{q1,q2,q3,} {q2,q3,} {q3,}

2108390109003
 Program 6
Objective: Convert NFA to DFA

Conversion from NFA to DFA

Converting NFA to its equivalent DFA. In NFA, when a specific input
is given to the current state, the machine goes to multiple states.
It can have zero, one or more than one move on a given input symbol.
On the other hand, in DFA, when a specific input is given to the
current state, the machine goes to only one state. DFA has only one
move on a given input symbol.

Let, M = (Q, ∑, δ, q0, F) is an NFA which accepts the language L(M).

There should be equivalent DFA denoted by M' = (Q', ∑', q0', δ', F')
such that L(M) = L(M').

Steps for converting NFA to DFA:

Step 1: Initially Q' = ϕ

2108390109003
Step 2: Add q0 of NFA to Q'. Then find the transitions from this
start state.

Step 3: In Q', find the possible set of states for each input
symbol. If this set of states is not in Q', then add it to Q'.

Step 4: In DFA, the final state will be all the states which
contain F(final states of NFA)

2108390109003
 Program
#include<stdio.h>
#include<stdlib.h>
struct node
{
int st;
struct node *link;
};
struct node1
{

int nst[20];
};
//RAJ PATEL
//CSE 3 YEAR
//ROLL_NO.-2108390109003
void insert(int ,char, int);
int findalpha(char);
void findfinalstate(void);
int insertdfastate(struct node1);
int compare(struct node1,struct node1);
void printnewstate(struct node1);
static int
set[20],nostate,noalpha,s,notransition,nofinal,start,finalstate[20],
c,r,buffer[20];
int complete=-1;
char alphabet[20];
static int eclosure[20][20]={0};
struct node1 hash[20];
struct node * transition[20][20]={NULL};
//RAJ PATEL
//CSE 3 YEAR

2108390109003
//ROLL_NO.-2108390109003
void main()
{
int i,j,k,m,t,n,l;
struct node *temp;
struct node1 newstate={0},tmpstate={0};

printf("Enter the number of alphabets?\n");

printf("NOTE:- [ use letter e as epsilon]\n");
printf("NOTE:- [e must be last character ,if it is present]\n");
printf("\nEnter No of alphabets and alphabets?\n");
scanf("%d",&noalpha);
getchar();
for(i=0;i<noalpha;i++)
{

alphabet[i]=getchar();
getchar();
}
//RAJ PATEL
//CSE 3 YEAR
//ROLL_NO.-2108390109003
printf("Enter the number of states?\n");
scanf("%d",&nostate);
printf("Enter the start state?\n");
scanf("%d",&start);
printf("Enter the number of final states?\n");
scanf("%d",&nofinal);
printf("Enter the final states?\n");
for(i=0;i<nofinal;i++)
scanf("%d",&finalstate[i]);
printf("Enter no of transition?\n");

2108390109003
 scanf("%d",&notransition);
printf("NOTE:- [Transition is in the form–> qno alphabet qno]\
n",notransition);
printf("NOTE:- [States number must be greater than zero]\n");
printf("\nEnter transition?\n");
//RAJ PATEL
//CSE 3 YEAR
//ROLL_NO.-2108390109003

for(i=0;i<notransition;i++)
{
scanf("%d %c%d",&r,&c,&s);
insert(r,c,s);
}
for(i=0;i<20;i++)
{
for(j=0;j<20;j++)
hash[i].nst[j]=0;
}
complete=-1;
i=-1;
printf("\nEquivalent DFA.....\n");
printf(".......................\n");

printf("Trnsitions of DFA\n");

newstate.nst[start]=start;
insertdfastate(newstate);
while(i!=complete)
{ i++;

2108390109003
 newstate=hash[i];
for(k=0;k<noalpha;k++)
{
c=0;
for(j=1;j<=nostate;j++)
set[j]=0;
for(j=1;j<=nostate;j++)
{
l=newstate.nst[j];
if(l!=0)
{
temp=transition[l][k];
while(temp!=NULL)
{
if(set[temp->st]==0)
{
c++;
set[temp->st]=temp->st;
}
temp=temp->link;
}
}
}
//RAJ PATEL
//CSE 3 YEAR
//ROLL_NO.-2108390109003
printf("\n");
if(c!=0)
{
for(m=1;m<=nostate;m++)
tmpstate.nst[m]=set[m];

2108390109003
 insertdfastate(tmpstate);

printnewstate(newstate);
printf("%c\t",alphabet[k]);
printnewstate(tmpstate);
printf("\n");
}
else
{
printnewstate(newstate);
printf("%c\t", alphabet[k]);
printf("NULL\n");
}
//RAJ PATEL
//CSE 3 YEAR
//ROLL_NO.-2108390109003
}
}
printf("\nStates of DFA:\n");
for(i=0;i<=complete;i++)
printnewstate(hash[i]);
printf("\n Alphabets:\n");
for(i=0;i<noalpha;i++)
printf("%c\t",alphabet[i]);
printf("\n Start State:\n");
printf("q%d",start);
printf("\nFinal states:\n");
findfinalstate();

}
int insertdfastate(struct node1 newstate)
{

2108390109003
 int i;
for(i=0;i<=complete;i++)
{
if(compare(hash[i],newstate))
return 0;
}
complete++;
hash[complete]=newstate;
return 1;
}
int compare(struct node1 a,struct node1 b)
{
int i;
//RAJ PATEL
//CSE 3 YEAR
//ROLL_NO.-2108390109003

for(i=1;i<=nostate;i++)
{
if(a.nst[i]!=b.nst[i])
return 0;
}
return 1;

void insert(int r,char c,int s)

{
int j;
struct node *temp;
j=findalpha(c);

2108390109003
 if(j==999)
{
printf("error\n");
exit(0);
}
temp=(struct node *) malloc(sizeof(struct node));
temp->st=s;
temp->link=transition[r][j];
transition[r][j]=temp;
}

int findalpha(char c)
{
int i;
for(i=0;i<noalpha;i++)
if(alphabet[i]==c)
return i;

return(999);

}
//RAJ PATEL
//CSE 3 YEAR
//ROLL_NO.-2108390109003

void findfinalstate()
{
int i,j,k,t;

for(i=0;i<=complete;i++)
{

2108390109003
 for(j=1;j<=nostate;j++)
{
for(k=0;k<nofinal;k++)
{
if(hash[i].nst[j]==finalstate[k])
{
printnewstate(hash[i]);
printf("\t");
j=nostate;
break;
} } }}}
void printnewstate(struct node1 state)
{
int j;
printf("{");
for(j=1;j<=nostate;j++)
{
if(state.nst[j]!=0)
printf("q%d,",state.nst[j]);
}
printf("}\t");

}
//RAJ PATEL
//CSE 3 YEAR
//ROLL_NO.-2108390109003

Output

Enter No of alphabets and alphabets?

2
a
b

2108390109003
Enter the number of states?
4
Enter the start state?
1
Enter the number of final states?
2
Enter the final states?
3
4
Enter no of transition?
8
NOTE:- [Transition is in the form–> qno alphabet qno]
NOTE:- [States number must be greater than zero]

Enter transition?
1 a 1
1 b 1
1 a 2
2 b 2
2 a 3
3 a 4
3 b 4
4 b 3

Equivalent DFA.....
.......................
Trnsitions of DFA

{q1,} a {q1,q2,}

{q1,} b {q1,}

2108390109003
{q1,q2,} a {q1,q2,q3,}

{q1,q2,} b {q1,q2,}

{q1,q2,q3,} a {q1,q2,q3,q4,}

{q1,q2,q3,} b {q1,q2,q4,}

{q1,q2,q3,q4,} a {q1,q2,q3,q4,}

{q1,q2,q3,q4,} b {q1,q2,q3,q4,}

{q1,q2,q4,} a {q1,q2,q3,}

{q1,q2,q4,} b {q1,q2,q3,}

States of DFA:
{q1,} {q1,q2,} {q1,q2,q3,} {q1,q2,q3,q4,} {q1,q2,q4,}
Alphabets:
a b
Start State:
q1
Final states:
{q1,q2,q3,} {q1,q2,q3,q4,} {q1,q2,q4,}

Program 7
Objective: Minimize any given DFA.

2108390109003
Minimization of DFA
Minimization of DFA means reducing the number of states from given
FA. Thus, we get the FSM(finite state machine) with redundant states
after minimizing the FSM.

We have to follow the various steps to minimize the DFA. These are
as follows:

Step 1: Remove all the states that are unreachable from the initial
state via any set of the transition of DFA.

Step 2: Draw the transition table for all pair of states.

Step 3: Now split the transition table into two tables T1 and T2. T1
contains all final states, and T2 contains non-final states.

Step 4: Find similar rows from T1 such that:

1. 1. δ (q, a) = p
2. 2. δ (r, a) = p

That means, find the two states which have the same value of a and b
and remove one of them.

Step 5: Repeat step 3 until we find no similar rows available in the

transition table T1.

Step 6: Repeat step 3 and step 4 for table T2 also.

Step 7: Now combine the reduced T1 and T2 tables. The combined

transition table is the transition table of minimized DFA.

Program
//RAJ PATEL

//CSE 3 YEAR

2108390109003
//ROLL_NO-2108390109003

#include <stdio.h>

#include <stdlib.h>

struct state{

int input[100];

int isFinal;

int current_set;

int last_set;

int value;

}table[100];

char input[100];

struct state optimized[100];

void compute_value(int ,int);

int generate_current_set(int );

void current_to_last(int );

void change_name(int,int,int);

void print(struct state *,int,int);

//RAJ PATEL

//CSE 3 YEAR

//ROLL_NO-2108390109003

int main()

int n,m,t=-1,set=2,i,j,key,q,flag,p,u;

printf("How many states in DFA");

scanf("%d",&n);

printf("How many inputs in DFA");

scanf("%d",&m);

fflush(stdin);

gets(input);

for(int i=0;i<n;i++)

printf("Input state table for %d\n",i);

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

2108390109003
 {

printf("Input %c \t",input[j]);

scanf("%d",&table[i].input[j]);

printf("Is %d a final state",i);

scanf("%d",&table[i].last_set);

table[i].isFinal=table[i].last_set;

flag=0;

q=1;

p=3;

print(table,n-1,m);

u=0;

//RAJ PATEL

//CSE 3 YEAR

//ROLL_NO-2108390109003

while(p!=q)

//compute function calculates the set value of every state and then
adds all the set values in array aar1 and returns the size of array aar1

if(flag==1)

q=p;

compute_value(n,m);

p=generate_current_set(n);

current_to_last(n);

printf("\n\n\t %d equivalent \t\t",++u);

for(int i=0;i<n;i++)

printf("%d",table[i].current_set);

printf("\n");

flag=1;

change_name(n,p,m);

2108390109003
//printf("%d",p);

print(optimized,p,m);

void compute_value(int n,int m)

int ans,c;

for(int i=0;i<n;i++)

ans=0;

c=1;

for(int j=0;j<m;j++)

ans=ans+table[table[i].input[j]].last_set*c;

c*=10;

table[i].value=ans;}}

//RAJ PATEL

//CSE 3 YEAR

//ROLL_NO-2108390109003

int generate_current_set(int n)

int c=-1,flag;

for(int i=0;i<n;i++)

flag=0;

for( int j=i-1;j>=0;j--)

if(table[i].last_set==table[j].last_set&&table[i].value==table[j].value)

table[i].current_set=table[j].current_set;

flag=1;

break; } }

if(flag!=1)

2108390109003
 { c++;

table[i].current_set=c; }}

return c;

void current_to_last(int n)

for(int i=0;i<n;i++)

table[i].last_set=table[i].current_set;

void change_name(int n,int c,int m)

for(int i=0;i<=c;i++)

for(int j=0;j<n;j++)

if(table[j].current_set==i)

for(int k=0;k<m;k++)

optimized[i].input[k]=table[j].input[k];

optimized[i].isFinal=table[j].isFinal;

break;

}}}

//RAJ PATEL

//CSE 3 YEAR

//ROLL_NO-2108390109003

for(int i=0;i<=c;i++)

for(int j=0;j<m;j++){

optimized[i].input[j]=table[optimized[i].input[j]].current_set; }}}

void print(struct state* tabl,int n,int m)

int i,j;

2108390109003
 printf("\n\n\n\ns/i");

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

printf("\t%c",input[j]);

printf("\n");

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

printf("%d",i);

if(tabl[i].isFinal==1)

printf("*\t");

else

printf("\t");

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

printf("%d\t",tabl[i].input[j]);

printf("\n");

//RAJ PATEL

//CSE 3 YEAR

//ROLL_NO-2108390109003

Output

How many states in DFA5

How many inputs in DFA2

ab

Input state table for 0

Input a 1

Input b 2

2108390109003
Is 0 a final state0

Input state table for 1

Input a 1

Input b 3

Is 1 a final state0

Input state table for 2

Input a 1

Input b 2

Is 2 a final state0

Input state table for 3

Input a 1

Input b 4

Is 3 a final state0

Input state table for 4

Input a 1

Input b 2

Is 4 a final state1

s/i a b

0 1 2

1 1 3

2 1 2

3 1 4

4* 1 2

1 equivalent 00012

2 equivalent 01023

3 equivalent 01023

s/i a b

0 1 0

1 1 2

2 1 3

2108390109003
3* 1 0

2108390109003