Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

I'm working on an assignment for automata class Here's the example code in Python: def dfa_accept(M, w): Runs the DFA M = (Q, Sigma,

I'm working on an assignment for automata class

Here's the example code in Python:

def dfa_accept(M, w): """ Runs the DFA M = (Q, Sigma, delta, q0, F) on the string w. Returns True if all characters in w are in Sigma and the DFA accepts the word. Also checks if all states returned by delta are in Q. Returns False otherwise. """ (Q, Sigma, delta, q0, F) = M q = q0 if q not in Q: return False s = w while s != "": a = s[0] s = s[1:] if a not in Sigma: return False q = delta(q, a) if q not in Q: return False if q in F: return True return False def delta_odd(q, a): if q == 0: if a == '0': return 0 elif a == '1': return 1 else: return 2 elif q == 1: if a == '0': return 1 elif a == '1': return 0 else: return 2 else: return 2 print("Odd? ",dfa_accept(({ 0, 1 }, { '0', '1' }, delta_odd, 0, { 0 }), "0001010101011")) # True print("Odd? ",dfa_accept(({ 0, 1 }, { '0', '1' }, delta_odd, 0, { 0 }), "0001010101010")) # False 

This code satisfied the first problem in this assignment:

For this assignment, you must hand in valid code for the following problems:

1, A functional model for DFAs, as shown in the example above, in the form of a function taking a DFA and a string in argument and returning a boolean indicating whether the string is in the language of the DFA

Now I need to figure out the code for the second problem:

2. A function (or method) that takes a model of a Nondeterministic Finite Automaton (NFA) in argument and returns a valid DFA, which the function above is able to execute.

I'm stumped by this problem...I wonder if anyone can help me with it. Appreciate for all the help I can get!

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Advanced Database Systems

Authors: Carlo Zaniolo, Stefano Ceri, Christos Faloutsos, Richard T. Snodgrass, V.S. Subrahmanian, Roberto Zicari

1st Edition

155860443X, 978-1558604438

More Books

Students also viewed these Databases questions