This project explores the implementation of finite slate machines and has two pa

Question

This project explores the implementation of finite slate machines and has two parts. Write a program that starts by asking the user to describe a finite state automaton. You then display a regular expression describing the strings accepted by this FSA. Write a program that takes a regular expression as an input and describes the FSA associated with the expression. For both parts, allow the user to enter a bit string and have your program determine whether it is accepted or rejected by their FSA or regular expression.

Explanation / Answer

Code to convert Regular expression to Finite Automata

#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
       struct current{int first,last;}stat[15];
       int l,j,change,n=0,i=0;
       int state=1,x,y,initial,end;
       char save,*ip1,ip[15];
clrscr();
                      printf("    INPUT REGULAR EXPRESSION n ");
scanf("%s",ip1);                                                                /*Example Inputs : 1. ab*c 2. ab+c " Getting regular

                                                                                         expression as input*/
for(i=0;i<10;i++)
ip[i]=NULL;
l=strlen(ip1);
a:
for(i=0;ip1[i]!=')';i++);
for(j=i;ip1[j]!='(';j--);
for(x=j+1;x<i;x++)
if(isalpha(ip1[x]))
ip[n++]=ip1[x];
else if(ip1[x]!='0')
save=ip1[x];
ip[n++]=save;
for(x=j;x<=i;x++)
ip1[x]='0';
if(ip1[0]!='0')
goto a;

printf(" From To Input ");
i=0;
while(ip[i]!='')
{
if(isalpha(ip[i]))
{
stat[i].first=state++;
stat[i].last=state++;
                       printf(" %d %d %c",stat[i].first,stat[i].last,ip[i]);   /*printing regular expression*/
}
else
{
change=0;
switch(ip[i])
{
case'|':
stat[i].first=state++;
stat[i].last=state++;
x=i-2;
y=i-1;
if(!isalpha(ip[y]))
{
b:
switch(ip[y])
{
case'*':if(!isalpha(ip[y-1]))
{
y=y-1;
goto b;
}
else
x=y-2;
break;
case'|':x=y-3;
break;
case '.':x=y-3;break;
}
change=1;
}
if(!isalpha(ip[y]&&change==0))
c:switch(ip[x])
{
case '*':
if(!isalpha(ip[x-1]))
{x=x-1;goto c;
}
else x=x-2;
break;
case'|':x=x-2;
break;
case '.':x=x-3;
break;
}
                                                printf(" %d %d E",stat[i].first,stat[x].first);
                                                printf(" %d %d E",stat[x].last,stat[i].last);
                                                printf(" %d %d E",stat[i].first,stat[i-1].first);
                                                printf(" %d %d E",stat[i-1].last,stat[i].last);

                                       /* listing from and to in expression*/
initial=stat[i].first;
end=stat[i].last;
break;
case'.':
x=i-2;
y=i-1;
if(!isalpha(ip[y]))
       {
                  d:
                  switch(ip[y])
      {
case'*':if(!isalpha(i[y-1]))
     {
                  y=y-1;
                goto d;
}
else
x=y-2;
break;
case'|':x=y-3;
break;
case '.':x=y-3;
break;
}
change=1;
}
if(!isalpha(ip[y]&&change==0))
e:switch(ip[x])
{
case'*':
if(!isalpha(ip[x-1]))
{
x=x-1;
goto e;
}
else x=x-2;
break;
case'|':x=x-3;
break;
case'.':x=x-3;
break;
}
stat[i].last=stat[y].last;
stat[i].first=stat[x].first;
printf(" %d %d E",stat[x].last,stat[i-1].first);
initial =stat[x].first;
end =stat[i-1].last;
break;
case'*':
stat[i].first=state++;
stat[i].last=state++;
                     printf(" %d %d E",stat[i].first,stat[i-1].first);
                     printf(" %d %d E",stat[i].first,stat[i].last);
                     printf(" %d %d E",stat[i-1].last,stat[i-1].first);
                     printf(" %d %d E",stat[i-1].last,stat[i].last);
initial=stat[i].first;
end=stat[i].last;
break;
}}
i++;
}
printf(" the initial expression was %d",initial);
printf(" at the end %d",end);
getch();
}

Kindly save the code and compile it for error check. Provide the regular expression as input to get the initial and final state of the design easily. Any queries comment below.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.