Project 3

Constructing an NFA Simulator

Project Overview

This project will get you acquainted with nondeterministic finite automata (NFAs). You will write a Python program that simulates an NFA.

What you need to do

Write a Python program (call it nfa.py) by completing the following steps:

  1. In whichever approach you wish, have your program read in a text file called nfa.txt, and construct an NFA from this information. This file will contain data that describes an NFA.

  2. The structure of nfa.txt will be as follows:

    • Line 1: the states of the NFA (separated by commas, if there is more than one state)
    • Line 2: the alphabet of the NFA (separated by commas, if there is more than one symbol)
    • Line 3: the starting state of the NFA
    • Line 4: the final/accept states of the NFA (separated by commas, if there is more than one accept state)
    • Line 5 and onward: the transition rules, where each rule takes the form a,b,c (where being in state ‘a’ and reading symbol ‘b’ transitions to new state ‘c’)

  3. In addition to the given alphabet, all NFAs may also contain empty-string transitions (we will use @ to represent an empty string transition).

  4. After your program constructs an NFA, read in another file called input.txt, where each line in the file is a string that will run on your NFA.

  5. Both nfa.txt and input.txt should be assumed to be in the same directory as your Python program. Do not ask for the names of these; just hardcode them in.

  6. Simulate each string in input.txt using your NFA, and write the output (accept or reject) into a new file called output.txt (also in the same directory as your Python program, and each result on a separate line).

  7. There is one special input string ‘@’, which represents the empty string (a string of no characters).

How to submit

To submit, save your Python program in a file named nfa.py, and upload/submit it to Moodle by the due date.