KTU
2019 Scheme
Compiler Design
ε-NFA to NFA

Conversion of epsilon NFA to NFA

Aim

Write a program to convert NFA with ε transition to NFA without ε transition.

Program

#include<stdio.h>
#include<string.h>
struct closures
{
	char state[20];
	int length;
	char closure[20][20];
}close[20];
int main()
{
	FILE *f1 = fopen("input.txt","r");
	int n,a_n;
	char alp[20];
	printf("Enter the number of alphabets.\n");
	scanf("%d",&a_n);
	printf("Enter the alphabets.\n");
	for(int i=0;i<a_n;i++)
	{
		scanf(" %c",&alp[i]);
	}
	printf("Enter the number of states.\n");
	scanf("%d",&n);
	char states[20][20];
	printf("Enter the states\n");
	for(int i=0;i<n;i++)
	{
		scanf("%s",states[i]);
	}
	char buffer[20][20];
	int idx = 0;
	for(int i=0;i<n;i++)
	{
		idx=0;
		char from[10],state[10],to[10],current_state[20];
		strcpy(buffer[idx++],states[i]);
		strcpy(current_state,states[i]);
		while(fscanf(f1,"%s %s %s",from,state,to)!=EOF)
		{
			if (strcmp(from,current_state)==0 && strcmp(state,"e")==0)
			{
				strcpy(buffer[idx++],to);
				strcpy(current_state,to); 
			}	
		}
		strcpy(close[i].state,states[i]);
		printf("Epsilon closure of %s is : ",close[i].state);
		close[i].length = idx;
		printf("{");
		for(int j=0;j<idx;j++)
		{
			strcpy(close[i].closure[j],buffer[j]);
			printf("%s",close[i].closure[j]);
		}
		printf("}");
		printf("\n");
		rewind(f1);	
	}
	for(int i=0;i<n;i++)
	{
		int length = close[i].length;
		for(int j=0;j<a_n;j++)
		{
			idx=0;
			char c_alp[20];
			c_alp[0] = alp[j];
			c_alp[1] = '\0';
			for(int k=0;k<length;k++)
			{
				char from[10],state[10],to[10];
				while(fscanf(f1,"%s %s %s",from,state,to)!=EOF)
				{
					if (strcmp(from,close[i].closure[k])==0 && strcmp(c_alp,state)==0)
					{
						for(int l=0;l<n;l++)
						{
							if(strcmp(to,close[l].state)==0)
							{
								int flag=0;
								for(int m=0;m<close[l].length;m++)
								{
									strcpy(buffer[idx++],close[l].closure[m]);	
								}
							}
						}
					}
				}
				rewind(f1); 
			}
			printf("NFA of %s on alphabet %c : ",close[i].state,alp[j]);
			printf("{");
			for(int k=0;k<idx;k++)
			{
				printf("%s",buffer[k]);
			}
			printf("}");
			printf("\n");	
		}	
	}
	return 0;
}

Input

q0 0 q0
q0 e q1
q1 1 q1
q1 e q2
q2 0 q2
q2 1 q2