Re-dfa Very Small N Simplified
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Re-dfa Very Small N Simplified as PDF for free.
More details
- Words: 733
- Pages: 6
/*PROGRAM FOR REGULAR EXPRESSION TO DFA*/ /*NAME: CLASS:TEIT ROLL NO.: */ #include<stdio.h> #include char re[10],opr_stack[10],temp; int i,j,state_top=0,lc=0,priority,state=0,opr_top=0,dlc=0,initial,final; struct nfae_dfa { char symbol; //n[]contains NFAe table AND d[]contain DFA table. int from,to; }n[50],d[50],state_stack[50],buff; //----------------------------------------------------void state_push(struct nfae_dfa a) //state stack push operation. { state_stack[state_top]=a; state_top++; } struct nfae_dfa state_pop() //state stack operation. { state_stack[state_top].symbol='-'; state_top--; return(state_stack[state_top]); } void opr_push(char a) //Operator stack push operation. { opr_stack[opr_top]=a; opr_top++; } char opr_pop() //Operato stack pop operatrion. { opr_stack[opr_top]='-'; opr_top--; return(opr_stack[opr_top]); } int validation(char str) { if(str>='a'&& str<='z') return(0); else if(str=='(') return(1); else if(str==')') return(2); else if(str=='+') return(3); else if(str=='.') return(4); else if(str=='^') return(5); else if(str=='*') return(6); else if(str=='#')
//checking the encounterd character
return(7); } void construct_dfa() //construct DFA from NFAe. { for(i=0;i
}
table.
} } for(i=0;i<=lc;i++)
//move all the state which is from without'e'to DF
if(n[i].symbol!='E')
{
d[dlc]=n[i]; dlc++; } } void new_state(char symbol) //creating new state.
{
}
buff.symbol=symbol;//crating new state. buff.from=state;// " buff.to=++state;// " n[lc]=buff; // Enterint state into nfae table. state_push(buff);//pushing to the stack. lc++; //Incrementing table conuter. state++; //Incrementing state conuter.
void check_operator() //This func is for checking whether there is operator at top op_stack { //if yes then perform the joining operation according to operator at top. struct nfae_dfa buff1,buff2; if(opr_top!=0) { temp=opr_pop(); priority=validation(temp); if(priority==1) { opr_push(temp); } else if(priority== 4) //in case of operator. { buff2=state_pop(); buff1=state_pop(); buff.symbol='E'; // Creating new 'E' state buff.from=buff1.to; // " buff.to=buff2.from; // " n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.symbol='X'; buff.from=buff1.from; //Initial state. buff.to=buff2.to; //Final state. state_push(buff); //Pushing initial & final state to the stack. } else if(priority==3) //Incase of operator + { buff2=state_pop(); buff1=state_pop(); buff.symbol='E'; // Creating new 'E' state buff.from=state; buff.to=buff1.from; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.from=state; buff.to=buff2.from; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.from=buff1.to;
buff.to=state+1; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.from=buff2.to; buff.to=state+1; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.symbol='X'; buff.from=state; buff.to=state+1; state_push(buff);
//Initial state. //Final state. //Pushing initial & final state to the stack.
state=state+2; } else if(priority==6) //when ^* found. { buff1=state_pop(); buff.symbol='E'; buff.from=buff1.to; //Creating E state by combining buff.to=buff1.from; //final to initial state. n[lc]=buff; //Entering state into nfae table. lc++; //Incrementing table counter. buff.from=state; buff.to=state+1; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.from=state; buff.to=buff2.from; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.from=buff1.to; buff.to=state+1; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.symbol='X'; buff.from=state; buff.to=state+1; state_push(buff);
//Initial state. //Final state. //Pushing initial & final state to the stack.
state=state+2; } else if(priority==7) //incase of ^#. { buff1=state_pop(); buff.symbol='E'; buff.from=buff1.to;//Creating E state by combining. buff.to=buff1.from;//Final to initial state. n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.from=state;
buff.to=buff1.from; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.from=buff1.to; buff.to=state+1; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.symbol='X'; state_push(buff); state=state+2; }
//Pushing initial & final state to the stack.
}
} void print_nfae() { printf("\n\t--------------NFAe-----------------\n"); printf("\n\t| FROM\t|\t|\tSYMB |\n"); printf("\n\t-----------------------------------\n"); for(i=0;i<=lc;i++) printf("\n\t| %d\t|\t %d\t|\t %c |",n[i].from,n[i].to,n[i].symbol); printf("\n\n\t--------------------------------"); buff=state_pop(); initial=buff.from; final=buff.to; printf("\n\tstart state: %d and End state:%d",initial,final); } void print_dfa() { printf("\n\n\t-----------------DFA-------------\n"); printf("\n\t|from\t|\tTO\t|\tSYMB |\n"); printf("\n\t------------------------------------"); for(i=0;i
break; case 1: opr_push(re[i]); //push ( to operator stack. break; case 2: while(opr_pop()!='(') //pop until '(' found. opr_top--; check_operator(); //check whether opr_stack contain operator. break; case 3: opr_push(re[i]); //+ operator found push on to opr_stack. break; case 4: opr_push(re[i]); //. operator found push on to opr_stack. break; case 5: i++; // ^operator found take its next operator by incrementing i++. opr_push(re[i]); //Here operator will be it whether * or #. check_operator(); //check whether opr_stack contain operator. break; } } print_nfae(); construct_dfa(); print_dfa(); getch(); }
//checking the encounterd character
return(7); } void construct_dfa() //construct DFA from NFAe. { for(i=0;i
}
table.
} } for(i=0;i<=lc;i++)
//move all the state which is from without'e'to DF
if(n[i].symbol!='E')
{
d[dlc]=n[i]; dlc++; } } void new_state(char symbol) //creating new state.
{
}
buff.symbol=symbol;//crating new state. buff.from=state;// " buff.to=++state;// " n[lc]=buff; // Enterint state into nfae table. state_push(buff);//pushing to the stack. lc++; //Incrementing table conuter. state++; //Incrementing state conuter.
void check_operator() //This func is for checking whether there is operator at top op_stack { //if yes then perform the joining operation according to operator at top. struct nfae_dfa buff1,buff2; if(opr_top!=0) { temp=opr_pop(); priority=validation(temp); if(priority==1) { opr_push(temp); } else if(priority== 4) //in case of operator. { buff2=state_pop(); buff1=state_pop(); buff.symbol='E'; // Creating new 'E' state buff.from=buff1.to; // " buff.to=buff2.from; // " n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.symbol='X'; buff.from=buff1.from; //Initial state. buff.to=buff2.to; //Final state. state_push(buff); //Pushing initial & final state to the stack. } else if(priority==3) //Incase of operator + { buff2=state_pop(); buff1=state_pop(); buff.symbol='E'; // Creating new 'E' state buff.from=state; buff.to=buff1.from; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.from=state; buff.to=buff2.from; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.from=buff1.to;
buff.to=state+1; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.from=buff2.to; buff.to=state+1; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.symbol='X'; buff.from=state; buff.to=state+1; state_push(buff);
//Initial state. //Final state. //Pushing initial & final state to the stack.
state=state+2; } else if(priority==6) //when ^* found. { buff1=state_pop(); buff.symbol='E'; buff.from=buff1.to; //Creating E state by combining buff.to=buff1.from; //final to initial state. n[lc]=buff; //Entering state into nfae table. lc++; //Incrementing table counter. buff.from=state; buff.to=state+1; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.from=state; buff.to=buff2.from; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.from=buff1.to; buff.to=state+1; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.symbol='X'; buff.from=state; buff.to=state+1; state_push(buff);
//Initial state. //Final state. //Pushing initial & final state to the stack.
state=state+2; } else if(priority==7) //incase of ^#. { buff1=state_pop(); buff.symbol='E'; buff.from=buff1.to;//Creating E state by combining. buff.to=buff1.from;//Final to initial state. n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.from=state;
buff.to=buff1.from; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.from=buff1.to; buff.to=state+1; n[lc]=buff; //Entering state into nfae table. lc++; // Incrementing table counter. buff.symbol='X'; state_push(buff); state=state+2; }
//Pushing initial & final state to the stack.
}
} void print_nfae() { printf("\n\t--------------NFAe-----------------\n"); printf("\n\t| FROM\t|\t|\tSYMB |\n"); printf("\n\t-----------------------------------\n"); for(i=0;i<=lc;i++) printf("\n\t| %d\t|\t %d\t|\t %c |",n[i].from,n[i].to,n[i].symbol); printf("\n\n\t--------------------------------"); buff=state_pop(); initial=buff.from; final=buff.to; printf("\n\tstart state: %d and End state:%d",initial,final); } void print_dfa() { printf("\n\n\t-----------------DFA-------------\n"); printf("\n\t|from\t|\tTO\t|\tSYMB |\n"); printf("\n\t------------------------------------"); for(i=0;i
break; case 1: opr_push(re[i]); //push ( to operator stack. break; case 2: while(opr_pop()!='(') //pop until '(' found. opr_top--; check_operator(); //check whether opr_stack contain operator. break; case 3: opr_push(re[i]); //+ operator found push on to opr_stack. break; case 4: opr_push(re[i]); //. operator found push on to opr_stack. break; case 5: i++; // ^operator found take its next operator by incrementing i++. opr_push(re[i]); //Here operator will be it whether * or #. check_operator(); //check whether opr_stack contain operator. break; } } print_nfae(); construct_dfa(); print_dfa(); getch(); }
Related Documents
Re-dfa Very Small N Simplified
December 2019 11
Very Small Aperture Terminal
June 2020 2
Very Very Very New.docx
December 2019 47
Quantum Computers In A Very Small Nutshell
April 2020 6
Very Very Important
June 2020 87