[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