Homework 1 CS 301 Languages and Automata Fall 2010
Due Date:
10:45am on Thurs, Sept 9, in class (strongly recommended)
12:00 noon on Fri, Sept 10, in recitation section SES 238 (hard deadline)

Please state any assumptions you make very clearly. Answer the questions in your own words. You must do the homework individually.

  1. Exercise 0.6
  2. The example on pages 32-33 assumes a swing-door.
    1. How does the design change if the door is a sliding door that allows traffic in both directions? Explain the changes in your design. Give the state transition diagram, state transition table, and the formal definition of the corresponding finite automaton.
    2. How does the design change if the door is a sliding door that allows traffic in one direction only? Explain the changes in your design. Give the state transition diagram, state transition table, and the formal definition of the corresponding finite automaton.
  3. Exercise 1.6, parts (a) through (n)