HW2:

Find a regular expression for binary numbers divisible by 5.  Not hard, but tedious.  Recommend you design the DFA, look for loops, process the loops.

Prove that perfect squares in base 10 do not form a regular language.
This is not hard once you see the trick, and it's not tedious, it's very short.  But the hint is look at 9^2.  Look at 99^2.  Look at 999^2.  Look at 9999^2.  You should probably see a pattern with these numbers.

Use the Pumping Lemma.  Remember, the PL works is there exists a k, such that for all strings whose length is >= k, the string can be split into uvw, such that |v| >=1 |uv|<=k and all of uv*w is also part of the regular language.

The idea behind these proofs is that given k, can you find some string whose length is >= k in the language that cannot be pumped no matter how u, v, and w are set up.

In other words you get the string (based on k), but you don't get the pick the u v w.  You've got to show that it can't be pumped no matter what the u v w are.

Furthermore, you don't have to show that all of uv*w fails to be in the language, you just have to show that one of them isn't.
If uvw is and uvvw is, and uvvvw is, and uvvvvw is not, you still win, provided you can show that you're right for all choices of u, v, w.

When we proved that balanced parentheses was not regular, I said:

Assume it is regular.  Then there is a k for which the pumping lemma holds.  I will select (^k )^k.  Since |uv| <= k, no matter what u and v are, u is all ('s and v is all ('s.  So, no matter what my v is, if I pump it even once, I now have more ('s than )'s, so contradiction.  Pumping lemma failed, and the language is not regular.

With perfect squares, it's slightly more sophisticated than this, but only slightly.  Based on your k, select your string to be a bigass string, so that you have more control over what u and v are.

PUSHDOWN AUTOMATA:

A pushdown automaton contains the following stuff:
A set of states
An alphabet (for the strings that may or may not be accepted by the automaton).
A stack alphabet
A start state
A start stack symbol (the stack does not start empty; it starts with one symbol on the stack)
A set of final states (and this is optional)

Then you have a set of transitions.  Since, by default, PDA's are nondeterministic.  These transitions aren't functions.  They don't mandate which state you go to next, they are just options for where you could go next.

A transition has a:

current state
A symbol in the alphabet or empty string
A stack symbol
another state
a string of stack symbols

Here's how to read this:

Based on your current state, the next symbol to be read (or not if the transition involves the empty string) and the TOP symbol on the stack, you may then proceed to the next state (as stipulated in the transition), pop the top element off the stack, and replace it with the designated string (so you push more than one stack symbol if you want to, or you can push the empty string if you want to so that the net effect is that the stack is one element shorter).

Depending on who's doing the defining, if when you're done processing the string, the string is accepted if you end up in a final state (that's one definition) OR if you end up with an empty stack (that's another definition).

Now because this is a nondeterministic machine, there may be more than one transition to another state from this state/symbol/stack symbol combination.  If there is a way to do it so that you end up accepting the string, then the string is accepted.

Here is a PDA to accept 0^n 1^n.

States are {p,q,r}
Alphabet is {0,1}
Stack Alphabet is {A,Z}
start state is p
start stack symbol  is Z
Final states are {r}

(p,0,Z,p,AZ) <-- when we push a string onto stack, the leftmost one is the top
(p,0,A,p,AA)
(p,e,Z,q,Z)
(p,e,A,q,A)
(q,1,A,q,e)
(q,e,Z,r,Z)

000111       Z      r
      ^


1           Z    r
^

PUMPING LEMMA FOR CFL's

For every CFL, there is a k such that for all strings in the language whose length is >= k, the string can be split into

u v w x y   so that

|vx| >= 1   (in other words they can't both be empty)
|vwx| <= k

and u v^n w x^n y are all in the language for n>=0.

This is primarily used to prove a language ISN'T context-free.

a^n b^n c^n   Show that this is NOT context-free.