Computer Science 313
Theory of Computation

Assignment 1 – Chapter 1

Due Wednesday 2 September

Exercises 1.3, 1.4acefg

Note: There is a typo in older printings of the book. Exercise 1.4.e should specify {w | w starts with an a and has at most one b.}

If you’re feeling ambitious (especially if you’re ambitious about continuing in computer science) I encourage you to do this assignment and the rest of them in LaTex, the document-preparation system used by computer scientists, mathematicians, and others. If you’re not interested in learning/using LaTex, then you can skip the next paragraph and just do your assignment in MSWord, using PowerPoint or another graphical tool to create your automata figures. Either way, make sure that you submit (by sakai) just a single PDF document containing your writeup.

For the LaTex approach, grab this repository from github (ask me for a quick github help session if you need it). Next open question1.pptx and export it as PDF. Then type make at the Linux command line to create the file ps0.pdf. You will rename and edit ps0.tex for each assignment, and modify the Makefile accordingly. You can use PowerPoint, LibreOffice Impress, or any other drawing program to create and edit figures, as long as you can export them as PDF (or PNG or JPG) and include them in your final document.

Extra credit

  • Use the constructive proof in Theorm 1.25 (pp.45-46) to build a finite automaton to recognize the union of languages A = {a}, B = {b}. Hint: You will have to have explicit trap states in your initial two machines.
  • Write a DFA class in Python (or your favorite programming language). This class should have a constructor method, which takes as inputs the elements from Definition 1.5 (p. 35):
    1. A set of states, implemented as a list of numbers
    2. An alphabet, implemented as a string
    3. A transition function, implemented as a list of elements, where each element contains a state, a symbol, and another state. Each element can be a tuple, a list, or an object belonging to the class Rule.
    4. A start state, a single number
    5. A set of accepting states, a list of numbers

    You should also have an accept method, which takes a string and returns True if the DFA accepts the string, and returns False otherwise. Ideally, you should also have a __repr__ method (takes self and returns a string), so that printing out a DFA object will result in a useful representation (showing states, alphabet, etc.). Put it in a file along with some test cases and send it as an attachment. I should be able to run your tests by doing python