COSC 157
Homework Assignments

Assignment #1. Due Fri, Aug 31
Textbook p. 9, exercise 1.7.

Assignment #2. Due Wed, Sep 5

Assignment #3. Due Fri, Sep 7
Textbook p. 57, exercise 2.9.

Assignment #4. Due Mon, Sep 10
Textbook p. 58, exercise 2.11, parts b) and c) (skip part a)).

Assignment #5. Due Mon, Sep 17
Textbook p. 61, exercise 2.19, parts b) and e), and p.62, exercise 2.22, parts a) and d).

Assignment #6. Due Fri, Sep 21
Textbook p. 64, exercise 2.25, parts b) and d).

Assignment #7. Due Mon, Sep 24
Textbook p. 65, exercise 2.34, parts a) and b).

Assignment #8. Due Wed, Oct 3
Textbook p. 110, exercise 3.1, part a), exercise 3.2, part a), and show that the grammar in exercise 3.2 is ambiguous.

Assignment #9. Due Fri, Oct 5
Textbook p. 113, exercise 3.20 (both parts).

Assignment #10. Due Mon, Oct 15

Assignment #11. Due Mon, Oct 22
Use Lemma 3.6.2 to show that 
  L = { a^k b^m c^k d^m | k=1,2,3,..., m=1,2,3,...}

 (where x^y means x raised to the power y)
is not context-free.

Assignment #12. Due Mon, Oct 29
Textbook p. 117, exercise 3.42, parts a) and b).
Note that you need to construct a pushdown automaton (PDA) which recognizes each of these languages and obeys the restrictions of a deterministic PDA (p. 106).

Assignment #13. Due Fri, Nov 9
Textbook p. 151, exercise 4.1 and exercise 4.9. Also, use the rules from 4.9 b) to compute a trace of your machine on the input 10111.

Assignment #14. Due Fri, Nov 16
Write the transition rules for a 2-tape Turing machine which simulates the pushdown automaton from Example 3.3.1 on p.83 of the text. Use the technique described in class to simulate the PDA and your machine should halt if the input is in the language {a^n b^n} and not halt otherwise. If you encounter unspecified details (such as exactly how to denote transition rules for a 2-tape machine), just make some reasonable decision and explain what you decided to do.

Assignment #15. Due Mon, Dec 3
Textbook p. 173, exercise 5.6.
Note that the book errata site suggests the sentence "Assume some fixed alphabet for all subparts of this exercise" be added to the end of the instructions.
Back to COSC 157 home page.