Written solutions to problems 2.3.7, 2.4.4, and one of the following three problems: 2.4.2, 2.4.5, 2.4.12 are due at the beginning of class Thursday Feb 11. Implement the algorithm described on pages 105-109 that checks if a string is accepted by generic NFA in the programming language of your choice. For the lab portion of the assignment, you may work with a partner.

Your code should accept two files as input. The first file is a description of the machine. The sample format for this file is shown below

qe 0
q0 0
q1 0
q2 0
q3 0
qf 1

qe E q0
q0 a q0
q0 b q0
q0 a q1
q0 b q2
q1 b qf
q2 b q3
q3 b qf
qf a qf
qf b qf

Each non empty line has either two or three strings separated by spaces. The lines with two strings represent states. The first string is the state name. The second string is either 0 or 1. A state is a final state if the second string is one. The first state listed is the start state (e.g., qe)

The lines with three strings represent the transition function. q0 a q0 is interpreted as "if the machine is in state q0 and reads an a, the machine may transition to state q0

You may assume that all states are listed before all transitions.

Use a E to idicate epsilon transitions, e.g., qe E q0

The second file is just a list of string that are inputs to the machine. See the example below.

ab
aabb
abb
baa
aaabbb
aabb
ababb
a
bb
aa
bbb

Your code should test each input string against the machine and label each string as accepted or not accepted.

Additionally, create a machine of your own and some test code to verify your program is correct.

$ python nfa_sol.py machine1.txt input1.txt 
ab: False
aabb: False
abb: True
baa: False
aaabbb: False
aabb: False
ababb: False
a: True
bb: False
aa: False
bbb: False

The solution below shows the intermediate state prior to reading the next symbol

$ python nfa_sol.py machine2.txt input1.txt 
['q0'] a
['q1', 'q0'] b
['q0', 'q2', 'qf'] no more input
ab: True
['q0'] a
['q1', 'q0'] a
['q1', 'q0'] b
['q0', 'q2', 'qf'] b
['q0', 'q3', 'q2', 'qf'] no more input
aabb: True
['q0'] a
['q1', 'q0'] b
['q0', 'q2', 'qf'] b
['q0', 'q3', 'q2', 'qf'] no more input
abb: True
['q0'] b
['q0', 'q2'] a
['q1', 'q0'] a
['q1', 'q0'] no more input
baa: False
['q0'] a
['q1', 'q0'] a
['q1', 'q0'] a
['q1', 'q0'] b
['q0', 'q2', 'qf'] b
['q0', 'q3', 'q2', 'qf'] b
['q0', 'q3', 'q2', 'qf'] no more input
aaabbb: True
['q0'] a
['q1', 'q0'] a
['q1', 'q0'] b
['q0', 'q2', 'qf'] b
['q0', 'q3', 'q2', 'qf'] no more input
aabb: True
['q0'] a
['q1', 'q0'] b
['q0', 'q2', 'qf'] a
['q1', 'q0', 'qf'] b
['q0', 'q2', 'qf'] b
['q0', 'q3', 'q2', 'qf'] no more input
ababb: True
['q0'] a
['q1', 'q0'] no more input
a: False
['q0'] b
['q0', 'q2'] b
['q0', 'q3', 'q2'] no more input
bb: False
['q0'] a
['q1', 'q0'] a
['q1', 'q0'] no more input
aa: False
['q0'] b
['q0', 'q2'] b
['q0', 'q3', 'q2'] b
['q0', 'q3', 'q2', 'qf'] no more input
bbb: True


$ python nfa_sol.py machine5.txt input1.txt 
['qe1', 'q0', 'qe2'] a
['q1'] b
['qf'] no more input
ab: True
['qe1', 'q0', 'qe2'] a
['q1'] a
[] no more states
aabb: False
['qe1', 'q0', 'qe2'] a
['q1'] b
['qf'] b
['qf'] no more input
abb: True
['qe1', 'q0', 'qe2'] b
[] no more states
baa: False
['qe1', 'q0', 'qe2'] a
['q1'] a
[] no more states
aaabbb: False
['qe1', 'q0', 'qe2'] a
['q1'] a
[] no more states
aabb: False
['qe1', 'q0', 'qe2'] a
['q1'] b
['qf'] a
['qf'] b
['qf'] b
['qf'] no more input
ababb: True
['qe1', 'q0', 'qe2'] a
['q1'] no more input
a: False
['qe1', 'q0', 'qe2'] b
[] no more states
bb: False
['qe1', 'q0', 'qe2'] a
['q1'] a
[] no more states
aa: False
['qe1', 'q0', 'qe2'] b
[] no more states
bbb: False

If you run update46 you will get the two input files I described as well as some sample starting point code. You may use this code or start from scratch. You can complete the project by simply implementing the five partially implemented methods or functions in the code. You do not need to add anything else.

Think about what modifications you need to make to the DFA to make the simulation work for an NFA. Note in particular that each state could transition to zero, one, or more than one states when reading a single symbol. You will also need to handle epsilon closures, denoted E(q) in the text and notes. Design your code in such a way to avoid infinite loops from trying to expand states that were previously expanded (machine5.txt has a potentially infinite epsilon loop)

Feel free to ask questions, but with the start code provided, you should have a basic idea of how to proceed

Run handin46 to submit your solution. If you are working with a partner, only one person needs to hand in the lab. Include both names at the top of your program.

Home Page

Last updated: Tuesday, September 22, 2020 at 01:07:44 PM