Skip to content

Instantly share code, notes, and snippets.

@AryanGitHub
Created June 5, 2023 10:32
Show Gist options
  • Save AryanGitHub/0bd6aefbd5bd3fbfff33d50d292474fd to your computer and use it in GitHub Desktop.
Save AryanGitHub/0bd6aefbd5bd3fbfff33d50d292474fd to your computer and use it in GitHub Desktop.
DFA using python3
# https://en.wikipedia.org/wiki/Deterministic_finite_automaton
class DFA: #Deterministic Finite Automaton
def __init__ (self ,states : set , alphabets : set, transition_function , initial , accepted_states : set):
self.states = states
self.alphabets = alphabets
if (self.__checkTransitionFunction__(transition_function)):
self.transitionFunction = transition_function
else :
print ("Error: The Transition function has some errors")
if (self.__checkInitialState__(initial)):
self.initialState = initial
else :
print ("Error: The initial states in not in all valid states. Here states =", self.states)
if (self.__checkAcceptedStates__(accepted_states)):
self.acceptedStates = accepted_states
else:
print("Error: The accepted states are not in all valid states. Here states are =" , self.states)
def __checkInitialState__ (self , initalState):
return initalState in self.states
def __checkAcceptedStates__ (self , accepted_states):
return accepted_states.issubset(self.states)
def __checkTransitionFunction__(self, transition_function):
def checkKey(key):
return len(key)==2 and key[0] in self.states and key[1] in self.alphabets
if (set (transition_function.values()).issubset(self.states)):
for key in transition_function :
if not checkKey(key):
return False
else:
return True
def getFinalState (self , inputData):
currentState = self.initialState
for input in inputData:
if (input not in self.alphabets):
print ("Input is not from the Alphabets")
break
currentState = self.transitionFunction.get((currentState, input) , None)
if currentState == None:
print("Error: The Transition Function do not have state for currentState: ", currentState , "input: ", input )
return currentState
def isAccepted (self , input):
return self.getFinalState(input) in self.acceptedStates
import DFA as dfa
def evenOnes (inputStr : str):
states = {"A" , "B" }
alphabets = { "1" }
tf = { ("A" , "1" ) : "B",
("B" , "1" ) : "A"
}
initial = "A"
accepted_state = {"A"}
testing = dfa.DFA(states=states , alphabets=alphabets , transition_function= tf , initial=initial , accepted_states=accepted_state)
return (testing.isAccepted(inputStr))
def contains110 (inputStr : str):
states = {"A" , "B" , "C" , "D"}
alphabets = { "0" , "1" }
tf = { ("A", "0"): "A",
("A", "1"): "B",
("B", "0"): "A",
("B", "1"): "C",
("C", "0"): "D",
("C", "1"): "A",
("D", "1"): "D",
("D", "0"): "D"
}
initial = "A"
accepted_state = {"D"}
testing = dfa.DFA(states=states , alphabets=alphabets , transition_function= tf , initial=initial , accepted_states=accepted_state)
return (testing.isAccepted(inputStr))
if(__name__ == "__main__"):
print(evenOnes("111"))
print(contains110("00010101001100000000000100001000"))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment