CS46 Homework 2

Regular Languages

Written solutions to problems 2.1.3, 2.2.2, and two of the following three problems: 1.8.3, 2.1.2, 2.2.6ab are due at the beginning of class Thursday Feb 4.

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.

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.

$ 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

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.

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

CS46 — Homework 2