C program for converting regular expression to NFA

C program to convert regular expression to NFA:

To convert the regular expression to NFA, this method is known as the Subset method.

The steps in this method are given below:-

Step-1: Make a transition diagram for a given regular expression, using NFA with ε moves.

Step-2: Then, Convert this NFA with ε to NFA without ε.

Step-3: Finally, Convert the obtained NFA to an equivalent DFA.

#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
int r[100];
static int pos = 0;
static int sc = 0;
void nfa(int st, int p, char*s)
{
 int i,sp,fs[15],fsc=0;
 sp=st:pos=p;sc=st;
while(*s!=NULL)
{
if(isalpha(*s))
{
 r[pos++]=sp;
 r[pos++]=*s;
 r[pos++]=++sc;}
if(*s=='.')
{ 
 sp=sc;
 r[pos++]=sc;
 r[pos++]=238;
 r[pos++]=++sc;
 sp=sc;
}
 if(*s=='|')
{
 sp=st;
 fs[fsc++]=sc;
}
 if(*s=='*')
{
 r[pos++]=sc;
 r[pos++]=238;
 r[pos++]=sp;
 r[pos++]=sp;
 r[pos++]=238;
 r[pos++]=sc;
}
 if(*s=='(')
{
  char ps[50];
  int i=0,flag=1;
  s++;
while(flag!=0)
{
  ps[i++]=*s;
  if(*s=='(')
  flag++;
 if(*s==')')
  flag--;
  s++;
}
 ps[--i]='
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
int r[100];
static int pos = 0;
static int sc = 0;
void nfa(int st, int p, char*s)
{
int i,sp,fs[15],fsc=0;
sp=st:pos=p;sc=st;
while(*s!=NULL)
{
if(isalpha(*s))
{
r[pos++]=sp;
r[pos++]=*s;
r[pos++]=++sc;}
if(*s=='.')
{ 
sp=sc;
r[pos++]=sc;
r[pos++]=238;
r[pos++]=++sc;
sp=sc;
}
if(*s=='|')
{
sp=st;
fs[fsc++]=sc;
}
if(*s=='*')
{
r[pos++]=sc;
r[pos++]=238;
r[pos++]=sp;
r[pos++]=sp;
r[pos++]=238;
r[pos++]=sc;
}
if(*s=='(')
{
char ps[50];
int i=0,flag=1;
s++;
while(flag!=0)
{
ps[i++]=*s;
if(*s=='(')
flag++;
if(*s==')')
flag--;
s++;
}
ps[--i]='\0';
nfa(sc,pos,ps);
s--;
}
s++;
}
sc++;
for(i=0;i<fsc;i++)
{
r[pos++]=fs[i];
r[pos++]=238;
r[pos++]=sc;
}
r[pos++]=sc-1;
r[pos++]=238;
r[pos++]=sc;
}
void main()
{
int i;
char *inp;
clrscr();
printf("enter the regular expression :");
gets(inp);
nfa(1,0,inp);
printf("\nstate input state\n");
for(i=0;i<pos;i=i+3)
print("%d  --%c--> %d\n", r[i], r[i+1], r[i+2]);
printf("\n");
getch();
}
'; nfa(sc,pos,ps); s--; } s++; } sc++; for(i=0;i<fsc;i++) { r[pos++]=fs[i]; r[pos++]=238; r[pos++]=sc; } r[pos++]=sc-1; r[pos++]=238; r[pos++]=sc; } void main() { int i; char *inp; clrscr(); printf("enter the regular expression :"); gets(inp); nfa(1,0,inp); printf("\nstate input state\n"); for(i=0;i<pos;i=i+3) print("%d --%c--> %d\n", r[i], r[i+1], r[i+2]); printf("\n"); getch(); }

Leave a Reply

Your email address will not be published. Required fields are marked *