rendered paste body/*
* Program to convert a regular expression to NFA *
* Author: *
Venkateswaran S<wenkat.s@gmail.com>
*
*
* Copyright 2004, 2005 VenkatSoft, Inc.
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public
* License along with this library; if not, write to the
* Free Software Foundation, Inc., 59 Temple Place - Suite 330,
* Boston, MA 02111-1307, USA.
*
*/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define ALPHABET 1
#define NON_ALPHABET 0
#define MAX 48
// Function Declaration
int createAutomata (struct automata **); // Just initializes default values of the struct Automata
int createNewState (struct state **); // The same as create Automata but this initializes struct state
struct automata * find_Nfa(); // Recursive Fn that finds the equivalent automata to the given regular expression
struct automata * applyStar (struct automata *);
// Note: The tranistions that are not named are epsilon transitions.
// ________
// | |
// converts (R)* to 3--> 1 --R--> 2 --> 4
// |___________________|
struct automata * applyOr (struct automata *,struct automata *);
// ____1 --R--> 2 ____
// | |
// converts R | S to 5 6
// |____3 --S--> 4_____|
struct automata * applyAnd (struct automata *, struct automata *);
// converts R . S to 1--R-->2 --> 3--S-->4
int ct = 1;
int flag = 0;
int last_char = NON_ALPHABET;
char cur_char='0';
struct state {
char *state_number;
struct state *transition1;
char v1;
struct state *transition2;
char v2;
};
struct automata {
struct state *start;
struct state *final;
};
int createNewState (struct state **ptr) {
struct state *tmp_st;
tmp_st =(struct state *) malloc(sizeof(struct state));
if(tmp_st != (struct state *)NULL) {
//tmp_st->state_number = (char *) malloc(MAX);
tmp_st->state_number = (char *)NULL;
tmp_st->transition1 = (struct state *)NULL;
tmp_st->v1='$';
tmp_st->transition2 = (struct state *)NULL;
tmp_st->v2='$';
*ptr = tmp_st;
return TRUE;
}
else {
printf("Unable to create a state");
return FALSE;
}
}
int createAutomata (struct automata **ptr) {
struct automata *tmp_automata;
tmp_automata = (struct automata *)malloc(sizeof(struct automata));
if(tmp_automata != (struct automata *)NULL) {
tmp_automata->start = (struct state *)NULL;
tmp_automata->final = (struct state *)NULL;
*ptr = tmp_automata;
return TRUE;
}
else {
printf("Unable to allocate memory for automata");
return FALSE;
}
}
struct automata * applyAnd (struct automata * nfa,struct automata * nfa1) {
if(nfa != (struct automata *)NULL && nfa1 != (struct automata *)NULL) {
printf("\n State : %s -- epsilon --> %s",nfa->final->state_number,nfa1->start->state_number);
nfa->final->transition1 = nfa1->start;
nfa->final = nfa1->final;
return (nfa);
}
else {
printf("\nUnable to Apply the 'and' operation on the nfa");
exit(1);
}
}
struct automata * applyOr (struct automata * nfa,struct automata * nfa1) {
if(nfa != (struct automata *)NULL && nfa1 != (struct automata *)NULL) {
struct state *tmp1 = (struct state *)NULL;
struct state *tmp2 = (struct state *)NULL;
if(createNewState(&tmp1) && createNewState(&tmp2)) {
tmp1->state_number = (char *) malloc(MAX);
itoa(ct++,tmp1->state_number,10);
tmp2->state_number = (char *) malloc(MAX);
itoa(ct++,tmp2->state_number,10);
tmp1->transition1 = nfa->start;
tmp1->v1 = '0';
tmp1->transition2 = nfa1->start;
tmp1->v2 = '0';
printf("\n State : %s -- epsilon --> %s",tmp1->state_number,tmp1->transition1->state_number);
printf("\n State : %s -- epsilon --> %s",tmp1->state_number,tmp1->transition2->state_number);
nfa->final->transition1 = tmp2;
nfa1->final->transition1 = tmp2;
printf("\n State : %s -- epsilon --> %s",nfa->final->state_number,nfa->final->transition1->state_number);
printf("\n State : %s -- epsilon --> %s",nfa1->final->state_number,nfa1->final->transition1->state_number);
nfa->start = tmp1;
nfa->final = tmp2;
return (nfa);
}
else {
printf("\nProbs in creating new states");
exit(1);
}
}
else {
printf("\nUnable to Apply the Or operation on the nfa");
exit(1);
}
}
struct automata * applyStar (struct automata * nfa) {
struct state *tmp1 = (struct state *)NULL;
struct state *tmp2 = (struct state *)NULL;
if(createNewState(&tmp1) && createNewState(&tmp2)) {
tmp1->state_number = (char *) malloc(MAX);
itoa(ct++,tmp1->state_number,10);
tmp1->transition1 = nfa->start;
tmp1->v1 = '0';
tmp1->transition2 = tmp2;
tmp1->v2 = '0';
tmp2->state_number = (char *) malloc(MAX);
itoa(ct++,tmp2->state_number,10);
nfa->final->transition1 = nfa->start;
nfa->final->v1 = '0';
nfa->final->transition2 = tmp2;
nfa->final->v2 = '0';
printf("\n State : %s -- epsilon --> %s",nfa->final->state_number,nfa->final->transition1->state_number);
printf("\n State : %s -- epsilon --> %s",nfa->final->state_number,nfa->final->transition2->state_number);
printf("\n State : %s -- epsilon --> %s",tmp1->state_number,nfa->start->state_number);
printf("\n State : %s -- epsilon --> %s",tmp1->state_number,tmp2->state_number);
nfa->start = tmp1;
nfa->final = tmp2;
return (nfa);
}
else {
printf("\nUnable to Apply the star operation on the nfa");
exit(1);
}
}
struct automata * find_Nfa() {
struct automata * nfa;
if(!createAutomata(&nfa)) {
printf("\nUnable to create automata called nfa");
exit(1);
}
while(cur_char != '$' || cur_char != '\n' || cur_char != '\r') {
if(flag == 0)
scanf("%c",&cur_char);
if( cur_char >= 'a' && cur_char <= 'z') {
if(last_char == ALPHABET) {
struct state *tmp1;
if(createNewState(&tmp1)) {
tmp1->state_number = (char *) malloc(MAX);
itoa(ct++,tmp1->state_number,10);
nfa->final->transition1 = tmp1;
nfa->final->v1 = cur_char;
printf("\n State : %s -- '%c' --> %s",nfa->final->state_number,nfa->final->v1,nfa->final->transition1->state_number);
nfa->final = tmp1;
}
}
else if (last_char == NON_ALPHABET) {
struct state *tmp1,*tmp2;
if(createNewState(&tmp1) && createNewState(&tmp2)) {
tmp1->state_number = (char *) malloc(MAX);
itoa(ct++,tmp1->state_number,10);
tmp2->state_number = (char *) malloc(16);
itoa(ct++,tmp2->state_number,10);
tmp1->transition1 = tmp2;
tmp1->v1=cur_char;
printf("\n State : %s -- '%c' --> %s",tmp1->state_number,tmp1->v1,tmp1->transition1->state_number);
nfa->start = tmp1;
nfa->final = tmp2;
}
last_char = ALPHABET;
}
else {
printf("Unable to create 2 new states");
exit(1);
}
}
else if ( cur_char == '(') {
last_char = NON_ALPHABET;
nfa = find_Nfa();
}
else if ( cur_char == ')' ) {
last_char = NON_ALPHABET;
return (nfa);
}
else if (cur_char == '*') {
last_char = NON_ALPHABET;
nfa = applyStar(nfa);
}
else if (cur_char == '|') {
last_char = NON_ALPHABET;
struct automata * temp2;
if(!createAutomata(&temp2)) {
printf("\nUnable to create automata called temp2");
exit(1);
}
temp2 = find_Nfa();
nfa = applyOr(nfa,temp2);
}
else if (cur_char == '.') {
last_char = NON_ALPHABET;
struct automata * temp3 = (struct automata *)NULL;
if(!createAutomata(&temp3)) {
printf("\nUnable to create automata called nfa");
exit(1);
}
temp3 = find_Nfa();
nfa = applyAnd(nfa,temp3);
}
else {
if(cur_char =='\n' || cur_char == '$' || cur_char == '\r') {
flag = 1;
return (nfa);
}
else {
printf("\nInvalid Input Character(s): %c\n",cur_char);
exit(1);
}
}
}
}
int main() {
struct automata * ans;
ans = find_Nfa();
printf("\n\n State : %s is the starting state",ans->start->state_number);
printf("\n State : %s is the Final State\n",ans->final->state_number);
return 0;
}