Project 1

Constructing a DFA Simulator

Project Overview

This project will get you acquainted with deterministic finite automata (DFAs). You will write a Python program that simulates a DFA.

What you need to do

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

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

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

    • Line 1: the states of the DFA (separated by commas, if there is more than one state)
    • Line 2: the alphabet of the DFA (separated by commas, if there is more than one symbol)
    • Line 3: the starting state of the DFA
    • Line 4: the final/accept states of the DFA (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. After your program constructs a DFA, read in another file called input.txt, where each line in the file is a string that will run on your DFA.

  4. Both dfa.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.

  5. Simulate each string in input.txt using your DFA, 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).

  6. 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 dfa.py, and upload/submit it to Moodle by the due date.