Question

I need a program(code) in any programming language that performs the following operations: union, concatenation and conversion DFA-NDFA.

Answer 1

1.

C programming code for concatenation

#include <stdio.h>

#include <string.h>

int main()

{

char a[1000], b[1000];

printf("Enter the first string\n");

gets(a);

printf("Enter the second string\n");

gets(b);

strcat(a, b);

printf("String obtained on concatenation: %s\n", a);

return 0;

}

2.

// C program to find union of

// two sorted arrays

#include<stdio.h>

/* Function prints union of arr1[] and arr2[]

m is the number of elements in arr1[]

n is the number of elements in arr2[] */

int printUnion(int arr1[], int arr2[], int m, int n)

{

int i = 0, j = 0;

while (i < m && j < n)

{

if (arr1[i] < arr2[j])

printf(" %d ", arr1[i++]);

else if (arr2[j] < arr1[i])

printf(" %d ", arr2[j++]);

else

{

printf(" %d ", arr2[j++]);

i++;

}

}

/* Print remaining elements of the larger array */

while(i < m)

printf(" %d ", arr1[i++]);

while(j < n)

printf(" %d ", arr2[j++]);

}

/* Driver program to test above function */

int main()

{

int arr1[] = {1, 2, 4, 5, 6};

int arr2[] = {2, 3, 5, 7};

int m = sizeof(arr1)/sizeof(arr1[0]);

int n = sizeof(arr2)/sizeof(arr2[0]);

printUnion(arr1, arr2, m, n);

getchar();

return 0;

}

3.

C code to conversion DFA-NDFA

#include<stdio.h>

int Fa[10][10][10],states[2][10],row=0,col=0,sr=0,sc=0,th=0,

in,stat,new_state[10][10],max_inp=-1,no_stat;

FILE *fp;

int search(int search_var)

{

int i;

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

if(search_var == states[1][i])

return 1;

return 0;

}

int sort(int *arr,int count)

{

int temp,i,j;

for(i=0;i<count-1;i++)

{

for(j=i+1;j<count;j++)

{

if(arr[i]>=arr[j])

{

temp=arr[i];

arr[i]=arr[j];

arr[j]=temp;

}

}

}

return 0;

}

int checkcon(int *arr,int *count) //for doing this {4,1}={1,2,1}=={1,2}

{

int i,temp,j,k,c,t,m;

for(i=0;i<*count;i++)

{

if(arr[i]>row)

{

temp =arr[i];

c=0;

t=0;

while(new_state[arr[i]][t]!=-1)

{

t++;

c++;

}

//right shift from ith postion (c-2) th time

for(k=0;k<=c-2;k++)

{

for(j=9;j>=i+1+k;j--)

{

arr[j]=arr[j-1];

}

}

t=0;

for(j=i;j<c;j++)

{

arr[j]=new_state[temp][t];

t++;

}

}

}

c=0;

for(i=0;arr[i]!=-1;i++)

c++;

*count=c;

return 0;

}

int remove_duplicate(int *arr,int *count)

{

int i,j=0;

for(i=1;i<*count;i++)

{

if(arr[i]!=arr[j])

{

j++;

arr[j]=arr[i];

}

}

*count=j+1;

return 0;

}

int check(int i ,int j,int c,int *name)///for checking is this a new state?

{

int t,l,f;

for(l=0;l<=stat;l++)

{

t=0; f=0;

while(Fa[i][j][t]!=-1)

{

if(Fa[i][j][t]==new_state[l][t])

t++;

else

{

f=1;

break;

}

}

if((t==c)&&!f)

{

*name=l;

return 1;

}

}

return 0;

}

int trans(int i ,int j,int t,int c,int *count,int *arr)//transition o/p for particular i/p on states

{

int k=0,co,temp;

*count=0;

for(k=0;k<c;k++)

{

temp=Fa[i][j][k];

co=0;

while(Fa[temp][t][co]!=-1)

{

arr[*count]=Fa[temp][t][co++];

(*count)++;

}

}

return 0;

}

int nfa2dfa(int start,int end)

{

int j,t,c,i,k,count,arr[10],name,l;

for(i=start;i<=end;i++)

{

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

{

c=0;t=0;

while(Fa[i][j][t]>=0)

{

t++;

c++;

}

if(c>1)

{

if(check(i,j,c,&name)==0)

{

for(k=0;k<c;k++)

{

new_state[stat][k]=Fa[i][j][k];

for(l=0;states[1][l]!=-1;l++)

if(new_state[stat][k] == states[1][l]&& !search(stat))

states[1][no_stat++]=stat;

}

for(t=0;t<=max_inp;t++)

{

count=0;

for(k=0;k<10;k++)

arr[k]=-1;

trans(i,j,t,c,&count,arr);

checkcon(arr,&count);

sort(arr,count);

remove_duplicate(arr,&count);

for(k=0;k<count;k++)

Fa[stat][t][k]=arr[k];

}

Fa[i][j][0]=stat++;

for(t=1;t<c;t++)

Fa[i][j][t]=-1;

}

else

{

Fa[i][j][0]=name ;

for(t=1;t<c;t++)

Fa[i][j][t]=-1;

}

}

}

}

return 0;

}

int main()

{

int i,j,k,flag=0,start,end;

char c,ch;

fp=fopen("Nfa_ip.txt","r+");

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

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

states[i][j]=-1;

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

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

new_state[i][j]=-1;

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

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

for(k=0;k<10;k++)

Fa[i][j][k]=-1;

while(fscanf(fp,"%d",&in)!=EOF)

{

fscanf(fp,"%c",&c);

if(flag)

{

states[sr][sc++]=in;

if(c=='\n')

{

sr++;

sc=0;

}

}

else if(c=='#')

{

flag=1;

Fa[row][col][th]=in;

}

else if(!flag)

{

Fa[row][col][th]=in;

if(c==',')

{

th++;

}

else if(c=='\n')

{

if(max_inp<col)

max_inp=col;

col=0;

row++;

th=0;

}

else if(c!=',')

{

col++;

th=0;

}

}

}

no_stat=0;

i=0;

while(states[1][i++]!=-1)

no_stat++;

stat=row+1;

start=0;end=row;

while(1)

{

nfa2dfa(start,end);

start=end+1;

end=row;

if(start>end)

break;

}

printf("\n\nDFA IS : \n\n\n");

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

printf("\t%d",i);

printf("\n");

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

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

{

printf("%d-> |",i);

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

{

printf("%2d ",Fa[i][j][0]);

}

printf("\n");

}

printf("\n\n");

printf("Total Number Of State Is : %d \n\n",stat);

printf("Final States Are : ");

for(i=0;states[1][i]!=-1;i++)

printf("%d ",states[1][i]);

printf("\n\n");

getch();

return 0;

}