CS 154 Introduction to Automata and Complexity Theory Handout 2

Winter 1996  R. van Glabbeek  January 10, 1996

Problem Set 1 Date Due: January 15, 1996

Reading: Floyd and Beigel, Chapter 0-2 Homework: Do the following exercises (FB refers to Floyd and Beigel The Language of Machines). Each problem must be submitted on a separate sheet. The homeworks must be solved without any collaboration.

1. (6 points) Consider the following truth table for p(u, v):

v

u

t f t f t
t t t t t
f f f t t

For each of the following predicates determine whether they are true or false:

(a) (∃v)(∃u)p(u, v)

(b) (∀v)(∀u)p(u, v)

(c) (∀u)(∃v)p(u, v)

(d) (∃v)(∀u)p(u, v)

(e) (∀v)(∃u)p(u, v)

(f) (∃u)(∀v)p(u, v)

2. (4 points) Which of the following languages are equal to (a ∪ b)^{∗}?

(a) a^{∗} ∪ b^{∗}

(b) a(a ∪ b)^{∗} ∪ b(a ∪ b)^{∗}

(c) (ab)^{∗}

(d) a^{∗} ∪ (a ∪ b)^{∗}b(a ∪ b)^{∗} In case of equality, explain informally and briefly, and in case of inequality, give a counter example.

3. (5 points) FB exercise 0.5-2 (a).

4. (15 points) For every natural number p ≥ 2, prove that every natural number n > 0 has a unique p-adic representation.

5. (5 points) FB exercise 0.6-3.

6. (10 points) FB exercise 0.6-17. Extra credit problem (optional) Prove that in any group of six students taking this class, there is a group of three people who are all either mutual strangers or all mutual acquaintences.

You may assume that all pairs of students in this class are either mutual strangers or mutual acquaintences.

(Harder) Generalize the above to infinite populations: In a class with infinitely many students, prove that there are either infinitely many mutual strangers or infinitely many mutual acquaintances.