CS46 — Homework 2

Regular Languages: Due Thursday 6 Feb at the start of class
Starting files are available from my public cs46 folder
cd ~/cs46/
cp -r examples/homework/wk2 homework/
cp -r examples/labs/wk2/ labs/
git status
git add homework/wk2 labs/wk2/
git commit -m "week2 start"
git push
More DFA practice
Written Exercises
Complete the written exercises from hw02.pdf. Latex source is provided in your homework folder. I recommend drawing your DFA on a separate sheet of paper. If you want to do it digitally, I can show you how. Hint: It's super tedious, and not a particular goal of the course!
Implement a DFA
Implement a generic DFA in the programming language of your choice. I recommend python and the examples here will use python. For this 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

ee 0
eo 0
oo 0
oe 1

ee a oe
ee b eo
eo a oo
eo b ee
oo a eo
oo b oe
oe a ee
oe b oo
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., ee)

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

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

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

Your code should test each input string against the machine and label each string as accepted or not accepted.
$ python dfa_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 sample code includes 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.

The key to this project is (1) understanding how a DFA works and (2) understanding how a python dictionary or other similar hash map works. Note that both the State class and the Machine class use dictionaries (indicated by {} to store info. If you are unfamiliar with dictionary syntax, giyf, or use one of the python refs in the lab, or a partner (your partner can either tell you how they work, or fetch the book for you). For State objects, the key for the dictionary should be a symbol and the value the name of another state. For Machine objects, the dictionary should store names of states as keys and return the actual state objects as values.

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

Run git add, git commit, git push as needed 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.