NFAs and non-regular languagues

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 a NFA simulator

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 qfEach 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.,

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 bbbYour 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.