Scribd Logo
Upload

Welcome to Scribd!

  • 41 views

    Q.9 Design A Program To Convert NFA To DFA. Program

    Uploaded by

    Aashutosh Tiwari
    The program converts a non-deterministic finite automaton (NFA) to a deterministic finite automaton (DFA) in the following steps: 1) It initializes the NFA states and transitions from user input. 2) It performs lambda closure on the start state to determine all reachable states. 3) It determines the DFA states by grouping NFA reachable states and outputs the DFA transition table.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Q.9 Design A Program To Convert NFA To DFA. Program

    Uploaded by

    Aashutosh Tiwari
    41 views12 pages
    The program converts a non-deterministic finite automaton (NFA) to a deterministic finite automaton (DFA) in the following steps: 1) It initializes the NFA states and transitions from user input. 2) It performs lambda closure on the start state to determine all reachable states. 3) It determines the DFA states by grouping NFA reachable states and outputs the DFA transition table.

    Original Title

    NFA to DFA.docx

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The program converts a non-deterministic finite automaton (NFA) to a deterministic finite automaton (DFA) in the following steps: 1) It initializes the NFA states and transitions from user input. 2) It performs lambda closure on the start state to determine all reachable states. 3) It determines the DFA states by grouping NFA reachable states and outputs the DFA transition table.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    41 views12 pages

    Q.9 Design A Program To Convert NFA To DFA. Program

    Uploaded by

    Aashutosh Tiwari
    The program converts a non-deterministic finite automaton (NFA) to a deterministic finite automaton (DFA) in the following steps: 1) It initializes the NFA states and transitions from user input. 2) It performs lambda closure on the start state to determine all reachable states. 3) It determines the DFA states by grouping NFA reachable states and outputs the DFA transition table.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 12

    Q.9 Design a program to convert NFA to DFA.

    Program:
    //NFA to DFA conversion

    #include <stdio.h>

    #include <string.h>

    #define STATES 50

    structDstate

    char name;

    char StateString[STATES+1];

    char trans[10];

    intis_final;

    }Dstates[50];

    structtran

    char sym;

    inttostates[50];

    intnotran;

    };

    struct state

    int no;

    structtrantranlist[50];

    };

    intstackA[100],stackB[100],C[100],Cptr=-1,Aptr=-1,Bptr=-1;

    struct state States[STATES];

    char temp[STATES+1],inp[10];
    intnos,noi,nof,j,k,nods=-1;

    void pushA(int z)

    {stackA[++Aptr]=z;}

    void pushB(int z)

    {stackB[++Bptr]=z;}

    intpopA()

    {return stackA[Aptr--];}

    void copy(inti)

    char temp[STATES+1]=" ";

    int k=0;

    Bptr=-1;

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

    while(temp[k]!='\0')

    pushB(temp[k]-'0');

    k++;

    intpopB()

    {return stackB[Bptr--];}

    intpeekB()

    {return stackA[Bptr];}

    intpeekA()

    {return stackA[Aptr];}

    int seek(intarr[],intptr,int s)

    {
    inti;

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

    if(s==arr[i])

    return 1;

    return 0;

    void sort()

    inti,j,temp;

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

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

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

    temp=stackB[j];

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

    stackB[j+1]=temp;

    void tostring()

    inti=0;
    sort();

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

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

    temp[i]='\0';

    void display_DTran()

    inti,j;

    printf("\n\t\t DFA Transition Table ");

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

    printf("\nStates\tString\tInputs\n ");

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

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

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

    printf("\n");

    void move(intst,int j)

    intctr=0;

    while(ctr<States[st].tranlist[j].notran)

    pushA(States[st].tranlist[j].tostates[ctr++]);

    void lambda_closure(intst)

    intctr=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 &&ctr<=States[curst].tranlist[noi].notran)

    pushA(in_state);

    main()

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

    char c,ans,st[20];

    printf("\nEnter no. of states in NFA : ");

    scanf("%d",&nos);

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

    {States[i].no=i;}

    printf("\nEnter the start state : ");

    scanf("%d",&start);

    printf("Enter the no. of final states : ");

    scanf("%d",&nof);

    printf("\nEnter the final states : \n");

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

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

    printf("\nEnter the no. of input symbols : ");


    scanf("%d",&noi);

    c=getchar();

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

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

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

    c=getchar();

    inp[i]='e';

    printf("\nEnter 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;

    //Conversion

    i=0;nods=0;fin=0;

    pushA(start);

    lambda_closure(peekA());

    tostring();

    Dstates[nods].name='A';

    nods++;

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

    while(i<nods)

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

    fin=0;

    copy(i);

    while(Bptr!=-1)

    move(popB(),j);

    }
    while(Aptr!=-1)

    lambda_closure(peekA());

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

    fin=seek(stackB,Bptr,final[k]);

    if(fin==1)

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

    Output:

    You might also like