Spring 2007
Assignment 11
Assigned 24 April, Due 2 May
- Read Chapter 10
- Do Excercises:
- Do any three of the following Problems
Assignment 10
Assigned 19 April, Due 26 April.
- Read Chapter 9.
- Do Excercises:
- 9.4
- 9.5
- 9.6
- 9.7 e, g, h
- 9.8
- 9.10
- 9.11
- Do Problems
Assignment 9
Assigned 12 April, Due 19 April
- Read Chapter 8
- Do Excercises:
- Do Problems
- 8.11
- 8.17
- 8.20
- Either 8.27 OR 8.28 (your choice)
- Extra Credit
Assignment 8
- Read Chapter 7
- Do Excercises:
- Do Problems
- 7.13 (hint: this is almost the same as 7.12)
- 7.17
- 7.21
- 7.30
- Extra Credit - see notes from 27 March.
Assignment 7
- Read Chapter 6
- Do Excercises:
- 6.1 You can get credit for pseudo-code. This doesn't have
to compile under any real language.
- 6.2
- 6.4
- Do Problems:
- 6.6
- 6.7
- 6.18
- 6.21 You may assume the result of 6.20.
- Extra Credit: Do excercise 6.1 in C or Java, and show that
it compiles and runs correctly. There are a few tricky parts
here to get everything to compile.
Assignment 6
- Read Chapter 5
- Do Excercises:
- Do Problems:
Assignment 5
- Read Chapter 4
- Do Excercises
- Do Problems
- 4.16
- 4.19 (hint: Use the result from 4.16)
- 4.22
- 4.27
Assignment 4
Assigned 8 Feb. Due 15 Feb.
- Read Chapter 3
- Do Excercises
- Consider the languages in Excercise 3.8. For each one, is
it regular? Is it context-free? Prove your answers.
- Do Problems
- 3.9
- 3.11
- 3.12
- 3.13
- 3.14
- 3.15
- I mentioned in class two different definitions for Context
Sensitive Grammars: In one the LHS of the rule had to be no
larger than the RHS, In the other, rules were of the form
&alpha A &beta -> &alpha &beta &gamma where A is a non-terminal;
&alpha and &gamma are in V* and &beta is in V+. Clearly all
rules of the second form are of the first form. Show that one can
express the rule
AB -> BA
using rules of the second form. This is not a formal proof that
the two forms are equivalent, but it's the hard part of that
proof.
- Extra Credit Complete the proof that the two
definitions of Context Sensitive Grammars are equivalent. Note
that you do not need to solve the first part of this problem to
get the extra credit part.
Assignment 3
Assigned 1 Feb. Due 8 Feb.
- Read Chapter 2
- Do Excercises
- 2.1
- 2.2 (note: You only need the result of Example 2.36, you
don't need to know the technique for this problem.)
- 2.9
- 2.10
- 2.11
- 2.13
- 2.15
- 2.16
- Do Problems
Assignment 2
Assigned 25 Jan. Due 1 Feb.
- Read Sections 1.3 and 1.4 (pages 63 - 82)
- Do Excercises:
- 1.18
- 1.19 a, c
- 1.20 a, c, e, f, h(h is a little tricky)
- 1.24 a, c, e, h
- 1.28
- 1.29 b (This is an important problem, you should do a and
c as well, but we won't grade them.)
- 1.30
- Do Problems:
- 1.51
- 1.53
- 1.60
- 1.61
- 1.63 (If you can't do part a, assume it and do part b,
which is easier.)
- Extra Credit:
Assignment 1
Assigned 18 Jan. Due 25 Jan. Late penalty waived if handed in by 29 Jan.
- Skim Chapter 0.
- Read Sections 1.1 and 1.2 (pages 31 - 62)
- Do Excercises
- 1.3
- 1.5 c, d, e
- 1.6 e, g, i, j, m
- 1.8 a
- 1.9 a
- 1.12 - only give the DFA, the Regular Expression is not
required.
- 1.16
- Do Problems:
Assignment 0
Assigned 1 Jan. Due 17 Jan.
- Buy Textbook.
- Come to class.
Last Modified 24 April 2007