Problem 2 Recall the following definitions of deterministic and nondeterministic

Question

Problem 2 Recall the following definitions of deterministic and nondeterministic finite automata: Definition i (Deterministic Finite Automaton). A deterministic nite automaton is a 5-tuple, M (Q,E, F, q , ), where: Q is a finite set of states is the input alphabet ·FG Q is a set of final states ·q, E Q is the initial state ·8: Q × Q is the transition function Definition 2 (Nondeterministic Finite Automaton). A nondeterministic nite automaton is a 5-tuple, M- where: Q, , F, o , ), Q is a finite set of states · is the input alphabet ·FG Q is a set of final states ·q, E Q is the initial state ·8: Q × (Eu {A) ) 2Q s the transitionfunction

Explanation / Answer

Code # defining dfa class class DFA: """.......Class that encapsulates a DFA..........""" def __init__(self, transitionFunction, initialState, finalStates): self.delta = transitionFunction self.q0 = initialState self.F = finalStates def deltaHat(self, state, inputString): for a in inputString: state = self.delta[state][a] return state def inLanguage(self, inputString): return self.deltaHat(self.q0, inputString) in self.F #defining nfa class NFA: """............Class that encapsulates an NFA............""" def __init__(self, transitionFunction, initialState, finalStates): self.delta = transitionFunction self.q0 = initialState self.F = set(finalStates) def deltaHat(self, state, inputString): states = set([state]) for a in inputString: newStates = set([]) for state in states: try: newStates = newStates | self.delta[state][a] except KeyError: pass states = newStates return states def inLanguage(self, inputString): return len(self.deltaHat(self.q0, inputString) & self.F) > 0 def alphabet(self): Sigma = reduce(lambda a,b:set(a)|set(b), [x.keys() for x in N.delta.values()]) return Sigma def states(self): Q = set([self.q0]) | set(self.delta.keys()) | reduce(lambda a,b:a|b, reduce(lambda a,b:a+b, [x.values() for x in self.delta.values()])) return Q def convertNFAtoDFA(N): q0 = frozenset([N.q0]) Q = set([q0]) unprocessedQ = Q.copy() delta = {} F = [] Sigma = N.alphabet() while len(unprocessedQ) > 0: qSet = unprocessedQ.pop() delta[qSet] = {} for a in Sigma: nextStates = reduce(lambda x,y: x|y, [N.deltaHat(q,a) for q in qSet]) nextStates = frozenset(nextStates) delta[qSet][a] = nextStates if not nextStates in Q: Q.add(nextStates) unprocessedQ.add(nextStates) for qSet in Q: if len(qSet & N.F) > 0: F.append(qSet) M = DFA(delta, q0, F) return M delta = {'q0':{'0':set(['q0','q1']),'1':set(['q0'])}, 'q1':{'1':set(['q2'])}} N = NFA(delta, 'q0', ['q2']) N.deltaHat('q0', '0001') print [(x, N.inLanguage(x)) for x in ['0001', '00010', '100101']] M = convertNFAtoDFA(N) print [(x, M.inLanguage(x)) for x in ['0001', '00010', '100101']] if __name__ == "__main__": import doctest doctest.testmod()

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.