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 in Language(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 in Language(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 convertNFA to DFA(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 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.