Hi everyone,

We (Professor Variyam and I) have both your first exams and homeworks graded.
Your individual results are up on Blackboard, and some coarse stats are available
on my course website (http://cs.jhu.edu/~ferraro/600.471f11/). If you have a
question on the homework or questions 1-3 on the exam, you can ask me; Professor
Variyam graded 4 and 5 on the exam.

As I state on my page, this is course is supposed to be a rigorous course in theory.
While some homework and exam problems displayed rigor, overall the rigor was not
consistent. What does it mean to be rigorous? It means to provide a complete proof
that covers all cases. It does not mean to SOLELY provide an intuitive description.

That being said, your intuition should definitely help guide you. But your intuition
can easily fool you. That is one purpose of a proof: to make sure your intuition was
not misleading you. For those interested, I've included as a P.S. an example of why
you can't just trust your intuition.

What makes this course difficult is not providing a correct answer, but rather in
justifying it. It's one thing to provide a grammar, or a DFA, and *claim* that it
recognizes (WLOG) a CFL or a regular language, respectively. However, can you actually
prove it? Recall that a language is simply a set of strings. Thus, to show that some
grammar G (or machine M) recognizes (or accepts) a language L, you must show that L(G) = L
(or L(M)=L). To show set equivalence, you must show that L(G) \subseteq L AND
L \subseteq L(G); that is, every x \in L(G) is L, and conversely that every x \in L is in L(G).

Here are two quick exercises for you to think about:
1) How would you go about proving that some grammar G recognizes L={0^n 1^n | n \ge 0}?
(Hint: can you prove that G recognizes all strings of length 0 of L? Of length 1? Of length 2?...

2) Similarly, how would you prove that given regular languages L_1 and L_2, the
concatenation of L_1 and L_2 is regular?

Aside from not providing rigorous arguments, the most common error I saw (on both the homeworks
and exams) involved the pumping lemma. Specifically:

(*) not choosing a string in the language, and not providing a supplementary argument of why
the string they pumped was sufficient; and
(*) choosing one, specific assignment of x,y,z for s=xyz; and
not considering all cases (e.g., when $x = \varepsilon$).

Let's take the pumping lemma for regular languages. All it says is if a language is regular,
then for all strings s of sufficient length (e.g., length at least the pumping length), there
exist strings x, y and z such that s=xyz where |xy|\le p, |y| > 0 and for all i \ge 0, xy^iz \in L.
Note that it does not say that you can *choose* what x, y or z are!

Of course, via exhaustive reasoning, you can assign structures to x, y and z, but they must be
general. So for example, in showing {0^n1^n} is not regular, for s=0^p1^p, you know that y can
contain only 0s, and it must contain at least one. Therefore you can write x=0^q, y=0^r, z=0^t1^p
where q+r+t=p and r>0 (and of course q and t are non-negative). Then you can complete the argument.

If you have any questions, or can't read what's written, please let me know.

Best,
Frank

P.S.
This example is from James Munkres's classic _Topology_ book.

An "x" means Cartesian product. "\cup" means union. In this problem, an open set is (a, b) x (c, d)

A set A is connected if it cannot be written as the union of two disjoint open sets B and C. That is,
if for every disjoint and open B and C, B \cup C is a proper subset of A (does not fully cover A),
then A is connected.

Let K={1/n | n \ge 1}. Let C1 = K x [0,1]; C2 = -K x [-1,0]; C3 = [0,1] x -K; C4 = [-1,0] x K.

Let C = C1 \cup C2 \cup C3 \cup C4. Show that C is connected.