Stærðfræðimynstur í tölvunarfræði

Weekly note 14

In the lecture on monday Dec. 5th we might perhaps finish up with the last few detail from Chapter 11 if needed, but mainly we will look back over the material covered in the class, look at the organization of the exam and answer questions. The section will be in that week as usual.

Below are 5 excercises that you are to solve and turn in to your section teacher before noon monday December 5th. Remember to mark your solutions with the number of your section and the name of the section teacher. Also below are few extra excercises that you can use to practice on and make sure that you have understood the material. Some of them will be solved in the sections if there is time.

Homework 13

1. Exercise 14 in section 11.1 on page 749 in the textbook.

2. Exercise 12 in section 11.2 on page 757 in the textbook.

3. Exercise 16 in section 11.3 on page 765 in the textbook.

4. Construct a finite-state automaton that has as input strings over the set {a, b}. It outputs 1 if the last two letters are not ab, and 0 otherwise.

5. [Exam '04] A grammar is said to be ambiguous if you can construct two different derivation trees for the same string in the language. Here is a grammar with the nonterminal symbol S (which is also the start symbol), the terminal symbols a and b, and the productions S → SS, S → a, and S → b. Is this grammar ambiguous? Justify your answer.

Hand these exercices in before noon monday December 5th.

From section 11.1:

13, 21, 23, 27.

From section 11.2:

3, 7, 9.

From section 11.3:

5, 9, 13, 19.

Remember that the above exercises are for you to practice on, and that you get the most out of them by trying to solve them yourselves (not by looking at someone else solving them!). The exercises in bold are more "interesting" than the others and it is more likely that they will be covered in the sections.