Converting dfa/ Regular Expression to c Program step wise explanation | deterministic finite automata | Example 1
Given : Regular Expression (01* +10*) 11
Step 1
Langugage L = { 011,111,0111111111,10000011,1011 }
Minimum strings = { 011,111}
Few examples of invalid strings ={ 000,11100,01010}
Step 2
Draw Dfa of given regular expression
or draw Nfa of given regular expression and convert it to Dfa
Dfa of (01* + 10*)11
dead states = State 8 and 9
initial state = State 1
Final State = state 4 and 7
Step 3
construct transition table of Dfa
Step 4
C program implementation
#include <stdio.h>
#include <string.h>
#include<conio.h>
int main()
{
char s[20];
int l, State, c;
char Temp;
printf("\n enter string to check: \n");
gets(s);
l=strlen(s); //length of the string
printf("String length is %d \n", l);
c=0;
printf("count is %d \n", c);
State=1; // initial state
printf("State is %d \n", State);
while(c<l)
{
Temp=s[c];
switch(State)
{
case 1:
if(Temp=='0')
State=2;
if(Temp=='1')
State=5;
break;
case 2:
if(Temp=='0')
State=8;
if(Temp=='1')
State=3;
break;
case 3:
if(Temp=='0')
State=8;
if(Temp=='1')
State=4;
break;
case 4:
if(Temp=='0')
State=8;
if(Temp=='1')
State=4;
break;
case 5:
if(Temp=='0')
State=5;
if(Temp=='1')
State=6;
break;
case 6:
if(Temp=='0')
State=9;
if(Temp=='1')
State=7;
break;
case 7:
if(Temp=='0')
State=9;
if(Temp=='1')
State=9;
break;
case 8:
if(Temp=='0')
State=8;
if(Temp=='1')
State=8;
break;
case 9:
if(Temp=='0')
State=9;
if(Temp=='1')
State=9;
break;
}
c++;
}
if((State==4) || (State==7))
printf("Valid string \n");
else
printf("InValid string \n");
getch();
return 0;
}
Step 5
output
