Computer Science Question

IMPORTANT NOTE BEFORE YOU ACCEPT THE BID: The project doesn’t take a long time at all, it is a straightforward fix but requires an advanced understanding of programming, especially Python, and a computer science degree.

if you are not sure you are qualified please don’t accept the bid as I will ask for a refund if the answer is wrong.

So please take a look at the file before you make a bid, as they are all attached.

What I want you to exactly is to change the test file I have in the folder attached to the original test file which is also attached In a separate file. The folder is named Comp370 P2 along with its code for the project. and the original test file is called test_pa2_original.py. My code works after I made these modifications on the test file not knowing that I cannot actually change the test file per the project requirements. You will notice some of the changes when you compare both test files. You can change the NFA or DFA class as much as you want, as long as the original test file outputs “All tests have passed”. I won’t accept the project if the test file doesn’t pass. I also attached the project instructions, you don’t need it, but just to give you an idea of whats the project about or if you needed hints on the algorithm.

COMP 370, Fall, 2023
Program #2, NFA to DFA conversion
Date Assigned: Thursday, September 21
Date Due: Thursday, October 5
For this assignment you will write a Python 3 program (in a file named nfa.py) that
defines a class named NFA. The constructor for this class reads an NFA specification
from a file. The class also has a method that converts the NFA to an equivalent DFA,
and returns the DFA as an object of the DFA class that you defined for pa1. Your
program should behave exactly as described further below.
1
Initial Setup
Both you and your partner will need to clone the starter code for your group using
git. The following assumes that you are using VSCode as your IDE. If you are using
some other IDE, follow the instructions for that IDE to clone a repository, or just use
command line git (“git clone url”).
1. You will need your group number in what follows. Get this from the “Programming partners and group numbers” file under the “Programming Assignments”
tab on Blackboard. This file also has your assigned partner.
2. In VS Code, open the command palette and select the “Git Clone” option.
3. When prompted for the repository URL, enter the following, with X replaced
by your group number (e.g. 7 or 12):
ssh://git@code.sandiego.edu/comp370-fa23-pa2-groupX
4. Choose the “Open Repository” option in the window that pops up in the lowerright corner of the screen. The repository should contain the following files:
• nfa.py: You will write your code in this file. It includes the header for
the NFA class that you will write, and the headers for the constructor and
to_dfa methods that you must add.
• test_pa2.py: This program will test your nfa.py program. See the discussion below on this.
• nfai.txt for i = 1, …, : Test nfa files.
• stri.txt for i = 1, … : Test input strings for the corresponding nfa’s.
• correcti.txt for i = 1, … : Correct answer for the test input strings for
the corresponding nfa’s
1
5. Each programming team will have it own repository that has been initialized
with the same starter code, so when you sync your code, you are sharing with
your partners, but with no one else in the class. (I can see your repository also.)
6. Once you have cloned your repository, you should copy your (correct) pa1 code
(dfa.py) into your repository, and add it to the repository. (See the instructions
for pa0 for a reminder of how to add a new file to a repository.) The program
test_pa2.py imports dfa.py to test your nfa.py code. You will have to make
a couple changes to your dfa.py file. Instructions on this further down.
7. Remember that if you close VSCode, then when you reopen it, you should see
your repository. But if you don’t see it, then just select File->Open, and then
select the directory containing your repository.
8. I also recommend that you stage changes, commit those changes, and sync the
changes periodically as you are working on the program, and certainly when
you are done with a session with your programming partner. This ensures that
you won’t lose any of your work in case your computer gets lost or a file gets
accidentally deleted. The message for each commit should describe the changes
made in the code since the last commit.
2
Program Specifications
As said above, your program should be contained in a file named nfa.py. In this file
you should define a class called NFA (all capital letters). NFA should have a constructor
that takes as its parameter the name of a file, and initializes the NFA from the contents
of the file. (Specifications for the file format are further down.) NFA should also have
a method named to_DFA that has no parameters, and returns a DFA object (an object
of the DFA class you defined for pa1) that is equivalent to the NFA that calls the
method (the “self” NFA). By equivalent, I mean that the DFA and the NFA should
accept exactly the same set of strings.
Remember (from the syllabus) – no importing of Python modules or any outside
modules. The point of this is to ensure that you’re doing the work of the assignment
on your own with your own code. If there is some class or function from a module
that you would like to use that you feel doesn’t take away from your coding the main
thrust of the assignment, post a note to me on campuswire and I’ll get back to you.
Your DFA class (and so the DFA object that is returned by to_DFA) must meet
several requirements. See the section below titled “DFA requirements.” for the full set
of requirements, but the most important one is that the states of your DFA must be
identified by the integers 1, 2, 3, …, up to the number of states. So, for example, if
your DFA has 5 states, they must be identified by the integers 1, 2, 3, 4, and 5.
Your to_DFA method must follow the algorithm described in class and in the
textbook. See the section below titled “Algorithm requirements” for details.
The project repository contains a nfa.py file that has the headers for the NFA
constructor and the to_DFA method.
2
The format of the NFA description is as follows (this is close to the same as the
DFA specification in the first programming assignment, except that there can be
nondeterminism, epsilon transitions, and a transition does not have to be specified
for all state/symbol combinations):
1. An integer that is the number of states in the NFA. This appears by itself on
the first line of input. (In the remainder of the description, each state must
be referred to by an integer in the range [1, 2, …, n], where n is the number of
states.)
2. The alphabet of the NFA. This appears by itself on the second line of input.
Every character in the line (not including the terminating newline character) is
a symbol of the alphabet. The alphabet cannot include the letter e, as this is
reserved for specifying epsilon transitions.
3. The transition function of the NFA. There will be one line of input per possible
transition in the transition function, starting with the third line of input. The
format of an entry is
qa ’c’ qb
This entry indicates that if the NFA is in state qb and the next symbol scanned
is a c, then the NFA can transition to qb. c can also be the letter e, in which
case is represents an epsilon transition.
qa and qb must be valid states; that is, qa ∈ {1, 2, . . . , n} and qb ∈ {1, 2, . . . , n}.
c must be in the alphabet or be the letter e (representing epsilon), and the single
quotes must be present (even for the letter e).
The entries of the transition function can appear in any order.
4. A blank line terminates the transition function entries. We need this because
we don’t know in advance how many transition function entries there will be.
5. An integer that is the start state of the NFA. This appears by itself on the first
line after the transition function lines.
6. The set of accept states of the NFA. These appear together on the line following
the line containing the start state.
Entries on a line are separated by one or more space characters. The first entry
on a line is preceded by 0 or more space characters, and the last entry on a line is
followed by 0 or more space characters (in addition to the newline character).
Your program can assume that the input file will be correctly formatted, with no
inconsistent data. (For example, if there are only 6 states in the NFA, there will be
no transition function entries that specify a state of greater than 6 or less than 1.)
3
3
DFA requirements
First, you need to make a quick edit to the DFA class in dfa.py: (Just in the pa2 folder.
You don’t have to go back and edit it in the pa1 folder). In the DFA constructor, add a
default value of None to the filename parameter. This will allow the DFA constructor
to create an “empty” DFA object (one without any defined instance variables) that
initialized by the NFA to_DFA method. So, to_DFA will create a DFA object (that is
empty), and then initialize its instance variables itself.
As said earlier, your DFA must identify its states by the integers 1, 2, 3, …, up
to the number of states. So, for example, if your DFA has 5 states, they must be
identified by the integers 1, 2, 3, 4, and 5. Recall that the to_nfa method will identify
states with subset of the NFA states, but you will need to map those subsets to the
integers 1, 2, …
Your DFA class will have to define a number of attributes associated with the DFA.
I’ll start with an example: suppose that the test_pa2 code defines an NFA object,
creates an equivalent DFA using the to_dfa method, and then prints the number of
states in the DFA:
n = NFA(“nfa1.txt”)
d = n.to_dfa()
print(d.num_states)
This seems to suggest that your DFA class has to have an instance variable named
num_states, but this is not the case. If you do happen to have a num_states instance
variable, then your good and you do not need to do anything more so support the
above code. But let’s suppose you called an instance variable number_states, or
maybe you don’t have an instance variable that stores the number of states – maybe
you have some list instance variable whose length is the number of states. As said
above, you do not have to go back and modify everything in your DFA class so that it
has a num_states instance variable. As an alternative, you might be thinking that
you could create a getter method that returns the number of states:
n = NFA(“nfa1.txt”)
d = n.to_dfa()
print(d.get_num_states())
This works, and it would be what you would do in say Java. But it is not the
Pythonic way of doing this. You will use Python property capability. There is quite a
bit to say about Python properties – the discussion at https://realpython.com/python-property/
I think is pretty good. The short version is: suppose your DFA class has an instance
variable named number_states, and you have to have an attribute num_states. Then
add the following to your DFA class:
@property
def num_states(self):
“”” Number of states property “””
return self.number_states
4
This looks like it is defining a method named num_states, but the @property
decorator turns it into a property, which can be accessed as if it were an instance
variable:
d.num_states
This is convenient. It allows your code to support a new attribute without you
having to reimplement your class.
The attributes your DFA class must support are:
• num_states: the integer number of states of your DFA
• alphabet: the list of symbols in the DFA. Represented as a Python list.
• start_state: the integer specifying the start state of the DFA. Must be in the
range 1, …, num_states
• accept_states: the set of accept states in the DFA. Represented as a Python
set. Each entry must be in the range 1, …, num_states
For each of these, if your DFA class already has an instance variable with the same
name that represents the data in the required manner, then do nothing. But if not,
follow the above example (for num_states) to create the required property.
You must also add a method named transition to your DFA class. Here is the
header:
def transition(self, state, symbol):
“””
Returns the state to transition to from “state” on in input symbol “symbol”.
state must be in the range 1, …, num_states
symbol must be in the alphabet
the returned state must be in the range 1, …, num_states
“””
4
Algorithm Requirements
Your program must implement the algorithm illustrated by examples in class (from
Lecture 7, Problem 1.13, and additional exercise, and the Charlie and Lucy Problem),
the example in Virtual Lecture 10, and in the proof to Theorem 1.39 in the textbook.
However, in Theorem 1.39, all possible states of the DFA are created (each associated
with a subset of states of the NFA). Do not do this – as in the examples from class
and the virtual lecture, you will generate the states of the DFA “on demand.” That
is, you’ll create the start state of the DFA from the epsilon closure of the start state of
the NFA, and then follow transitions from that state on all possible alphabet symbols
to possibly new states (but to possibly states you’ve already defined). Eventually you
will define all DFA states reachable from the start state, and you’ll be done, after
having defined hopefully many fewer states than the maximum possible.
5
You must make sure your algorithm implementation handles epsilon transitions.
Suppose that you have a subset of NFA states that defines a DFA state. You want to
expand this subset of states to include all states reachable by following one or more
epsilon transitions from any state in this subset. The resulting subset of NFA states
is called the epsilon closure of the original subset of states. So every time you create
a new state of the DFA (as defined by a subset of NFA states), you expand the subset
to be the epsilon closure of the subset. This is illustrated in the additional exercise in
Lecture 7, and is discussed at the end of the proof to Theorem 1.39 in the textbook.
I suggest that you create a helper method that takes a subset of states (of the NFA),
and returns the epsilon closure of this subset.
5
Working on the Program
You should work with your programming partner, using the pair programming software development technique.
As said above, the project repository contains test data for you. For each test
NFA there is the NFA specification file (e.g. nfa1.txt), a file containing test strings
(e.g. str1.txt), one string per line, and a file containing the correct answers for each
test string (e.g., correct1.txt), one answer (Accept or Reject) per line. (The lines
of correct1.txt correspond to the lines of str1.txt.)
The project repository contains a Python program called test_pa2.py that tests
your NFA class on all of the test NFAs in the files described above, and it reports
the results. Your program must pass all tests before you submit your program for
grading. If it fails any test, I’ll return the program to you for further work.
As I said above, you should have added your solution code to pa1 (dfa.py) to
your repository and modified it as described above, as test_pa2.py imports that file,
and uses it to test your code.
Be sure that your code satisfies the requirements specified above for your algorithm
implementation. If I see in your code that you have not done this, I will send it back
to you for correction.
Your program should follow the programming style guidelines contained in the programmingStyleGuidelines.txt document on blackboard->Programming Assignments.
Failure to follow these guidelines will result in me sending your code back to you for
further work.
To submit your program for review, be sure that you’ve pushed it the repository,
and post a note on campuswire, category pa2_submit, giving just your group number.
(Questions about pa2 should go to category PA2.)
6
Recommended Approach
I recommend you approach the problem by following the following steps:
1. First, understand the NFA to DFA conversion algorithm. Review the algorithm
as illustrated in Lecture 7 (Problem 1.13 and the Charlie and Lucy problem),
6
and Virtual Lecture 10. You should also review Theorem 1.39 in the textbook,
starting on page 55, and the example of the construction described in the Theorem, in Example 1.41, starting at the bottom of page 56. But remember, the
textbook examples generate also possible subsets of the states of the NFA, and
as noted above in the section on algorithm requirements, you should not do
that. Note that your program needs to account for epsilon transitions in an
NFA. The end of Theorem 1.39 describes how to handle these, and Example
1.41 also handles these.
2. On paper, trace the algorithm for at least one sample NFA in the repository,
making sure you have at least one example that has epsilon transitions. If you
come to office hours for help on this project, I’m going to ask to see the examples
you traced. (If you cannot trace the algorithm on paper, then it will be hard
for you to code it up.)
3. Familiarize yourself (if you haven’t already) with the debugger in your IDE, particularly the features that allow you to set breakpoints and examine the values
of data (variable, instance variables, parameters) as the program is executing.
4. Start coding by writing the NFA class constructor, which should create an internal representation of the NFA it is reading from the file. You internal representation of an NFA will likely be similar to the internal representation of a
DFA from your pa1 program. Once written, run your debugger on the program,
reading in from a couple of the test NFA files. Examine the values of the variables, to make sure that they correctly represent the NFAs. If you don’t have a
correct internal representation of the NFA, you’re not going to be able to write
out a correct DFA.
5. Next, convert the internal representation of the NFA into an internal representation of an equivalent DFA. Remember to adhere to the requirements in the
above section on DFA requirements.
6. Again, use the debugger to validate (for at least a couple test NFAs) the internal
representation of your DFAs, debugging your code as necessary.
7. Complete your testing by running test_pa2.py and making sure it reports all
tests are correct. No credit unless you get all tests correct. As you are testing
and debugging, you can edit test_pa2.py to execute only certain test inputs.
7