[Tutor] Theory of computation non-emptiness
tracey jones-Francis
drtraceyjones at hotmail.com
Sat Apr 21 07:50:24 EDT 2018
Hi there, I've been working on code that takes a text file that represents a specific Deterministic Finite Automata.
The text files are set up in a specific way so that line 1 specifies the number of states. Line 2 specifies the states (i.e., just a list of the names of the states, separated by spaces). Line 3 specifies the size of the alphabet. Line 4 specifies the alphabet. Lines 5-7 give the transition function, each row corresponding to a state (in order specified on line 2) and each column corresponding to a symbol from the alphabet (in order specified on line 4). Line 8 specifies the start state. Line 9 specifies the number of final/accept states. Line 10 specifies the final states.
I have already constructed some functions but next I want to construct a function determining, for any DFA M, whether or not L(M) = 0 i.e., whether or not there exists at least one string that is accepted by M. if the language If L(M) = 0 then I want “language empty” printed. If L(M) != 0; then i need to print “language non-empty - xxxx accepted”, where xxxx is replaced by some string that is accepted by M.
I wanted to use breath first search in order to determine the existence of a path. Code below is all I've done so far but i'm struggling to find a way in which to link the states with the transitions in the text file.
hope you can give me some direction and advice.
def NonEmptiness(dic):
dic = openTextFile(dic)
#print(dic['states'].split())
theString = ""
visited = []
queue = dic['states'].split()
newStates = dic['states']
newStatesFinal = re.sub(' ','', newStates)
newAplhabet = re.sub(' ','', dic['alphabet'])
#print(dic['finalStates'][2])
print(newStatesFinal)
#print(newStatesFinal[0])
while queue:
currentState = queue.pop(0)
visited.append(currentState)
#print(visited)
for a in newAplhabet:
if (currentState, a) == (newStatesFinal[0], newAplhabet[0]):
if dic['transitionStates'][0][0] != dic['finalStates'][0] or dic['finalStates'][2]:
theString + a
else:
More information about the Tutor
mailing list