enfa_to_nfa.c

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int st;
    struct node *link;
};

static int set[20],nostate,noalpha,s,notransition,nofinal,start,finalstate[20],c,r,buffer[20];
char alphabet[20];
static int e_closure[20][20]={0};
struct node * transition[20][20]={NULL};

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

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

void insert_trantbl(int r,char c,int s)
{
    int j;
    struct node *temp;
    j=findalpha(c);
    if (j==-1)
    {
        printf("\nError!!");
        exit(0);
    }
    temp=(struct node *)malloc(sizeof(struct node));
    temp->st=s;
    temp->link=transition[r][j];
    transition[r][j]=temp;
}

void unionclosure(int i)
{
    int j=0,k;
    while (e_closure[i][j]!=0)
    {
        k=e_closure[i][j];
        set[k]=1;
        j++;
    }
}

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

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])
                {
                    print_e_closure(j);
                }
            }
        }
    }
}

void main()
{
    int i,j,k,m,t,n;
    struct node *temp;
    printf("Enter the Number of Alphabets:");
    scanf("%d",&noalpha);
    getchar();
    printf("\nNOTE:-Use letter 'E' as Epsilon");
    printf("\nNOTE:-'E' must be the last character, if present");
    printf("\nEnter Alphabets:\n");
    for (i = 0; i < noalpha; i++)
    {
        alphabet[i]=getchar();
        getchar();
    }
    printf("\nEnter the Number of States:");
    scanf("%d",&nostate);
    printf("\nEnter the Initial State:");
    scanf("%d",&start);
    printf("\nEnter the Number of Final States:");
    scanf("%d",&nofinal);
    printf("\nEnter the Final State(s):");
    for (i = 0; i < nofinal; i++)
    {
        scanf("%d",&finalstate[i]);
    }
    printf("\nEnter the Number of Transitions:");
    scanf("%d",&notransition);
    printf("\nNOTE:-Input Transitions in the form:State Alphabet State");
    printf("\nNOTE:-State numbers must be greater than Zero");
    printf("\nEnter the Transitions:\n");
    for (i = 0; i < notransition; i++)
    {
        scanf("%d %c %d",&r,&c,&s);
        insert_trantbl(r,c,s);
    }
    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("\nEquivalent NFA without Epsilon");
    printf("\n******************************");
    printf("\nStart State:");
    print_e_closure(start);
    printf("\nAlphabets:");
    for (i = 0; i < noalpha; i++)
    {
        printf("%c ",alphabet[i]);
    }
    printf("\nStates:");
    for (i = 1; i <= nostate; i++)
    {
        print_e_closure(i);
    }
    printf("\nTransitions:");
    printf("\n************");
    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("\nFinal States:");
    findfinalstate();
}