CSC 344/444

In class we covered Chapters 2 of the book and reviewed material from Appendix A (A.1 through A.5). For fun, check out Nietzsche and Heine's argument for eternal recurrence (based on a finite state argument). Movie clips:

- Jacquet-Droz' writer
- Hero's automated temple doors
- Robert-Houdin's Antonio Diavolo (starts at 2:30)
- Babbage's Difference engine

I also mentioned (but didn't show) Cantor's diagonal argument. In fact, there are really three arguments: using topology (his first argument), using the decimal expansion of a number (his second argument), and his proof that the powerset of a set is always larger than the set itself, even for infinite sets. Since the powerset of the natural numbers has the same cardinality as the real numbers, this last proof also implies that the reals are uncountable. The last proof, in a way, is the easiest. Suppose f: X -> P(X) is a function from X to the powerset of X. Then the set D = {x: x not in f(x)} is not in the range of f, so there is no function from X to its powerset which hits every element of the powerset.

Next Monday we'll continue with Section 4.1 and Chapter 5.

Be sure to check out the following blogs:

Homework is due at the beginning of next class for in-class students and by midnight for OL students.

**Submission**: you can submit the homework by hardcopy
in class or by sending it to me as an email.

1. [Reading Assignment] Read chapters 2 and 3 of the book and review sections A.1.1, A.2, A.3, A.4 and A.5.

2. [Languages, 5pt] Do Exercise 2.3 (page 19).

3. [Operations on Languages, 12pt] Do Exercise 2.7 b-e (page 20) of the book. A
language L *is closed under a function f* if f(x_{1}, ..., x_{k})
lies in L for all x_{1}, ..., x_{k} in L. For example, the natural
numbers are closed under addition and multiplication (since for all natural
numbers x and y, the sum x+y and product x*y is a natural number), but not under negation,
subtraction or division (e.g. 5 and 7 are natural numbers, but 5 - 7 = -2 is
not). The real numbers are closed under all these operations
except division (since 1/0 is not a real number). The *closure* of a set
under an operation is the smallest set that contains the original set and is
closed under the operation. For example, the closer of the natural numbers under
subtraction are the integers. For each of the problems: state whether it's
closed and, if it isn't, give a counterexample and state what the closure is.
Example: 2.7 a):

L = {a,b} is not closed under concatentation, since ab is the
concatenation of two elements of L but is itself not in L (also, aa would
have worked). The closure of L under concatenation is the smallest set that
contains both a and b as is closed under concatenation, which is {a,b}^{+}.
(Note, it is not
{a,b}*.)

4. [True or False, 12pt] If true, give an argument and if false, give a counterexample.

a) If L^{R} = L for a
language L, then all words in L are palindromes.

b)
If L^{*} = L, then L = Σ^{*}.

c)
If L^{*} is countable, then it is finite.

d)
(L^{*}J^{*})^{*} = (L u J)^{*} for
any languages L and J (using u for union).

5. [Functions, 12pt]

a) Let the function trunc:
Σ^{*}
→
Σ^{* }be defined as follows:

trunc(ε) =
ε, trunc(aw) = w, for a in Σ and w in Σ^{*}.

Is trunc one-to-one (injective)? Is trunc onto (surjective)? What is the closure of {a,b} under trunc?

b) Consider the function dup(w): Σ^{*}
→
Σ^{*}
defined as dup(w) = ww for
w in Σ^{*}.

Is dup one-to-one (injective)? Is dup onto (surjective)? What is the closure of {a,b} under dup?

c) Let the function rot: Σ^{*}
→
Σ^{* }be defined as follows:

rot(ε) = ε, rot(aw) = wa, for a in Σ and w in Σ^{*}.

Is rot one-to-one (injective)? Is rot onto (surjective)? What is the closure of {a,b} under rot?

6. [Extra Credit, 10pt] We say a pattern (a sequence of variables) matches a text, if the variables in the pattern can be replaced by non-empty words so that the pattern becomes a subword of the text. For example, the pattern xx matches the texts 'arrange' (x = r) and 'banana' (x = na or x = an) but not 'computer'. And the pattern xyx matches 'engineer' (x = e, y = ngin). Show that for a fixed alphabet Σ every word that is long enough (what's the best bound you can find) is matched by the pattern xyx. Can you find other patterns that have this property (i.e. they occur in every sufficiently long word)?

Marcus Schaefer

Last updated: September 14th, 2010.