PS1

Computer Science 313
Theory of Computation

Assignment 1 – Chapter 1

Due Wednesday 17 September on Github

Exercises 1.3, 1.4acefg

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 dfa.py along with some test cases and send it as an attachment. I should be able to run your tests by doing python dfa.py.