DFA implementation in python

What you have to do:

First of all, create a DFA for the required string pattern

For example, if we consider the expression 01(1 + 0)* + (1 + 0)*01, the DFA will be:

To create a program for this DFA we need to create nine states q0, q1, q2, q3, q4, q5, q6, q7, q8. And specify all the inputs and outputs for them.

a normal state will be like this

In C Language:

#include<stdio.h>
#include<string.h>

int q0(char str[], int i)
{
if(i > strlen(str)-1)
{
return(0) ;
}
else
{
if(str[i] == '0')
{
return q2(str, i+1);
}
else
{
if(str[i] == '1')
{
return q1(str, i+1);
}
else
{
return(0);
}
}
}
}
int q1(char str[], int i)
{
if(i > strlen(str)-1)
{
return(0);
}
else
{
if(str[i] == '0')
{
return q3(str, i+1);
}
else
{
if(str[i] == '1')
{
return q1(str, i+1);
}
else
{
return(0);
}
}
}
}
int q2(char str[], int i)
{
if(i > strlen(str)-1)
{
return(0);
}
else
{
if(str[i] == '0')
{
return q3(str, i+1);
}
else
{
if(str[i] == '1')
{
return q4(str, i+1);
}
else
{
return(0);
}
}
}
}
int q3(char str[], int i)
{
if(i > strlen(str)-1)
{
return(0);
}
else
{
if(str[i] == '0')
{
return q3(str, i+1);
}
else
{
if(str[i] == '1')
{
return q5(str, i+1);
}
else
{
return(0);
}
}
}
}
int q4(char str[], int i)
{
if(i > strlen(str)-1)
{
return(1);
}
else
{
if(str[i] == '0')
{
return q7(str, i+1);
}
else
{
if(str[i] == '1')
{
return q6(str, i+1);
}
else
{
return(0);
}
}
}
}
int q5(char str[], int i)
{
if(i > strlen(str)-1)
{
return(1);
}
else
{
if(str[i] == '0')
{
return q3(str, i+1);
}
else
{
if(str[i] == '1')
{
return q1(str, i+1);
}
else
{
return(0);
}
}
}
}
int q6(char str[], int i)
{
if(i > strlen(str)-1)
{
return(1);
}
else
{
if(str[i] == '0')
{
return q7(str, i+1);
}
else
{
if(str[i] == '1')
{
return q6(str, i+1);
}
else
{
return(0);
}
}
}
}
int q7(char str[], int i)
{
if(i > strlen(str)-1)
{
return(1);
}
else
{
if(str[i] == '0')
{
return q7(str, i+1);
}
else
{
if(str[i] == '1')
{
return q8(str, i+1);
}
else
{
return(0);
}
}
}
}
int q8(char str[], int i)
{
if(i > strlen(str)-1)
{
return(1);
}
else
{
if(str[i] == '0')
{
return q7(str, i+1);
}
else
{
if(str[i] == '1')
{
return q6(str, i+1);
}
else
{
return(0);
}
}
}
}
void main()
{
char str[20];
printf("Enter a string\n");
scanf("%[^\n]", &str);
printf("%s", str);
if(q0(str, 0) == 1)
{
printf("\nTrue");
}
else
{
printf("\nFalse");
}

}

Try It by Running it:

In python Language:

def q0(arr, i):
if i > len(arr)-1:
return False
else:
if arr[i] == '0':
return q2(arr, i+1)

elif arr[i] == '1':
return q1(arr, i+1)

def q1(arr, i):
if i > len(arr)-1:
return False
else:
if arr[i] == '1':
return q1(arr, i+1)

elif arr[i] == '0':
return q3(arr, i+1)

def q2(arr, i):
if i > len(arr)-1:
return False
else:
if arr[i] == '0':
return q3(arr, i+1)

elif arr[i] == '1':
return q4(arr, i+1)

def q3(arr, i):
if i > len(arr)-1:
return False
else:
if arr[i] == '0':
return q3(arr, i+1)

elif arr[i] == '1':
return q5(arr, i+1)


def q4(arr, i):
if i > len(arr)-1:
return True
else:
if arr[i] == '0':
return q7(arr, i+1)

elif arr[i] == '1':
return q6(arr, i+1)


def q5(arr, i):
if i > len(arr)-1:
return True
else:
if arr[i] == '0':
return q3(arr, i+1)

elif arr[i] == '1':
return q1(arr, i+1)

def q6(arr, i):
if i > len(arr)-1:
return True
else:
if arr[i] == '1':
return q6(arr, i+1)

elif arr[i] == '0':
return q7(arr, i+1)


def q7(arr, i):
if i > len(arr)-1:
return True
else:
if arr[i] == '0':
return q7(arr, i+1)

elif arr[i] == '1':
return q8(arr, i+1)

def q8(arr, i):
if i > len(arr)-1:
return True
else:
if arr[i] == '0':
return q7(arr, i+1)

elif arr[i] == '1':
return q6(arr, i+1)

if __name__ == '__main__':
take = input("enter the string : ")

print(q0(take, 0))

Try it bu running it:

Hope you've learned something
If any thing is wrong please tell me in comment section

Pointotech

Search This Blog