Fall 2000, CSE 468: Assignment 1

Distributed: Published on the web on Sep 8.
Due: Sep 20 (in class).
Total maximum score: 100 points.

The purpose of this assignment is to "refresh the memory" about some of the preliminary notions, and to provide experience with regular expressions.

Please write your solutions as clearly and concisely as possible.

(30 pts) For each of the following binary relations on N (the set of natural numbers), say whether it is a equivalence relation or not. Motivate the answer. In case it is an equivalence relation, define the partition associated to the relation.
1. x R y if and only if x + y is an even number.
2. x R y if and only if -10 < x - y < 10
3. x R y if and only if the decimal representations of x and y have the same length and differ at most for the last digit. Example: 0 is related to 1, 10 is related to 11, 1 is not related to 10 and 10 is not related to 20.
(30 pts) Consider the language L on the alphabet A = {a,b,c} defined inductively as follows:
1. abcc is in L
2. if x is in L then axcc is in L
Prove that L is equal to the language L' = {aⁿbc²ⁿ | n > 0}. Hint: prove that L is contained in L' by structural induction, and that L' is contained in L by induction on n.
(30 pts) For each of the following languages, give a regular expression which defines the same language.
1. The language of strings representing even natuaral numbers: 0, 2, 4, ... , 10, 12, ...
2. The language of all strings on {a,b,c} which contain exactly one occurrence of b.
3. The language L on {a,b} defined inductively as follows:
  1. ab is in L
  2. if x is in L then abx is in L
4. The language of all strings on {a,b} which have odd length.
(10 pts) Find the mistake in the following reasoning, which proves (erroneously) that all people have the same height:
- Statement: for every n, in any group of n people everybody has the same height.
- Proof:
  - Base case: (n=0) in a empty group, the statement is trivially true
  - Inductive step: Take a group of n+1 people. Send away one person (say, John). By inductive hypothesis, the remaining people have the same height. Call back John and send away another person (say, Jack). The new group contains John and is again of n people, therefore John has the same height as everybody else (and as Jack).